KombinatorykaWyzwanieZadanie nr 3880
Permutacje liczb od 1 do 8 o naprzemiennie rosnących i malejących wyrazach
Ile jest permutacji \((a_1,a_2,\ldots,a_8)\) zbioru \(\{1,2,\ldots,8\}\), dla których \(a_1<a_2>a_3<a_4>a_5<a_6>a_7<a_8\)?
Świetnie.
Jak rozwiązać to zadanie?
Potrzebujesz pomocy? Pokaż wskazówkę
Niech \(E_n\) oznacza liczbę takich permutacji zbioru \(n\)-elementowego (wzorzec zaczyna się od wzrostu). Zastanów się, gdzie może stać największa liczba i na jakie dwa niezależne fragmenty dzieli ona ciąg. Przyda się też symetria \(a_i\mapsto n+1-a_i\).
Chcesz poznać sposób? Rozwiązanie krok po kroku
- Niech \(E_n\) będzie liczbą permutacji \(n\) liczb o wzorcu \(a_1<a_2>a_3<\ldots\) (naprzemiennym, zaczynającym się od wzrostu); zamiana \(a_i\mapsto n+1-a_i\) pokazuje, że tyle samo jest permutacji o wzorcu \(a_1>a_2<a_3>\ldots\). Przyjmujemy \(E_0=E_1=1\).
- Rozważmy wszystkie permutacje liczb \(1,\ldots,n+1\) (\(n\ge1\)) naprzemienne w którymkolwiek kierunku — jest ich \(2E_{n+1}\). Niech liczba \(n+1\) stoi na pozycji \(k+1\), \(0\le k\le n\). Na prawo od niej stoi \(n-k\) liczb, które (po spadku z \(n+1\)) muszą tworzyć ciąg naprzemienny zaczynający się wzrostem; na lewo — \(k\) liczb, które czytane od strony \(n+1\) (od prawej do lewej) też tworzą ciąg naprzemienny zaczynający się wzrostem.
- Dla ustalonego \(k\) zbiór liczb po lewej wybieramy na \(\binom nk\) sposobów, lewy fragment na \(E_k\), a prawy na \(E_{n-k}\) sposobów; odwrotnie, każdy taki wybór daje permutację naprzemienną (jej kierunek zależy od parzystości \(k\)). Stąd rekurencja \(2E_{n+1}=\sum_{k=0}^{n}\binom nk E_kE_{n-k}\).
- Obliczamy: \(E_2=1\), \(E_3=2\), \(E_4=5\), \(E_5=16\), \(E_6=61\), \(E_7=272\), np. \(2E_8=\sum_{k=0}^{7}\binom7kE_kE_{7-k}=2(272+7\cdot61+21\cdot16+35\cdot10)=2\cdot1385\), bo \(E_2E_5=16\), \(E_3E_4=10\).
- Zatem szukana liczba permutacji to \(E_8=1385\).
Odpowiedź: \(1385\)
Czego warto się nauczyć?
Kombinatoryka to sztuka liczenia bez wypisywania wszystkiego. Najważniejsze jest rozbicie problemu na etapy.
Podobne zadania
- 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}
- Niemalejące ciągi długości 10 o wyrazach z {1, …, 12}, w których aᵢ ≠ i dla każdego i
- Pary z 20-elementowego zbioru liczb o średniej nie mniejszej niż średnia całego zbioru