Twierdzenie o mnożeniu
Twierdzenie o mnożeniu, twierdzenie dotyczące zbiorów mówiące, że jeżeli zbiór A ma m elemntów, a zbiór B ma n elementów, to liczba różnych par (x, y) takich, że x∈A i y∈B wynosi m · n.
Jeżeli dane są dwa skończone zbiory A i B, to liczba różnych par (x, y), takich, że x∈A oraz b∈B jest równa .
Ogólna wersja twierdzenia o mnożeniu
Liczba różnych ciągów (x1 , x2, ..., xn)
takich, że xk możemy wybrać na mk sposobów,
k = 1, 2, ..., n jest równa
m1 · m2 · ... · mn.
Ilustracja graficzna twierdzenia o mnożeniu, jest przejrzysta na tak zwanym drzewku, jednak dla dużych n rysowanie takiego drzewka jest bardzo uciążliwe.
Przykład
Ile różnych wyników można otrzymać przy rzucie monetą i kostką?
Rozwiązanie
2 · 6 = 12
(O, 1), (O, 2), (O, 3),(O, 4), (O, 5), (O, 6)
(R, 1), (R, 2), (R, 3),(R, 4), (R, 5), (R, 6)
Drzewko
