Ile jest różnych ciągów...

tajner · Post autor: **tajner** » 13 mar 2011, o 21:39

Niech A będzie n-elementowym podzbiorem zbioru liczb naturalnych. Ile różnych ciągów \(\displaystyle{ (c_1,...,c_k) (k \le n)}\) o wyrazach z A i takich, że \(\displaystyle{ c_1< ... <c_k}\), a ile takich, że \(\displaystyle{ c_1> ... >c_k}\)?

norwimaj · Post autor: **norwimaj** » 13 mar 2011, o 22:00

Każdy ciąg rosnący możesz skonstruować w taki sposób: wybierasz \(\displaystyle{ k}\) elementów ze zbioru \(\displaystyle{ A}\) i sortujesz te elementy rosnąco. Zatem ciągów jest tyle samo, co podzbiorów \(\displaystyle{ k}\)-elementowych zbioru \(\displaystyle{ A}\). Chyba wystarczająco dużo już napisałem.

tajner · Post autor: **tajner** » 14 mar 2011, o 07:51

Analogicznie z malejącymi?

kristoffwp · Post autor: **kristoffwp** » 14 mar 2011, o 08:51

\(\displaystyle{ {n \choose k}}\), zakładając, że \(\displaystyle{ k}\) jest ustalone. Ale nie wiem, czy tak to rozumieć. Jeżeli nie (do tego się skłaniam, proszę o uwagi), to według mnie otrzymamy:
\(\displaystyle{ {n \choose 1}+ {n \choose 2}+...+{n \choose n}=2^{n}-1}\). Oczywiście z malejącymi jest tak samo.