plik

Matematyka dyskretna

2. Rozmieszczanie przedmiotów w pudełkach

Niech danych będzie n pudełek i k przedmiotów. Załóżmy, że w każdym pudełku
mieści się co najwyżej jeden przedmiot.
1

◦

Załóżmy, że pudełka są rozróżnialne i przedmioty są rozróżnialne. Wówczas opisem
rozmieszczenia jest funkcja różnowartościowa ze zbioru przedmiotów w zbiór pudełek
(wariacja bez powtórzeń). Liczba rozmieszczeń wynosi:

(n − k)!

◦

Załóżmy, że pudełka są nierozróżnialne a przedmioty są rozróżnialne. Wówczas ist-
nieje co najwyżej jedno rozwiązanie.
3

◦

Załóżmy, że pudełka są rozróżnialne a przedmioty są nierozróżnialne. Wówczas opi-
sem rozmieszczenia jest k-elementowy podzbiór zbioru pudełek (kombinacje bez po-
wtórzeń). Liczba rozmieszczeń wynosi:

k!(n − k)!

◦

Załóżmy, że pudełka są nierozróżnialne i przedmioty są nierozróżnialne. Wówczas
istnieje co najwyżej jedno rozwiązanie.

Niech teraz w każdym pudełku można umieścić dowolną ilość przedmiotów.
1

◦

Załóżmy, że pudełka są rozróżnialne i przedmioty są rozróżnialne. Wówczas jest to
wariacja z powtórzeniami. Ilość rozmieszczeń wynosi: n

◦

Załóżmy, że pudełka są nierozróżnialne a przedmioty są rozróżnialne. Wówczas opi-
sem rozmieszczenia jest podział zbioru pudełek.
3

◦

Załóżmy, że pudełka są rozróżnialne a przedmioty są nierozróżnialne. Wówczas opi-
sem rozmieszczenia jest multizbiór pudełek.
4

◦

Załóżmy, że pudełka są nierozróżnialne i przedmioty są nierozróżnialne. Wówczas opi-
sem rozmieszczenia jest podział liczby k na co najwyżej n składników. Takie podziały
nazywamy partycjami liczby k.

3. Kombinacje

Definicja 3.1
Niech dany będzie zbiór X, taki że |X| = n. Każdy k-elementowy podzbiór zbioru
X nazywamy k-elementową kombinacją zbioru X.
Liczbę k-elementowych kombinacji zbioru n-elementowego oznaczamy:

n
k

Twierdzenie 3.1
Prawdziwe są następujące równości:

(a)

k=0

= 2

(b)

n − k

(c)

n − 1

k − 1

n − 1

(d)

n − 1

k − 1

Dowód:
(b)
Niech P

(X) oznacza rodzinę wszystkich k-elementowych podzbiorów zbioru X, a

n−k

(X) - rodzinę wszystkich (n − k)-elementowych podzbiorów zbioru X. Zdefinu-

jemy bijekcję P

(X) ←→ P

n−k

(X) w ten sposób, że jeśli A ∈ P

(X) to podzbiorowi A

przyporządkujemy zbiór X \ A ∈ P

n−k

(X). Tak zdefiniowana funkcja jest różnowar-

tościowa i przekształca zbiór P

(X) na zbiór P

n−k

(X). A więc |P

(X)| = |P

n−k

(X)|.

Ponieważ |P

(X)| =

n
k

oraz |P

n−k

(X)| =

n−k

, stąd

n
k

n−k

(X) będzie rodziną k-elementowych podzbiorów zbio-

ru X. Przedstawmy zbiór P

(X) w postaci sumy rozłącznych zbiorów A i B. Niech

A będzie rodziną wszystkich k-elementowych podzbiorów zawierających element n i
niech B = P

(X) \ A.

Utwórzmy bijekcję A ←→ P

k−1

(Y ), gdzie Y = {1, . . . , n − 1}, w ten sposób, że do-

wolnemu zbiorowi Z ∈ A przyporządkujemy zbiór Z \ {n}. Taka funkcja jest ”1 − 1”
i ”na” co oznacza, że rodzina A jest równoliczna ze zbiorem P

k−1

(Y ).

Rozpatrzmy teraz zbiór B = P

(Y ) (bo podzbiory zbioru B są k-elementowe i nie

zawierają elementu n). Mamy więc:

= |P

(X)| = |A| + |B| = P

k−1

(Y ) + P

(Y ) =

n − 1

k − 1

n − 1

(d)
Rozpatrzmy zbiór par Z = {(A, x): A ∈ P

(X) ∧ x ∈ A}. Elementy zbioru Z mo-

gą być dobrane na dwa sposoby. Możemy najpierw wybrać k-elementowy podzbiór
A ⊂ X i potem ze zbioru A wybrać element x ∈ A.
Otrzymujemy, że: |Z| =

n
k

· k.

Możemy odwrócić ten proces i najpierw wybrać element x ∈ X i do niego dobrać
taki podzbiór A ⊂ X, że x ∈ A.
Otrzymujemy: |Z| = n ·

n−1
k−1

, gdyż podzbiór A możemy traktować jako (k − 1)-

elementowy podzbiór zbioru (n − 1)-elementowego.
Z powyższych rozważań wynika równość (d).

Uwaga 3.1

k!(n − k)!

Definicja 3.2
Silnią dolną nazywamy wielomian: [x]

= x(x − 1) · . . . · (x − k + 1)

Silnią górną nazywamy wielomian: [x]

= x(x + 1) · . . . · (x + k − 1)

4. Multizbiory (kombinacje z powtórzeniami)

◦

Niech ϕ

(X) będzie rodziną wszystkich n-elementowych ciągów elementów zbio-

ru X. Zdefiniujmy w tym zbiorze relację róznoważności ∼ w następujący sposób:
(x

, . . . , x

) ∼ (y

, . . . , y

), gdy istnieje permutacja σ zbioru wszystkich wskaźników

{1, . . . , n}, taka że y

= x

σ(i)

, i = 1, . . . , n

Tak zdefiniowana relacja dzieli zbiór ϕ

(X) na klasy abstrakcji. Każdą taką klasę

abstrakcji nazywamy multizbiorem.
2

◦

Niech dana będzie funkcja charakterystyczna χ: X → N

, taka że jeśli x ∈ X, to χ(x)

oznacza liczbę wystąpień elementu x w multizbiorze wyznaczonym przez funkcję χ.
Liczba wszystkich elementów wyznaczonych przez χ wynosi:

x∈X

χ(x)

◦

Niech X = {1, . . . , n}. Wówczas każdy k-elementowy podzbiór zbioru X można utoż-
samiać z ciągiem silnie rosnącym elementów tego zbioru. Każdy k-elementowy mul-
tizbiór można utożsamiać z ciągiem niemalejącym o długości k utworzonym z ele-
mentów zbioru X.

Twierdzenie 4.1
Liczba k-elementowych multizbiorów utworzonych ze zbioru n-elementowego jest
równa

n+k−1

Dowód:
Niech X = {1, . . . , n} i niech M

(X) oznacza rodzinę wszystkich k-elementowych

multizbiorów utworzonych ze zbioru X. Załóżmy, że {x

, . . . , x

} ∈ M

(X), przy

czym x

¬ . . . ¬ x

. Utwórzmy z tego ciągu nowy ciąg {x

, x

+ 1 . . . , x

+ k − 1} =

, . . . , y

}, gdzie y

= x

+ i − 1.

Zauważmy, że ciąg {y

, . . . , y

} jest ciągiem rosnącym:

i+1

− y

= (x

i+1

+ i) − (x

+ i − 1) = x

i+1

− x

+ 1 > 0

Ponadto gdyby x

= n, to y

= n + k − 1, niech zatem Y = {1, . . . , n + k − 1}.

Zatem każdy ciąg niemalejący {x

, . . . , x

} można rozszerzyć do ciągu rosnącego

, . . . , y

}, gdzie y

< . . . < y

. Postępowanie odwrotne jest także możliwe. Z każ-

dego ciągu {y

, . . . , y

} można utworzyć ciąg niemalejący {y

, y

−1, . . . , y

−k +1} =

, . . . , x

}, gdzie x

= y

− i + 1.

Zdefiniowaliśmy więc bijekcję M

(X) ←→ P

(Y ), a więc oba te zbiory są równolicz-

ne, czyli: |M

(X)| = |P

(Y )| =

n+k−1

Uwaga 4.1

n + k − 1

[n]

Copyright

Grzegorz Gierlasiński