Permutacje z powtórzeniami
Niech S = {a1, a2, a3, ..., ak} oraz n = n1 + n2 + ...+ nk.
Tworzymy ciąg, w którym element
a1 występuje n1 razy
a2 występuje n2 razy
...
ak występuje nk razy.
Utworzony n- elementowy ciÄ…g nazywamy n- elementowÄ… permurtacjÄ… z
powtórzeniami zbioru k  elementowego. Liczbę tych permutacji
1
Pnn ,n2 ,...,nk
oznaczamy symbolem
Twierdzenie:
Liczba n  elementowych permutacji zbioru k- elementowego wynosi
n!
1
Pnn ,n2 ,...,nk=
n1!n2!...nk!
Dowód:
Przestawienia jednakowych elementów nie zmieniają permutacji. Jeżeli
więc element aj występuje nj razy, to liczba permutacji jest nj! razy
mniejsza, niż dla nj różnych elementów.
Przykład 1
Ile wyrazów 8-mio literowych (mających sens lub nie) można ułożyć z
liter słowa MATEMATYKA
RozwiÄ…zanie
Podane słowo ma 10 liter, w tym 6 różnych. Litera A  występuje n1=3
razy, M i T pon2= 2 razy, pozostale występują raz. Mamy do czynienia z
permutacją zbioru o n= 10 elementach, z powtórzeniami. Występują 6
grup jednakowych elementów o liczebnościach: n1 = 3, n2 = n3 = 2, n4=
n5 =n6 =1, przy czym n = n1+n2+...+n6. Liczba wszystkich możliwych
10!
3
P10,2,2,1,1,1= =
słów to liczba permutacji 151200
3!2!2!
MD - kombinatoryka
12
Przykład 2
Ile wyrazów 11-to literowych (mających sens lub nie) można ułożyć z
liter słowa KATALIZATOR
RozwiÄ…zanie
Podane słowo ma 11 liter, w tym 8 różnych.
Mamy n1=3 (dla A), n2 = 2 (dla T) , n3 = ...= n8 =1 dla pozostałych
znaków.
Stąd liczba różnych słów
11!
3
P11,2,1,1,1,1,1,1= =3326400
3!2!
Przykład 3.
Oblicz na ile sposobów można rozmieścić 10 róznych kul w 5
szufladach tak, aby w każdej była inna liczba kul?
RozwiÄ…zanie.
W każdej szufladzie ma być inna liczba kul. Jedyna możliwość to
podział na
n1 + n2 + n3 + n4 + n5 = 0 + 1 + 2 + 3 + 4 = 10.
Poszczególnym przedmiotom należy przyporządkować szuflady w taki
sposób, by pierwsza nie była związana z żadnym przedmiotem, druga 
z jednym, trzecia  z dwoma itp. To znaczy, utworzyć ciąg w którym
poszczególne szuflady wystąpią 0, 1, 2, 3, 4 razy. Takich ciągów można
10!
1
P10,2,3,4= =12600
utworzyć
1!2!3!4!
Wariacje z powtórzeniami
Ze zbioru n- elementowego losujemy k elemntów ze zwracaniem.
Otrzymany ciąg wylosowanych elementów nazywamy k- elementową
wariacjÄ… zbioru n- elementowego.
Twierdzenie
Liczba k- wyrazowych wariacji z powtórzeniami ze zbioru n-
elementowego jest równa
Vnk=nk
MD - kombinatoryka
13
Przykład
Jest siedem ponumerowanych kul, które umieszczamy w czterech
pojemnikach. Ile jest różnych sposobów rozmieszczenia kul, jeśli
wiadomo, że w każdym z pojemników zmieści się siedem kul?
Każda kula może trafić do każdego pojemnika, 7 razy losujemy
każdy z 4 pojemników, stąd różnych sposobów jest 47.
Kombinacje z powtórzeniami
Ze zbioru n elementowego losujemy k elementów ze zwracaniem. Z
wylosowanych elementów tworzymy nowy zbiór  w ten sposób
otrzymujemy kombinacjÄ™ k- elemntowÄ… zbioru n- elementowego ze
Cnk
zwracaniem. LiczbÄ™ tych kombinacji oznaczamy przez
Twierdzenie
Liczba wszystkich k- elementowych kombinacji z powtórzeniami ze
zbioru n- elementowego jest wyrażona wzorem
n + k -1
ëÅ‚ öÅ‚
k
Cnk = Cn+k-1 = ìÅ‚ ÷Å‚
ìÅ‚ ÷Å‚
k
íÅ‚ Å‚Å‚
Przykład
Ile razy więcej jest kombinacji 2-elementowych z powtórzeniami ze
zbioru 10-elementowego, niż kombinacji 10-elementowych z
powtórzeniami ze zbioru 2-elementowego? Odp. 5.
Przykład
Z talii 24 kart wybieramy kolejno 4 karty, zwracając za każdym razem
wylosowaną kartę do talii. Ile różnych układów 4 kart można w ten
sposób otrzymać? Odp. 17 550.
Przykład
Mamy trzy rodzaje owoców: jabłka, gruszki i pomarańcze. Ile różnych
paczek można utworzyć, jeśli każda paczka ma zawierać 5 owoców?
Odp. 21.
MD - kombinatoryka
14
Kombinacje z powtórzeniami  uzasadnienie
Zagadnienie kombinacji z powtórzeniami można sformułować inaczej:
Na ile sposobów można pomalować k jednakowych kul,
mając do dyspozycji n kolorów?
Szukana liczbę jest funkcją liczby kolorów n i liczby kul k -
oznaczymy jÄ… przez f (n,k).
Gdy mamy 3 kule i 3 różne kolory, biały (b), czerowny (c) i niebieski (n)
.
Wszystkie możliwości pokolorowania 3 kul tymi kolorami to
bbb bbc bcc ccc bbn bnn ccn cnn nnn bcn
Metoda 1. Równania rekurencyjne
Oznaczenia: kolory majÄ… numery 1 do n
Zbiór wszystkich pokolorowań dzielimy na dwa rozłączne podbiory:
C1  nie występuje kolor n C2 - pozostałe
|C1| = f (n -1, k) |C2| = ?
W C2 z każdego pokolorowania usuwamy jedną kule koloru n
(zawsze taka będzie); otrzymujemy pokolorowanie
k-1 kul, też za pomocą n kolorów, a więc
|C2| = f (n, k-1)
Stąd równanie rekurencyjne
f (n, k) = f (n -1, k) + f (n, k-1)
Przy tym, nietrudno pokazać, że
f (1, k) = 1 f (n, 1) = n
Obliczając dla kilku początkowych wartości n, k otrzymujemy
f (2, 2) = f (1, 2) + f (2, 1) = 1 + 2 = 3
f (2, 3) = f (1, 3) + f (2, 2) = 1 + 3 = 4
f (3, 2) = f (2, 2) + f (3, 1) = 3 + 3 = 6
f (3, 3) = f (2, 3) + f (3, 2) = 4 + 6 = 10
MD - kombinatoryka
15
f (n,k)=Cnk
Teraz można uzasadnić, że
n + k -1
ëÅ‚ öÅ‚
k k
÷Å‚
n
ìÅ‚
gdzie C = Cn+k-1 = ìÅ‚ ÷Å‚
k
íÅ‚ Å‚Å‚
Dowód indukcyjny
k
ëÅ‚ öÅ‚
k
ìÅ‚ ÷Å‚
f (1,k) = C1k = Ck = = 1
Dla n =1 mamy ìÅ‚k ÷Å‚ ,
íÅ‚ Å‚Å‚
n
ëÅ‚ öÅ‚
1 1
ìÅ‚
f (n,1) = Cn = Cn+1-1 = = n
ìÅ‚1÷Å‚
÷Å‚
dla k = 1
íÅ‚ Å‚Å‚
k k k
Cn+Cn -1=Cn+1 (C bez kresek)
Skorzystamy z tozsamości
f (n-1,k)+f (n,k-1)=
k k
=Cnk +Cnk-1=Cn-1+k-1+Cn+-1
-1 k-1-1
k k k
=Cn+k-2+Cn+-1 =Cn+k-1=Cnk=f (n,k)
k-2
cnu.
Metoda 2. Funkcja tworzÄ…ca
Inna interpretacja:
liczba całkowitych nieujemnych rozwiązań równania
t 1 + t 2 + ... + t n = k
Tu t j oznacza liczbÄ™ kul pomalowanych kolorem j,
wszystkich kul jest k , kolorów n.
Rozpatrzmy wyrażenie
g (x) = (1 + x + x2 + ... ) n =
= (1 + x + x2 + ... )(1 + x + x2 + ... ) ... (1 + x + x2 + ... )
n czynników
Jaki jest współczynnik przy xk ?
MD - kombinatoryka
16
Z każdego nawiasu bierzemy taką potęgę, by ich suma była równa k .
Zróbmy inaczej. Korzystamy z równości
1 + x + x2 + ... = 1 / (1-x)
oraz z rozwinięcia
"
r
k
(1+ x)r = ìÅ‚ ÷Å‚
"ëÅ‚ öÅ‚
ìÅ‚k ÷Å‚x
k=0
íÅ‚ Å‚Å‚
StÄ…d
"
k
(1+x)-n= (-x)k
"(-n)
k!
k=0
gdzie (-n)k = (-n)(-n-1)...(-n-k+1) = (-1)k n(n+1) ... (n+k-1)
więc
"
k
g(x)=
"(n+k-1)!x
(n-1)!k!
k=0
a stąd szukana liczba rozwiązań równania
(= liczbie kombinacji z powtórzeniami) ,
(n+k-1)!
f (n,k)=
(n-1)!k!
Symbole wielomianowe
(inne spojrzenie na permutacje z powtórzeniami)
Zbiór n -elementowy dzielimy na r rozłącznych podzbiorów o
liczebnosciach t1 , t2 , ... , tr , przy czym
t1 + t2 + ... + tr = n
Liczba możliwości takich podziałów jest równa
MD - kombinatoryka
17
n n - t1 n - (t1 + t2) n - (t1 + ... + tr-2) n - (t1 + ... + tr-1)
ëÅ‚ öÅ‚ëÅ‚ öÅ‚ëÅ‚ öÅ‚ ëÅ‚ öÅ‚ëÅ‚ öÅ‚
ìÅ‚ ÷Å‚ìÅ‚ ÷Å‚ìÅ‚ ÷Å‚LìÅ‚ ÷Å‚ìÅ‚ ÷Å‚ =
ìÅ‚t ÷Å‚ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚ìÅ‚ ÷Å‚
t2 ÷Å‚ìÅ‚ t3 tr-1 tr
íÅ‚ Å‚Å‚íÅ‚ Å‚Å‚íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚íÅ‚ Å‚Å‚
1
n! (n-t1)! (n-(t1+t2))!
Å" Å" Å"...
t1!(n-t1)! t2!(n-(t1+t2))! t3!(n-(t1+t2+t3))!
(n-(t1+...+tr-2))! (n-(t1+...+tr-1))!
Å" =
... Å"
tr-1!(n-(t1+...+tr-1))! tr!(n-(t1+...+tr ))!
ozn
n
n! ëÅ‚ öÅ‚
ìÅ‚ symbol wielomianowy
=
ìÅ‚t , t2... ,tr ÷Å‚
÷Å‚
t1!t2!... tr!
íÅ‚ 1 Å‚Å‚
Otrzymany rezultat jest więc identyczny jak dla permutacji z
powtórzeniami (dlaczego?).
Dla r = 2 symbol wielomianowy jest zwykłym symbolem
dwumianowym; podstawiajÄ…c t1 = k oraz t2 = n - k (bo t1+t2 = n) mamy
n n n
ëÅ‚ öÅ‚ n! ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
ìÅ‚ ÷Å‚ = = ìÅ‚ ÷Å‚ = ìÅ‚ ÷Å‚
k!(n - k)!
íÅ‚k, n - k Å‚Å‚ íÅ‚k Å‚Å‚ íÅ‚n - k, k Å‚Å‚
Symbol wielomianowy występuje we wzorze na potęgę wielomianu
n
ëÅ‚ öÅ‚
1 r
(x1 + x2 + ... + xr )n = ìÅ‚
"
ìÅ‚t , ... ,tr ÷Å‚x1tLxrt
÷Å‚
íÅ‚
t1,t2 ,...,tr "N 1 Å‚Å‚
t1 +t2 +...+tr =n
Szczególnym przypadkiem tego wzoru, przy r = 2, jest wcześniej
poznany wzór dwumianowy. Wystarczy podstawić x1 = a, x2 = b oraz
jak poprzednio, t1 = k i t2 = n - k .
MD - kombinatoryka
18