KombinatorykaWyzwanieZadanie nr 3854
Niemalejące ciągi długości 10 o wyrazach z {1, …, 12}, w których aᵢ ≠ i dla każdego i
Ile jest ciągów niemalejących \((a_1,a_2,\ldots,a_{10})\) liczb całkowitych ze zbioru \(\{1,2,\ldots,12\}\), w których \(a_i\ne i\) dla każdego \(i=1,2,\ldots,10\)?
Świetnie.
Jak rozwiązać to zadanie?
Potrzebujesz pomocy? Pokaż wskazówkę
Najpierw udowodnij, że aᵢ > i dla każdego i. Potem przekształć ciąg w ścieżkę kratową i zastosuj zasadę odbicia.
Chcesz poznać sposób? Rozwiązanie krok po kroku
- Z \(a_1\ge1\) i \(a_1\ne1\) mamy \(a_1\ge2\). Jeśli \(a_i\ge i+1\), to \(a_{i+1}\ge a_i\ge i+1\) i \(a_{i+1}\ne i+1\), więc \(a_{i+1}\ge i+2\). Zatem warunek jest równoważny nierównościom \(i+1\le a_i\le12\).
- Połóżmy \(c_i=13-a_{11-i}\) dla \(i=1,\ldots,10\). Jest to bijekcja na ciągi niemalejące z \(1\le c_i\le i+1\). Dopisując na początku \(1\), dostajemy ciągi niemalejące \(1\le d_1\le\ldots\le d_{11}\) z \(d_j\le j\) (i \(d_1=1\) automatycznie).
- Ciągowi \((d_j)\) przypisujemy ścieżkę kratową z \((0,0)\) do \((11,11)\) o krokach \(E=(1,0)\), \(N=(0,1)\), w której \(j\)-ty krok \(E\) wykonujemy na wysokości \(d_j-1\). Warunek \(d_j\le j\) oznacza, że ścieżka nigdy nie wchodzi nad przekątną \(y=x\); jest to bijekcja.
- Ścieżek wszystkich jest \(\binom{22}{11}\). Ścieżka zła dotyka prostej \(y=x+1\); odbijając jej początek do pierwszego takiego punktu względem tej prostej, dostajemy bijekcję ze ścieżkami z \((-1,1)\) do \((11,11)\), których jest \(\binom{22}{10}\).
- Wynik: \(\binom{22}{11}-\binom{22}{10}=\frac{1}{12}\binom{22}{11}=\frac{705432}{12}=58786\) (liczba Catalana \(C_{11}\)). Odpowiedź: \(58786\).
Odpowiedź: \(58786\)
Czego warto się nauczyć?
Kombinatoryka to sztuka liczenia bez wypisywania wszystkiego. Najważniejsze jest rozbicie problemu na etapy.
Podobne zadania
- Permutacje liczb od 1 do 8 o naprzemiennie rosnących i malejących wyrazach
- Liczby od 1 do 11 na okręgu i iloczyny liczb stojących co drugie miejsce
- Największa rodzina parami przecinających się 4-elementowych podzbiorów zbioru {1, …, 12}
- Pary z 20-elementowego zbioru liczb o średniej nie mniejszej niż średnia całego zbioru