Permutacją z powtórzeniami zbioru $n$–elementowego, nazywamy każdy ciąg $n$–wyrazowy utworzony z elementów tego zbioru, wśród których pewne elementy powtarzają się odpowiednio $n_1$, $n_2$, $...$, $n_k$ razy.

Liczba elementów permutacji z powtórzeniami wyraża się wzorem:

Obliczymy, ile wyrazów (mających sens lub nie) można utworzyć ze wszystkich liter słowa:

1. $LITERA$

2. $LITERAT$

3. $APARATURA$

Rozwiązanie:

1. Wszystkie możliwe ustawienia liter $\left\{L, I, T, E, R, A\right\}$ można zapisać w postaci sześcioelementowych ciągów. Pierwszy element (literę) można wybrać na 6 sposobów, drugi na $5$ sposobów, itd. Korzystając z reguły mnożenia, możemy utworzyć: $6·5·4·3·2·1=6!=720$ wyrazów.

2. W wyrazie $LITERAT$ występują dwie litery $T$. Litery $T$ możemy zamienić miejscami na $2!$ sposoby, a utworzony wyraz nie ulegnie zmianie. Z liter wyrazu $LITERAT$ można więc utworzyć $\frac{6!}{2!}=\frac{720}{2}=360$ wyrazów.

3. W wyrazie $APARATURA$ są $4$ litery $A$ i $2$ litery $R$. Korzystamy ze wzoru na liczbę permutacji z powtórzeniamipermutacja z powtórzeniamipermutacji z powtórzeniami. $\frac{9!}{4!·2!}=\frac{9·8·7·6·5}{2}=7560$

Odpowiedź:

Ze wszystkich liter słowa $LITERA$ można utworzyć $720$ wyrazów, z liter słowa $LITERAT$ można utworzyć $360$ wyrazów, a z liter słowa $APARATURA$ aż $7560$ wyrazów.

Sprawdzian z matematyki składający się z $5$ zadań pisało łącznie $100$ uczniów z klas trzecich. Każde zadanie zostało rozwiązane przez przynajmniej $60$ uczniów. Wykażemy, że można wskazać takich dwóch uczniów, że każde zadanie zostało rozwiązanie przynajmniej przez jednego z nich.

Rozwiązanie:

Dla każdych z dwóch uczniów rozpatrzmy najpierw zbiór zadań, których żaden nie rozwiązał. Tych zbiorów jest

$\left(\begin{array}{c}100\\ 2\end{array}\right)=\frac{100·99}{2}=4950$

Wykażemy, że przynajmniej jeden z nich jest pusty.

Dla każdego zadania istnieje co najwyżej $100-60=40$ uczniów, którzy go nie rozwiązali.

Każde zadanie należy do co najwyżej

$\left(\begin{array}{c}40\\ 2\end{array}\right)=\frac{40\cdot 39}{2}=780$ spośród wyznaczonych zbiorów.

Niepustych zbiorów jest co najwyżej

$5\cdot 780=3900$

Ponieważ

$3900<4950$,

zatem istnieje para uczniów, dla której zbiór zadań, których żaden z dwójki tych uczniów nie rozwiązał, jest pusty.

Zapoznaj się z animacją, pokazującą przykłady wykorzystania kombinacji do zliczania obiektów osadzonych w kontekście realistycznym.

W partii $n$ wyprodukowanych śrub $w$ jest wykonanych wadliwie. Obliczymy, ile jest możliwości, że wśród $m$ wylosowanych śrub, dokładnie $d$ okaże się wadliwych.

Wylosować dokładnie $d$ śrub wadliwych, z ogólnej liczby $w$ śrub wadliwych, można na

$\left(\begin{array}{c}w\\ d\end{array}\right)$ sposobów.

Pozostałe wylosowane śruby mają być dobre. Tych $m-d$ śrub należy wylosować z $n-w$ śrub dobrych.

Można to zrobić na

$\left(\begin{array}{c}n-w\\ m-d\end{array}\right)$ sposobów.

Wszystkich możliwości jest zatem

$\left(\begin{array}{c}w\\ d\end{array}\right)·\left(\begin{array}{c}n-w\\ m-d\end{array}\right)$

Odpowiedź:

Jest $\left(\begin{array}{c}w\\ d\end{array}\right)·\left(\begin{array}{c}n-w\\ m-d\end{array}\right)$ możliwości wylosowania śrub wadliwych.

Obliczymy, na ile sposobów można rozmieścić w $n$ rozróżnialnych szufladach $k$:

1. nierozróżnialnych szalików, jeżeli każda szuflada może zawierać co najwyżej jeden szalik,

2. rozróżnialnych szalików, jeżeli nie ma ograniczenia na liczbę szalików, które mogą się zmieścić w jednej szufladzie,

3. rozróżnialnych szalików, jeżeli każda szuflada może zawierać co najwyżej jeden szalik.

Rozwiązanie:

1. Zauważmy, że $n\ge k$. Szaliki są nierozróżnialne, więc liczba wszystkich sposobów wyboru jest równa liczbie kombinacji $k$–elementowych ze zbioru $n$–elementowego, czyli $\left(\begin{array}{c}n\\ k\end{array}\right)$.

2. Każdy z $k$ szalików można umieścić w jednej z $n$ szuflad. Zatem dla pierwszego szalika jest $n$ możliwości, dla drugiego szalika jest $n$ możliwości,
   $\dots$
   dla $k$–tego szalika jest $n$ możliwości. Wszystkich możliwości jest więc: $n·n·...·n=n^k$.

3. W tym przypadku $n\ge k$. Dla pierwszego szalika jest $n$ możliwości wyboru szuflady, dla drugiego szalika jest $\left(n-1\right)$ możliwości wyboru szuflady,
   $\dots$
   dla $k$–tego szalika jest $\left(n-k+1\right)$ możliwości wyboru szuflady. Wszystkich możliwości jest więc: $n\cdot \left(n-1\right)\cdot \left(n-2\right)\cdot \dots \cdot \left(n-k+1\right)=\frac{n!}{\left(n-k\right)!}$.

permutacją z powtórzeniami zbioru $n$–elementowego, nazywamy każdy ciąg $n$–wyrazowy utworzony z elementów tego zbioru, wśród których pewne elementy powtarzają się odpowiednio $n_1$, $n_2$, $...$, $n_k$ razy; liczba elementów permutacji z powtórzeniami wyraża się wzorem: