LV OM - I - Zadanie 5

Zawody matematyczne:

LV OM, 2003-2004

Etap:

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

$ \{1,2, 3,\ldots,n\}. $

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$

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

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

$ c_\ell = b_\ell - b_{\ell -1}\ \textrm{dla}\ \ell = 2,3,\ldots,n. $

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

$ c_{n+1} = m - (c_1 + c_2 + \ldots + c_n) = m + 1 - b_n. $

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)$ .