LV OM - I - Zadanie 5

Dla liczb całkowitych dodatnich $ m $, $ n $ niech $ N(m,n) $ oznacza liczbę $ m $-wyrazowych ciągów niemalejących o wyrazach ze zbioru

\[<br /> \{1,2, 3,\ldots,n\}.<br /> \]

Dowieść, że $ N(m, n+1) =N(n, m+1) $.

Rozwiązanie

Dowolnemu ciągowi niemalejącemu $ a_1,a_2,\ldots,a_m $ o wyrazach ze zbioru $ \{1,2,3,\ldots,n+1\} $ przypisujemy ciąg $ b_1, b_2, \ldots, b_n $ określony następująco: dla $ \ell = 1,2,\ldots,n $

\[<br /> (1) \qquad b_\ell = 1+(\textrm{liczba wyrazów ciągu $a_1,a_2,... ,a_m$ mniejszych lub równych $\ell$}).<br /> \]

W ten sposób określony ciąg $ b_1, b_2, ...,b_n $ ma wyrazy ze zbioru $ \{1,2,...,m+1\} $ i jest niemalejący. Ponadto, każdy ciąg niemalejący $ b_1,b_2,... ,b_n $ o wyrazach należących do zbioru $ \{1,2, ...,m+1\} $ można otrzymać za pomocą wzoru (1) z dokładnie jednego ciągu niemalejącego $ a_1 , a_2, ..., a_m $ o wyrazach należących do zbioru $ \{1,2,...,n+1\} $. Istotnie: znając wartości $ b_1,b_2, ...,b_n $ znamy również liczbę $ c_1 = b_1 - 1 $ oraz liczby

\[<br /> c_\ell = b_\ell - b_{\ell -1}\ \textrm{dla}\ \ell = 2,3,\ldots,n.<br /> \]

Liczba $ c_\ell $ dla $ \ell =1,2,\ldots ,n $ jest, na mocy wzoru (1), liczbą wszystkich wyrazów ciągu $ a_1,a_2,... ,a_m $ równych $ \ell $. Z kolei wyrazów ciągu $ a_1, a_2, ..., a_m $ równych $ n+1 $ jest

\[<br /> c_{n+1} = m - (c_1 + c_2 + \ldots + c_n) = m + 1 - b_n.<br /> \]

Ponieważ ciąg $ b_1 ,b_2,\ldots,b_n $ jest niemalejący, $ b_1 \geq 1 $ oraz $ b_n \leq m+1 $, więc wszystkie liczby $ c_1, c_2, ..., c_{n+1} $ są nieujemne. Liczby te wyznaczają zatem jednoznacznie ciąg niemalejący $ a_1, a_2, ...,a_m $ o wyrazach ze zbioru $ \{1,2, ...,n+1\} $.

Wykazaliśmy tym samym, że wzór (1) opisuje wzajemnie jednoznaczną odpowiedniość pomiędzy $ m $-wyrazowymi ciągami niemalejącymi o wyrazach ze zbioru $ \{1,2,... ,n+1\} $, a $ n $-wyrazowymi ciągami niemalejącymi o wyrazach ze zbioru $ \{1,2,...,m+1\} $. Stąd $ N(m,n + 1) = N(n,m + 1) $.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź