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!

(n − k)!

2

◦

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:

n!

k!(n − k)!

4

◦

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

k

.

2

◦

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)

n

X

k=0

n

k

!

= 2

n

(b)

n

k

!

=

n

n − k

!

(c)

n

k

!

=

n − 1

k − 1

!

+

n − 1

k

!

(d)

n

k

!

=

n

k

n − 1

k − 1

!

Dowód:
(b)
Niech P

k

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

P

n−k

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

jemy bijekcję P

k

(X) ←→ P

n−k

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

k

(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

k

(X) na zbiór P

n−k

(X). A więc |P

k

(X)| = |P

n−k

(X)|.

Ponieważ |P

k

(X)| =



n
k



oraz |P

n−k

(X)| =



n

n−k



, stąd



n
k



=



n

n−k



.

(c)
Niech X = {1, . . . , n} i niech P

k

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

ru X. Przedstawmy zbiór P

k

(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

k

(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

k

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

zawierają elementu n). Mamy więc:

n

k

!

= |P

k

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

k−1

(Y ) + P

k

(Y ) =

n − 1

k − 1

!

+

n − 1

k

!

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

k

(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

n

k

!

=

n!

k!(n − k)!

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

k

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

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

k

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

4. Multizbiory (kombinacje z powtórzeniami)

1

◦

Niech ϕ

n

(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

1

, . . . , x

n

) ∼ (y

1

, . . . , y

n

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

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

i

= x

σ(i)

, i = 1, . . . , n

Tak zdefiniowana relacja dzieli zbiór ϕ

n

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

abstrakcji nazywamy multizbiorem.
2

◦

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

0

, 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

χ(x)

3

◦

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

k



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

k

(X) oznacza rodzinę wszystkich k-elementowych

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

1

, . . . , x

k

} ∈ M

k

(X), przy

czym x

1

¬ . . . ¬ x

k

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

1

, x

2

+ 1 . . . , x

k

+ k − 1} =

{y

1

, . . . , y

k

}, gdzie y

i

= x

i

+ i − 1.

Zauważmy, że ciąg {y

1

, . . . , y

k

} jest ciągiem rosnącym:

y

i+1

− y

i

= (x

i+1

+ i) − (x

i

+ i − 1) = x

i+1

− x

i

+ 1 > 0

Ponadto gdyby x

k

= n, to y

k

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

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

1

, . . . , x

k

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

{y

1

, . . . , y

k

}, gdzie y

1

< . . . < y

k

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

dego ciągu {y

1

, . . . , y

k

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

1

, y

2

−1, . . . , y

k

−k +1} =

{x

1

, . . . , x

k

}, gdzie x

i

= y

i

− i + 1.

Zdefiniowaliśmy więc bijekcję M

k

(X) ←→ P

k

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

ne, czyli: |M

k

(X)| = |P

k

(Y )| =



n+k−1

k



Uwaga 4.1

n + k − 1

k

!

=

[n]

k

k!

Copyright

c

Grzegorz Gierlasiński