ciągi rosnące ze zbioru n elementów

[wielkireturner]

Układamy \(\displaystyle{ 3}\)-elementowe ciągi rosnące (bez powtórzeń) ze zbioru \(\displaystyle{ n}\) liczb. Czy wówczas liczba ciągów rosnących to \(\displaystyle{ {n \choose 3}}\), jeśli nie, to dlaczego i jaka jest prawidłowa odpowiedź, jeśli tak, to również dlaczego?

[Zahion]

Symbol \(\displaystyle{ {n \choose k}}\) określa też coś w kombinatoryce - co ? Wypisz sobie kilka takich zbiorów i sprawdz dlaczego zachodzi owa równość.

[a4karo]

Na ile sposobów możesz wybrać zbiór trzyelementowy? Ile ciągów rosnących można z tych trzech elementów ułożyć?

[wielkireturner]

Zbiór trzyelementowy mogę wybrać na \(\displaystyle{ {n \choose 3}}\) sposobów ze zbioru \(\displaystyle{ n}\)-elementowego, więc wydawałoby się, że liczba ciągów rosnących będzie mniejsza od liczby wszystkich ciągów trzyelementowych, które można wybrać.

[a4karo]

A konkretnie ile ich będzie?

[wielkireturner]

A konkretnie ile ich będzie?

\(\displaystyle{ \sum_{i=1}^{n-1} \frac{(n-i)(n-i-1)}{2}}\)?

[a4karo]

Ile ciągów rosnących zrobisz że zbioru 4,7,2?
A ile z 9,0,1?

[wielkireturner]

Ile ciągów rosnących zrobisz że zbioru 4,7,2?
A ile z 9,0,1?

Za każdym razem \(\displaystyle{ 1}\). I moja suma zgadza się z oboma przypadkami.

[a4karo]

Czekaj, najpierw napisz wyrażnie co oznacza Twoja suma. Mam wrażenie,że wyjąłes ją z kontekstu.-- 23 gru 2015, o 21:11 --I przede wszystkim musisz ten wzór UDOWODNIĆ (a nie go napisać)

[wielkireturner]

Ale chyba rozumiem, czemu \(\displaystyle{ {n \choose 3}}\). W kombinacjach kolejność elementów nie ma znaczenia, stąd każdą daną kombinację możemy ułożyć w ciąg rosnący, dlatego wszystkich ciągów rosnących będzie \(\displaystyle{ {n \choose 3}}\)
Co do sumy, to obliczyłem ją tak, że zbiór \(\displaystyle{ n}\) liczb sprowadziłem do zbioru \(\displaystyle{ \left\{ 1,2,3, ..., n \right\}}\) bez straty ogólności i następnie zakładałem, że wybieram któryś z elementów jako pierwszy element tego ciągu, np. 1. Wówczas mogłem wybrać \(\displaystyle{ n-2}\) miejsc na drugi wyraz i w konsekwencji dla miejsca \(\displaystyle{ 2}\) miałem \(\displaystyle{ n-2}\) miejsc, dla miejsca \(\displaystyle{ 3}\) miałem \(\displaystyle{ n-3}\) miejsc dla trzeciego wyrazu ciągu, itd. stąd suma możliwości dla pierwszego wyrazu ciągu z \(\displaystyle{ 1}\) była równa \(\displaystyle{ \frac{(n-1)(n-2)}{2}}\), dalej zakładałem, że pierwszym ciągu jest \(\displaystyle{ 2,3,4,}\) itd. i stąd otrzymałem taką sumę jak ww.

[Zahion]

Zbiór trzyelementowy mogę wybrać na \(\displaystyle{ {n \choose 3}}\) sposobów ze zbioru n-elementowego

Ja osobiście zawsze na to spoglądałem w ten sposób :
Wezmy dowolny taki zbiór trzyelementowy, tj. \(\displaystyle{ A = \left\{ x_{1}, x_{2}, x_{3}\right\}}\).
Zauważmy, że \(\displaystyle{ \left\{ x_{1}, x_{2}, x_{3}\right\} = \left\{ x_{p}, x_{q}, x_{r}\right\}}\), gdzie \(\displaystyle{ p, q, r}\) to permutacja liczb \(\displaystyle{ 1, 2, 3}\). Dowolny ciąg, jaki otrzymamy, przykładowo \(\displaystyle{ \left\{ 2, 1, 3 \right\}}\) jest równoważny ciągowi \(\displaystyle{ \left\{ 2, 1, 3 \right\} = \left\{ 1, 2, 3\right\}}\), co oznacza, że z każdego takiego ciągu możemy tak ułożyć wyrazy, aby był on rosnący, czyli to wszystkie takie ciągi. ( Zapis uproszczony, Mój swiatopogląd. )

[a4karo]

Ale chyba rozumiem, czemu \(\displaystyle{ {n \choose 3}}\). W kombinacjach kolejność elementów nie ma znaczenia, stąd każdą daną kombinację możemy ułożyć w ciąg rosnący, dlatego wszystkich ciągów rosnących będzie\(\displaystyle{ {n \choose 3}}\)

To jest za słaby argument: z wybranych trzech wyrazów można ułożyć dokładnie jeden ciag rosnący. To daje odpowiedniość 1-1 między trzyelementowymi ppodzbiorami a ciagami rosnacymi.

Tę ideę wyraził również Zahion