Kombinatoryka — zadania

Silnia to iloczyn kolejnych liczb naturalnych:

$$4!=4\cdot3\cdot2\cdot1=24$$

Odpowiedź: C. $24$.

Silnia to iloczyn kolejnych liczb naturalnych:

$$4!=4\cdot3\cdot2\cdot1=24$$

Odpowiedź: C. $24$.

To permutacja pięciu elementów:

$$P_5=5!=5\cdot4\cdot3\cdot2\cdot1=120$$

Skąd to wynika: na pierwsze miejsce mamy $5$ możliwości, na drugie $4$, i tak dalej — mnożymy.

Odpowiedź: $120$ sposobów.

To liczba permutacji zbioru $5$-elementowego:

$$5!=5\cdot4\cdot3\cdot2\cdot1=120$$

Odpowiedź: $120$ sposobów.

1. Kolejność nie ma znaczenia: $\binom{10}{3}=\frac{10\cdot9\cdot8}{6}=120$.

Odpowiedź: $120$

Na każdej z trzech pozycji mamy $10$ możliwości:

$$10\cdot10\cdot10=10^3=1000$$

To wariacja z powtórzeniami: $n^k$, gdzie $n=10$, $k=3$.

Odpowiedź: $1000$ kodów.

Permutacja to ustawienie wszystkich elementów w kolejności. Liczba permutacji to $n!$.

Dlaczego: na pierwszą pozycję mamy $n$ możliwości, na drugą $n-1$, i tak dalej — iloczyn daje $n!$.

Odpowiedź: B. $n!$.

1. $5$ liter, w tym M i A po dwa razy: $\frac{5!}{2!\,2!}=30$.

Odpowiedź: $30$

Z definicji przyjmujemy:

$$0!=1$$

Dlaczego tak: istnieje dokładnie jeden sposób ustawienia pustego zbioru — nie robić nic. Ta umowa sprawia też, że wzory kombinatoryczne działają bez wyjątków.

Odpowiedź: B. $1$.

Skracamy silnie:

$$\frac{6!}{4!}=\frac{6\cdot5\cdot4!}{4!}=6\cdot5=30$$

Wskazówka: $6!=6\cdot5\cdot4!$, więc $4!$ się skraca — nie trzeba liczyć pełnych silni.

Odpowiedź: $30$.

1. Wybór cyfr: nieparzyste $\binom52=10$, parzyste $\binom52=10$; ustawienia: $4!=24$. Razem $2400$ (z zerem na początku).
2. Złe: $0$ na początku — druga parzysta $4$ sposoby, nieparzyste $\binom52=10$, reszta ustawiona na $3!=6$ sposobów: $240$.
3. $2400-240=2160$.

Odpowiedź: $2160$

Rozpisujemy licznik tylko do $4!$ i skracamy:

$$\frac{6!}{4!}=\frac{6\cdot5\cdot4!}{4!}=6\cdot5=30$$

Odpowiedź: $30$.

Z definicji przyjmujemy $0!=1$.

Dlaczego: jest tylko jeden sposób ustawienia zbioru pustego — nie robić nic.

Odpowiedź: A. $1$.

1. Sklejamy Anię i Bartka w blok: $5$ „obiektów” — $5!=120$ ustawień.
2. Wewnątrz bloku: $2$ ustawienia. Razem $240$.

Odpowiedź: $240$

Wybieramy $3$ elementy z $5$, przy czym kolejność ma znaczenie, a elementy się nie powtarzają:

$$5\cdot4\cdot3=60$$

Wzór: $\frac{n!}{(n-k)!}=\frac{5!}{2!}=60$.

Dla porównania: $125=5^3$ to wariacje z powtórzeniami.

Odpowiedź: A. $60$.

$$3!=3\cdot2\cdot1=6$$

Wypisane: ABC, ACB, BAC, BCA, CAB, CBA.

Odpowiedź: $6$ sposobów.

1. $2$K+$2$M: $\binom72\binom52=210$; $3$K+$1$M: $\binom73\binom51=175$; $4$K: $\binom74=35$.
2. Razem $420$ (kontrola: $\binom{12}4-\binom54-\binom71\binom53=495-5-70=420$ ✓).

Odpowiedź: $420$

To permutacja czterech elementów:

$$4!=24$$

Uwaga: zero nie występuje wśród cyfr, więc żadna z tych liczb nie zaczyna się od zera — nie musimy nic odejmować.

Odpowiedź: $24$ liczby.

Wszystkie trzy litery są różne, więc liczba permutacji:

$$3!=6$$

Wypisane: KOT, KTO, OKT, OTK, TKO, TOK.

Odpowiedź: $6$.

1. Przypadek 1: pierwsza cyfra to $5$ — drugą piątkę na jedno z $5$ miejsc, pozostałe $4$ cyfry: po $9$ możliwości: $5\cdot9^4=32\,805$.
2. Przypadek 2: pierwsza cyfra $\ne0,5$ — $8$ możliwości; dwie piątki na $\binom52=10$ sposobów; pozostałe $3$ cyfry po $9$: $8\cdot10\cdot729=58\,320$.
3. Razem $32\,805+58\,320=91\,125$.

Odpowiedź: $91\,125$

Rozpoznanie: kolejność ma znaczenie (przewodniczący to inna funkcja niż zastępca), a jedna osoba nie może pełnić obu — to wariacja bez powtórzeń.

$$12\cdot11=132$$

Odpowiedź: $132$ sposoby.

Krok 1 — skracamy $8!$ przez $6!$:

$$\frac{8!}{6!}=8\cdot7=56$$

Krok 2 — dzielimy przez $2!=2$:

$$\frac{56}{2}=28$$

Uwaga: to symbol Newtona $\binom{8}{2}=28$.

Odpowiedź: $28$.

1. Wszystkich trójkątów: $\binom{10}3=120$.
2. Z dwoma bokami dziesięciokąta (trzy kolejne wierzchołki): $10$.
3. Z dokładnie jednym bokiem: $10$ boków $\cdot$ $6$ wierzchołków niesąsiednich z tym bokiem $=60$.
4. $120-10-60=50$.

Odpowiedź: $50$

Każda moneta daje $2$ możliwości, a monety są rozróżnialne:

$$2^3=8$$

Wypisanie: OOO, OOR, ORO, ROO, ORR, ROR, RRO, RRR.

Odpowiedź: D. $8$.

$$\frac{5!}{3!}=5\cdot4=20$$

Odpowiedź: D. $20$.

1. Wszystkich rozmieszczeń: $3^5=243$.
2. Włączenia–wyłączenia: pusta co najmniej jedna szuflada: $3\cdot2^5-3\cdot1^5=96-3=93$.
3. $243-93=150$.

Odpowiedź: $150$

Rozpoznanie: nagrody są różne, więc kolejność przydziału ma znaczenie; jedna osoba nie może dostać dwóch — bez powtórzeń.

$$7\cdot6\cdot5=210$$

Wzór: $\frac{7!}{4!}=210$.

Odpowiedź: $210$ sposobów.

Krok 1 — sklejamy dwie osoby w jeden „blok". Mamy wtedy $3$ obiekty do ustawienia (blok + dwie osoby):

$$3!=6$$

Krok 2 — wewnątrz bloku dwie osoby można zamienić miejscami:

$$2!=2$$

Krok 3 — mnożymy:

$$6\cdot2=12$$

Metoda „sklejania". Gdy elementy mają być razem, traktujemy je jak jeden obiekt, a potem mnożymy przez permutacje wewnątrz bloku.

Odpowiedź: $12$ sposobów.

1. Ustawiamy $5$ zer — powstaje $6$ luk (przed, między i za zerami).
2. Jedynki wstawiamy do $3$ różnych luk: $\binom63=20$.

Odpowiedź: $20$

Na każdej z pięciu pozycji mamy $2$ możliwości:

$$2^5=32$$

To wariacja z powtórzeniami — litery mogą się powtarzać.

Odpowiedź: C. $32$.

Rozpisujemy licznik:

$$\frac{(n+1)!}{n!}=\frac{(n+1)\cdot n!}{n!}=n+1$$

Odpowiedź: B. $n+1$.

1. Miejsca parzyste: $2,4,6$ — dokładnie trzy, liczby parzyste też trzy: $3!=6$ ustawień.
2. Liczby nieparzyste na pozostałych $4$ miejscach: $4!=24$.
3. $6\cdot24=144$.

Odpowiedź: $144$

Z powtórzeniami — na każdej pozycji $10$ cyfr:

$$10^4=10\,000$$

Bez powtórzeń — liczba możliwości maleje o jeden przy każdej kolejnej pozycji:

$$10\cdot9\cdot8\cdot7=5040$$

Obserwacja: zakaz powtórzeń zmniejsza liczbę kodów prawie o połowę.

Odpowiedź: $10\,000$ oraz $5040$.

Krok 1 — sprawdzamy kolejne silnie:

$$1!=1,\quad 2!=2,\quad 3!=6$$

Krok 2 — wniosek:

$$n=3$$

Odpowiedź: $n=3$.

To permutacja sześciu elementów:

$$6!=6\cdot5\cdot4\cdot3\cdot2\cdot1=720$$

Odpowiedź: $720$ sposobów.

Krok 1 — sklejamy $3$ matematyczne w blok. Mamy $3$ obiekty (blok + $2$ fizyczne):

$$3!=6$$

Krok 2 — wewnątrz bloku $3$ książki:

$$3!=6$$

Krok 3 — mnożymy:

$$6\cdot6=36$$

Odpowiedź: $36$ sposobów.

Zestawienie wzorów:

• $n!$ — permutacje (ustawienia wszystkich elementów)
• $n^k$ — wariacje z powtórzeniami
• $\frac{n!}{(n-k)!}$ — wariacje bez powtórzeń
• $\frac{n!}{k!(n-k)!}$ — kombinacje (kolejność nieistotna)

Odpowiedź: B. $n^k$.

$$6!=720$$

Odpowiedź: C. $720$.

Litery mają być różne, a kolejność ma znaczenie:

$$26\cdot25\cdot24=15\,600$$

Dla porównania: gdyby litery mogły się powtarzać, byłoby $26^3=17\,576$.

Odpowiedź: $15\,600$.

Krok 1 — pierwsza pozycja jest ustalona. Zostaje ustawienie pozostałych $4$ osób:

$$4!=24$$

Odpowiedź: $24$ sposoby.

Skracamy $6!$ w liczniku i mianowniku:

$$\frac{8\cdot7\cdot6!}{6!\cdot2}=\frac{56}{2}=28$$

Uwaga: to wzór na kombinacje — wybór $2$ elementów z $8$ bez uwzględniania kolejności.

Odpowiedź: A. $28$.

$$3!\cdot2!=6\cdot2=12$$

Odpowiedź: A. $12$.

Krok 1 — wszystkie ustawienia:

$$4!=24$$

Krok 2 — odrzucamy te zaczynające się od zera. Jeśli zero stoi na pierwszym miejscu, pozostałe trzy cyfry można ustawić na:

$$3!=6\ \text{sposobów}$$

Takie zapisy nie są liczbami czterocyfrowymi.

Krok 3 — odejmujemy:

$$24-6=18$$

Kontrola inną drogą. Na pierwsze miejsce mamy $3$ możliwości (bez zera), a pozostałe trzy pozycje wypełniamy dowolnie: $3\cdot3!=3\cdot6=18$ ✔

Odpowiedź: $18$ liczb.

Krok 1 — powtarzające się litery. Wyraz MAMA ma $4$ litery, ale $M$ powtarza się $2$ razy i $A$ powtarza się $2$ razy.

Krok 2 — permutacje z powtórzeniami:

$$\frac{4!}{2!\cdot2!}=\frac{24}{2\cdot2}=6$$

Krok 3 — sprawdzenie przez wypisanie: MAMA, MAAM, MMAA, AMMA, AMAM, AAMM — sześć układów.

Dlaczego dzielimy. Zwykłe $4!$ liczyłoby zamiany jednakowych liter jako różne układy. Dzielenie przez $2!\cdot2!$ usuwa te powtórzenia.

Odpowiedź: $6$.

Krok 1 — sklejamy parę. Traktujemy dwie osoby jako jeden blok. Zamiast $5$ obiektów mamy teraz $4$:

$$4!=24\ \text{ustawień}$$

Krok 2 — wnętrze bloku. Te dwie osoby mogą stać w dwóch kolejnościach:

$$2!=2$$

Krok 3 — mnożymy:

$$24\cdot2=48$$

Kontrola sensu: wszystkich ustawień pięciu osób jest $120$, a nasz wynik to $48$ — mniej, czyli warunek faktycznie ograniczył możliwości ✔ Stanowi to $\frac{48}{120}=40\%$ wszystkich ustawień.

Odpowiedź: $48$ sposobów.

Krok 1 — problem permutacji cyklicznych. Przy okrągłym stole ustawienia różniące się obrotem są identyczne.

Krok 2 — unieruchamiamy jedną osobę. Sadzamy pierwszą osobę na dowolnym miejscu (to ustala „punkt odniesienia"), a pozostałe $3$ ustawiamy względem niej:

$$3!=6$$

Wzór ogólny. Liczba permutacji cyklicznych $n$ osób to $(n-1)!$ — dzielimy $n!$ przez $n$ możliwych obrotów.

Odpowiedź: $6$ sposobów.

Krok 1 — cyfry nieparzyste: $1$, $3$, $5$, $7$, $9$ — jest ich $5$.

Krok 2 — z powtórzeniami. Na każdej z trzech pozycji mamy $5$ możliwości (zero nie należy do zbioru, więc pierwsza cyfra nie sprawia kłopotu):

$$5^3=125$$

Krok 3 — bez powtórzeń:

$$5\cdot4\cdot3=60$$

Odpowiedź: $125$ liczb, w tym $60$ o różnych cyfrach.

Krok 1 — upraszczamy lewą stronę:

$$\frac{(n+2)!}{n!}=(n+2)(n+1)$$

Krok 2 — równanie:

$$(n+2)(n+1)=30$$

Krok 3 — szukamy dwóch kolejnych liczb o iloczynie $30$. To $5$ i $6$:

$$n+1=5 \quad\Rightarrow\quad n=4$$

Krok 4 — sprawdzenie dziedziny. Silnia wymaga $n\ge0$, więc $n=4$ jest poprawne (drugie rozwiązanie równania kwadratowego byłoby ujemne i odpada).

Sprawdzenie: $\frac{6!}{4!}=6\cdot5=30$ ✔

Odpowiedź: $n=4$.

Z uwzględnieniem kolejności (wariacje bez powtórzeń):

$$52\cdot51\cdot50=132\,600$$

Bez uwzględniania kolejności (kombinacje). Każdy zestaw trzech kart policzyliśmy powyżej $3!=6$ razy — raz dla każdej kolejności:

$$\frac{132\,600}{6}=22\,100$$

Kluczowa różnica. Gdy rozdajemy karty na rękę, kolejność nie ma znaczenia — liczy się skład. Gdy jednak przypisujemy kartom role (pierwsza odkryta, druga, trzecia), kolejność się liczy.

Zapis wzorem: $\binom{52}{3}=\frac{52!}{3!\cdot49!}=22\,100$.

Odpowiedź: $132\,600$ z kolejnością, $22\,100$ bez.

Krok 1 — budujemy ustawienie pozycja po pozycji. Ustawiamy $n$ różnych elementów w rzędzie.

Krok 2 — zliczamy możliwości na kolejnych miejscach:

• na pierwsze miejsce — $n$ elementów do wyboru,
• na drugie — $n-1$ (jeden już użyty),
• na trzecie — $n-2$,
• …, na ostatnie — $1$.

Krok 3 — reguła mnożenia. Wybory są niezależne, więc mnożymy:

$$n\cdot(n-1)\cdot(n-2)\cdot\ldots\cdot2\cdot1=n! \qquad ∎$$

Sprawdzenie dla $n=3$: $3!=6$, a wypisanie ABC, ACB, BAC, BCA, CAB, CBA daje sześć układów ✔