XLII OM - III - Zadanie 2

Niech $ X $ będzie zbiorem punktów płaszczyzny $ (x.y) $ o obydwu współrzędnych całkowitych. Drogą długości $ n $ nazywamy każdy taki ciąg $ (P_0, P_1,\ldots, P_n) $ punktów zbioru $ X $, że $ |P_{i-1}P_{i}|=1 $ dla $ i \in \{1,2,\ldots,n\} $. Niech $ F(n) $ będzie liczbą różnych dróg $ (P_0,P_1,\ldots,P_n) $ o początku $ P_0 = (0,0) $ i końcu $ P_n $ położonym na prostej o równaniu $ y = 0 $. Udowodnić, że

\[<br />
F(n) = \binom{2n}{n}.<br />
\]

Rozwiązanie

Dowolnej drodze długości $ n $, o początku $ P_0 = (0,0) $, przyporządkujemy ciąg $ 2n $ symboli, z których każdy jest zerem lub jedynką. Czynimy to w sposób następujący. Jeżeli droga ma postać $ (P_0,P_1,\ldots,P_n) $, to odpowiadający jej ciąg zero-jedynkowy

\[<br />
(c_1,c_2,\ldots,c_{2n-1} ,c_{2n}),<br />
\]

zwany kodem tej drogi, określamy zespołem reguł:

\[<br />
\begin{array}{lcll}<br />
\textrm{jeśli} & \overrightarrow{P_{j-1}P_j} = [ 1,0], & \textrm{to} & c_{2j-1} = 1, c_{2j} = 0;\\<br />
\textrm{jeśli} & \overrightarrow{P_{j-1}P_j} = [ 0,1], & \textrm{to} & c_{2j-1} = 1, c_{2j} = 1;\\<br />
\textrm{jeśli} & \overrightarrow{P_{j-1}P_j} = [-1,0], & \textrm{to} & c_{2j-1} = 0, c_{2j} = 1;\\<br />
\textrm{jeśli} & \overrightarrow{P_{j-1}P_j} = [0,-1], & \textrm{to} & c_{2j-1} = 0, c_{2j} = 0.<br />
\end{array}<br />
\]

Mówiąc obrazowo: krok w prawo kodujemy przy pomocy pary $ 10 $; krok w górę: $ 11 $; krok w lewo: $ 01 $; krok w dół: $ 00 $.

Na odwrót: każdy ciąg zero-jedynkowy długości $ 2n $ wyznacza drogę, której jest kodem.

Różnym drogom odpowiadają różne ciągi zero-jedynkowe; kodowanie jest wzajemnie jednoznaczne.

Zauważmy teraz, że jeżeli punkt $ P_n $, koniec drogi, leży na prostej o równaniu $ y = k $, to znaczy, że wykonaliśmy $ g $ kroków w górę i $ d $ kroków w dół, gdzie $ g $ i $ d $ są liczbami o różnicy $ g - d = k $. Pozostałe ruchy (w liczbie $ n-g-d $) były poziome, i jest bez znaczenia, które z nich wykonaliśmy w prawo, a które w lewo.

Liczba jedynek w kodzie takiej drogi wynosi

\[<br />
2g + (n-g-d) = n + g-d = n + k.<br />
\]

A zatem kodami dróg kończących się na prostej $ y = 0 $ są ciągi złożone dokładnie z $ n $ jedynek i $ n $ zer. Numery miejsc, na których występują jedynki, mogą tworzyć dowolny $ n $-elementowy podzbiór zbioru $ \{1,2,\ldots,2n\} $. Liczba takich podzbiorów wynosi $ \binom{2n}{n} $. Tyle jest więc i dróg długości $ n $ o końcu położonym na prostej $ y = 0 $.

Komentarze

Dodaj nową odpowiedź