KombinatorykaWyzwanieZadanie nr 3880

Permutacje liczb od 1 do 8 o naprzemiennie rosnących i malejących wyrazach

Permutacje naprzemienne Zadania konkursoweZadania olimpijskie

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\)?

+18 pkt za pierwsze rozwiązanie na koncie

Zapis: ułamki (3/4), pierwiastki (2sqrt(3)), pi/6.

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
  1. 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\).
  2. 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.
  3. 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}\).
  4. 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\).
  5. 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.

Więcej zadań z kombinatoryki →

Podobne zadania