Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
MATEMATYKA DYSKRETNA - MATERIAA
Y DO WYKLADU
Zliczanie
ALEKSANDRA ORPEL
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Prawa sumy
TWIERDZENIE
Jeżeli A i B są zbiorami skończonymi,
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Prawa sumy
TWIERDZENIE
Jeżeli A i B są zbiorami skończonymi, to
|A *" B| = |A| + |B| - |A )" B|.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Prawa sumy
TWIERDZENIE
Jeżeli A i B są zbiorami skończonymi, to
|A *" B| = |A| + |B| - |A )" B|.
W szczególności, gdy zbiory A i B są rozłączne, to
|A *" B| = |A| + |B|.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Prawa sumy
TWIERDZENIE
Jeżeli A i B są zbiorami skończonymi, to
|A *" B| = |A| + |B| - |A )" B|.
W szczególności, gdy zbiory A i B są rozłączne, to
|A *" B| = |A| + |B|.
PRZYKA
AD
Stwierdzić ile liczb ze zbioru S:={1,...,2001} jest podzielnych przez
5 lub przez 7.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Prawa iloczynu
TWIERDZENIE
Jeżeli A i B są zbiorami skończonymi, to
|A � B| = |A| � |B|.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Prawa iloczynu
TWIERDZENIE
Jeżeli A i B są zbiorami skończonymi, to
|A � B| = |A| � |B|.
W ogólności, dla k (k " N) dowolnych zbiorów skończonych
A1, ..., Ak zachodzi
k

|A1 � ... � Ak| = |Ai|.
i=1
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Prawa iloczynu
TWIERDZENIE
Jeżeli A i B są zbiorami skończonymi, to
|A � B| = |A| � |B|.
W ogólności, dla k (k " N) dowolnych zbiorów skończonych
A1, ..., Ak zachodzi
k

|A1 � ... � Ak| = |Ai|.
i=1
PRZYKA
AD
Wyznaczyć liczbę możliwych sposobów wylosowania (bez
zwracania) 3 kart z klasycznej talii kart.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Prawo potęgi
TWIERDZENIE
Niech A i B będą dowolnymi zbiorami skończonymi. Rozważmy
zbiór BA := {f : A B}. Wówczas |BA| = |B||A|.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Prawo potęgi
TWIERDZENIE
Niech A i B będą dowolnymi zbiorami skończonymi. Rozważmy
zbiór BA := {f : A B}. Wówczas |BA| = |B||A|.
PRZYKA
AD
Wyznaczyć liczbę podzbiorów zbioru n-elementowego A.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Wariacje bez powtórzeń
DEFINICJA
Niech S będzie skończonym, niepustym zbiorem o n elementach i
niech r będzie dowolną liczbą naturalną taką, że 0 < r n.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Wariacje bez powtórzeń
DEFINICJA
Niech S będzie skończonym, niepustym zbiorem o n elementach i
niech r będzie dowolną liczbą naturalną taką, że 0 < r n.
r-wyrazową wariacją elementów zbioru S bez powtórzeń
nazywamy
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Wariacje bez powtórzeń
DEFINICJA
Niech S będzie skończonym, niepustym zbiorem o n elementach i
niech r będzie dowolną liczbą naturalną taką, że 0 < r n.
r-wyrazową wariacją elementów zbioru S bez powtórzeń
nazywamy dowolny ciąg r różnych elementów zbioru S.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Wariacje bez powtórzeń
DEFINICJA
Niech S będzie skończonym, niepustym zbiorem o n elementach i
niech r będzie dowolną liczbą naturalną taką, że 0 < r n.
r-wyrazową wariacją elementów zbioru S bez powtórzeń
nazywamy dowolny ciąg r różnych elementów zbioru S.
TWIERDZENIE
Liczba r-wyrazowych wariacji elementów zbioru S bez powtórzeń
jest równa
P(n, r) = n(n - 1)(n - 2) � ... � (n - r + 1).
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Wariacje z powtórzeniami
DEFINICJA
Niech S będzie skończonym, niepustym zbiorem o n elementach i
niech r będzie dowolna liczbą naturalną taką, że 0 < r n.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Wariacje z powtórzeniami
DEFINICJA
Niech S będzie skończonym, niepustym zbiorem o n elementach i
niech r będzie dowolna liczbą naturalną taką, że 0 < r n.
r-wyrazową wariacją elementów zbioru S z powtórzeniami
nazywamy dowolny ciąg r elementów zbioru S.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Wariacje z powtórzeniami
DEFINICJA
Niech S będzie skończonym, niepustym zbiorem o n elementach i
niech r będzie dowolna liczbą naturalną taką, że 0 < r n.
r-wyrazową wariacją elementów zbioru S z powtórzeniami
nazywamy dowolny ciąg r elementów zbioru S.
TWIERDZENIE
Liczba r-wyrazowych wariacji elementów zbioru S z powtórzenimi
jest równa nr .
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Wariacje z powtórzeniami
DEFINICJA
Niech S będzie skończonym, niepustym zbiorem o n elementach i
niech r będzie dowolna liczbą naturalną taką, że 0 < r n.
r-wyrazową wariacją elementów zbioru S z powtórzeniami
nazywamy dowolny ciąg r elementów zbioru S.
TWIERDZENIE
Liczba r-wyrazowych wariacji elementów zbioru S z powtórzenimi
jest równa nr .
PRZYKA
AD
Wyznaczyć liczbę możliwych ciągów 3 elementowych ze zbioru
S:={A,B,C,D,E}. Ile jest takich ciągów, które nie zawierają
powtarzających się liter?
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Permutacje
DEFINICJA
Permutacją elementów zbioru S (o n elementach) bez powtórzeń
nazywamy n-wyrazową wariacją elementów zbioru S bez
powtórzeń.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Permutacje
DEFINICJA
Permutacją elementów zbioru S (o n elementach) bez powtórzeń
nazywamy n-wyrazową wariacją elementów zbioru S bez
powtórzeń.
TWIERDZENIE
Liczba permutacji elementów zbioru S (o n elementach) jest równa
P(n, n) = n!.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Permutacje
DEFINICJA
Permutacją elementów zbioru S (o n elementach) bez powtórzeń
nazywamy n-wyrazową wariacją elementów zbioru S bez
powtórzeń.
TWIERDZENIE
Liczba permutacji elementów zbioru S (o n elementach) jest równa
P(n, n) = n!.
PRZYKA
AD
Wyznaczyć liczbę różnowortościowych odwzorowań
n-elemetowego zbioru A na siebie.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Kombinacje
DEFINICJA
Niech A będzie ustalonym zbiorem n elementowym. Każdy k
elementowy podzbiór tego zbioru nazywamy k elementową
kombinacją, gdzie 1 k n.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Kombinacje
DEFINICJA
Niech A będzie ustalonym zbiorem n elementowym. Każdy k
elementowy podzbiór tego zbioru nazywamy k elementową
kombinacją, gdzie 1 k n.
TWIERDZENIE
Liczba wszystkich k elementowych kombinacji zbioru n
n
elementowego jest równa , 1 k n.
k
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Kombinacje
DEFINICJA
Niech A będzie ustalonym zbiorem n elementowym. Każdy k
elementowy podzbiór tego zbioru nazywamy k elementową
kombinacją, gdzie 1 k n.
TWIERDZENIE
Liczba wszystkich k elementowych kombinacji zbioru n
n
elementowego jest równa , 1 k n.
k
PRZYKA
AD
Na ile sposobów można wybrać komisję składającą się z 4 osób
mając do dyspozycji grupę 9 kandydatów?
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
DEFINICJA
Podziałem zbioru niepustego S nazywamy rodzinę parami
rozłącznych jego podzbiorów, których suma jest równa S.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
DEFINICJA
Podziałem zbioru niepustego S nazywamy rodzinę parami
rozłącznych jego podzbiorów, których suma jest równa S.
LEMAT
Niech dane będa zbiory skończone A i B.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
DEFINICJA
Podziałem zbioru niepustego S nazywamy rodzinę parami
rozłącznych jego podzbiorów, których suma jest równa S.
LEMAT
Niech dane będa zbiory skończone A i B. Jeżeli � : A B
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
DEFINICJA
Podziałem zbioru niepustego S nazywamy rodzinę parami
rozłącznych jego podzbiorów, których suma jest równa S.
LEMAT
Niech dane będa zbiory skończone A i B. Jeżeli � : A B oraz
istnieje taka liczba r > 0,
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
DEFINICJA
Podziałem zbioru niepustego S nazywamy rodzinę parami
rozłącznych jego podzbiorów, których suma jest równa S.
LEMAT
Niech dane będa zbiory skończone A i B. Jeżeli � : A B oraz
istnieje taka liczba r > 0, że dla dowolnego b " B przeciwobraz
�-1({b}) := {a " A; �(a) = b}
ma r elementów,
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
DEFINICJA
Podziałem zbioru niepustego S nazywamy rodzinę parami
rozłącznych jego podzbiorów, których suma jest równa S.
LEMAT
Niech dane będa zbiory skończone A i B. Jeżeli � : A B oraz
istnieje taka liczba r > 0, że dla dowolnego b " B przeciwobraz
�-1({b}) := {a " A; �(a) = b}
ma r elementów, to
|A|
|B| = .
r
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
TWIERDZENIE
Rozważmy zbiór X o n elementach i jego podział na k podzbiorów
X1, ..., Xk o liczebności |Xi| = ni, tj. n1 + ... + nk = n.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
TWIERDZENIE
Rozważmy zbiór X o n elementach i jego podział na k podzbiorów
X1, ..., Xk o liczebności |Xi| = ni, tj. n1 + ... + nk = n. Załóżmy, że
elementy w ramach każdego z podzbiorów są nierozróżnialne.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
TWIERDZENIE
Rozważmy zbiór X o n elementach i jego podział na k podzbiorów
X1, ..., Xk o liczebności |Xi| = ni, tj. n1 + ... + nk = n. Załóżmy, że
elementy w ramach każdego z podzbiorów są nierozróżnialne.
Rozważmy teraz permutacje rozróżnialne zbioru X , tj. takie, w
których w co najmniej jednym miejscu występują elementy z
różnych zbiorów Xi.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
TWIERDZENIE
Rozważmy zbiór X o n elementach i jego podział na k podzbiorów
X1, ..., Xk o liczebności |Xi| = ni, tj. n1 + ... + nk = n. Załóżmy, że
elementy w ramach każdego z podzbiorów są nierozróżnialne.
Rozważmy teraz permutacje rozróżnialne zbioru X , tj. takie, w
których w co najmniej jednym miejscu występują elementy z
różnych zbiorów Xi. Wówczas liczba rozróżnialnych permutacji
zbioru X jest równa
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
TWIERDZENIE
Rozważmy zbiór X o n elementach i jego podział na k podzbiorów
X1, ..., Xk o liczebności |Xi| = ni, tj. n1 + ... + nk = n. Załóżmy, że
elementy w ramach każdego z podzbiorów są nierozróżnialne.
Rozważmy teraz permutacje rozróżnialne zbioru X , tj. takie, w
których w co najmniej jednym miejscu występują elementy z
różnych zbiorów Xi. Wówczas liczba rozróżnialnych permutacji
zbioru X jest równa
n!
.
n1! � ... � nk!
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
TWIERDZENIE
Rozważmy zbiór X o n elementach i jego podział na k podzbiorów
X1, ..., Xk o liczebności |Xi| = ni, tj. n1 + ... + nk = n. Załóżmy, że
elementy w ramach każdego z podzbiorów są nierozróżnialne.
Rozważmy teraz permutacje rozróżnialne zbioru X , tj. takie, w
których w co najmniej jednym miejscu występują elementy z
różnych zbiorów Xi. Wówczas liczba rozróżnialnych permutacji
zbioru X jest równa
n!
.
n1! � ... � nk!
PRZYKA
AD
Rozważmy permutacje zbioru X := {b, b, a, a, a, r, r}. Ile jest
permutacji odpowiadających słowu BARBARA? Ile jest
rozróżnialnych permutacji?
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
DEFINICJA
Podziałem uporządkowanym zbioru S nazywamy ciąg podzbiorów
(A1, ..., Ak), k > 1, którego elementy A1, ..., Ak tworzą podział
zbioru S.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
DEFINICJA
Podziałem uporządkowanym zbioru S nazywamy ciąg podzbiorów
(A1, ..., Ak), k > 1, którego elementy A1, ..., Ak tworzą podział
zbioru S.
TWIERDZENIE
Niech dany będzie zbiór n elementowy S.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
DEFINICJA
Podziałem uporządkowanym zbioru S nazywamy ciąg podzbiorów
(A1, ..., Ak), k > 1, którego elementy A1, ..., Ak tworzą podział
zbioru S.
TWIERDZENIE
Niech dany będzie zbiór n elementowy S. Wówczas liczba jego
podziałów uporządkowanych (A1, ..., Ak),
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
DEFINICJA
Podziałem uporządkowanym zbioru S nazywamy ciąg podzbiorów
(A1, ..., Ak), k > 1, którego elementy A1, ..., Ak tworzą podział
zbioru S.
TWIERDZENIE
Niech dany będzie zbiór n elementowy S. Wówczas liczba jego
podziałów uporządkowanych (A1, ..., Ak), takich, że |Ai| = ni,
i=1,...,k, tj. n1 + ... + nk = n,
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
DEFINICJA
Podziałem uporządkowanym zbioru S nazywamy ciąg podzbiorów
(A1, ..., Ak), k > 1, którego elementy A1, ..., Ak tworzą podział
zbioru S.
TWIERDZENIE
Niech dany będzie zbiór n elementowy S. Wówczas liczba jego
podziałów uporządkowanych (A1, ..., Ak), takich, że |Ai| = ni,
i=1,...,k, tj. n1 + ... + nk = n, jest równa
n!
.
n1! � ... � nk!
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
TWIERDZENIE
Jeżeli skończony zbiór S jest podzielony na k podzbiorów, to co
najmniej jeden z nich ma |S|/k lub więcej elementów.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
TWIERDZENIE
Jeżeli skończony zbiór S jest podzielony na k podzbiorów, to co
najmniej jeden z nich ma |S|/k lub więcej elementów.
TWIERDZENIE
Dla dowolnych liczb naturalnych s, r, t, takich , że
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
TWIERDZENIE
Jeżeli skończony zbiór S jest podzielony na k podzbiorów, to co
najmniej jeden z nich ma |S|/k lub więcej elementów.
TWIERDZENIE
Dla dowolnych liczb naturalnych s, r, t, takich , że s > rt
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
TWIERDZENIE
Jeżeli skończony zbiór S jest podzielony na k podzbiorów, to co
najmniej jeden z nich ma |S|/k lub więcej elementów.
TWIERDZENIE
Dla dowolnych liczb naturalnych s, r, t, takich , że s > rt i
dowolnej funkcji f : S T , gdzie |S| = s i |T | = t,
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
TWIERDZENIE
Jeżeli skończony zbiór S jest podzielony na k podzbiorów, to co
najmniej jeden z nich ma |S|/k lub więcej elementów.
TWIERDZENIE
Dla dowolnych liczb naturalnych s, r, t, takich , że s > rt i
dowolnej funkcji f : S T , gdzie |S| = s i |T | = t, istnieje y " T
taki, że
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
TWIERDZENIE
Jeżeli skończony zbiór S jest podzielony na k podzbiorów, to co
najmniej jeden z nich ma |S|/k lub więcej elementów.
TWIERDZENIE
Dla dowolnych liczb naturalnych s, r, t, takich , że s > rt i
dowolnej funkcji f : S T , gdzie |S| = s i |T | = t, istnieje y " T
-1
taki, że f (y) ma więcej niż r elementów.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
TWIERDZENIE
Jeżeli skończony zbiór S jest podzielony na k podzbiorów, to co
najmniej jeden z nich ma |S|/k lub więcej elementów.
TWIERDZENIE
Dla dowolnych liczb naturalnych s, r, t, takich , że s > rt i
dowolnej funkcji f : S T , gdzie |S| = s i |T | = t, istnieje y " T
-1
taki, że f (y) ma więcej niż r elementów.
TWIERDZENIE
Jeżeli X jest zbiorem n elementowym, a Y jest zbiorem m
elementowym i n > m,
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
TWIERDZENIE
Jeżeli skończony zbiór S jest podzielony na k podzbiorów, to co
najmniej jeden z nich ma |S|/k lub więcej elementów.
TWIERDZENIE
Dla dowolnych liczb naturalnych s, r, t, takich , że s > rt i
dowolnej funkcji f : S T , gdzie |S| = s i |T | = t, istnieje y " T
-1
taki, że f (y) ma więcej niż r elementów.
TWIERDZENIE
Jeżeli X jest zbiorem n elementowym, a Y jest zbiorem m
elementowym i n > m, to nie istnieje funckja różnowartościowa
f : X Y .
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
PRZYKA
AD
Niech A będzie pewnym ustalonym dziesięcioelementowym
podzbiorem zbioru {x " N : 1 x 50}. Udowodnić, że istnieją
dwa różne pięcioelementowe podzbiory zbioru A takie, że sumy
wszystkich elementów każdego z tych dwóch podzbiorów są sobie
równe.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Przykłady końcowe
PRZYKA
AD
Niech S := {a, b, c, d} i T := {1, 2, 3, 4, 5, 6, 7}.
Ile jest funkcji różnowartościowych z T do S?
Ile jest funkcji różnowartościowych z S do T ?
Ile jest funkcji z S do T ?
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT
Podstawowe prawa
Elementy kombinatoryki
Zasada szufladkowa Dirichleta
Przykłady końcowe
PRZYKA
AD
Niech S := {a, b, c, d} i T := {1, 2, 3, 4, 5, 6, 7}.
Ile jest funkcji różnowartościowych z T do S?
Ile jest funkcji różnowartościowych z S do T ?
Ile jest funkcji z S do T ?
PRZYKA
AD
Na ile sposobów można n identycznych przedmiotów w k
rozróżnialnych pudełkach.
ALEKSANDRA ORPEL MATEMATYKA DYSKRETNA - MAT