Liczba ciągów monotonicznych utworzonych ze zbioru liczb

[U238]

Jest dany zbiór \(\displaystyle{ A= \left\{ 1,2,3,4,5,6,7\right\}}\). Losujemy trzy liczby bez zwracania. Ile jest takich zdarzeń, że wylosowane liczby dadzą ciąg monotoniczny?
Już wiem, że może to być jedynie ciąg rosnący i malejący, gdyż losuje się bez zwracania, czyli liczby nie mogą się powtórzyć. W odpowiedziach jest, że \(\displaystyle{ 70}\). Da się to jakoś szybciej policzyć niż wypisując kolejne trójki?

[Premislav]

Pewnie da się to sprytniej policzyć, ale ja jestem do bani z kombinatoryki. Drugim wyrazem ciągu musi być jedna z liczb \(\displaystyle{ 2,3,4,5,6}\). Gdy drugim wyrazem ciągu jest \(\displaystyle{ i\in\left\{ 2,3,4,5,6\right\}}\), to mamy \(\displaystyle{ (i-1)(7-i)}\) ciągów rosnących i tyle samo malejących, tak więc łącznie jest ich
\(\displaystyle{ \sum_{i=2}^{6}2(i-1)(7-i)= \sum_{i=2}^{6}\left(-14+16i -2i^2\right)=\\=-70+16 \sum_{i=2}^{6}i-2 \sum_{i=2}^{6}i^2=-84+16 \sum_{i=1}^{6}i-2 \sum_{i=1}^{6}i^2=\\=-84+16\cdot 21-13\cdot 14=70}\)
Skorzystałem ze wzorów
\(\displaystyle{ \sum_{i=1}^{n}i=\frac{n(n+1)}{2}, \ \sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}}\)
dla \(\displaystyle{ n=6}\).

[Slup]

Wybierasz zatem trzy różne liczby ze zbioru \(\displaystyle{ A}\). Takich wyborów jest

\(\displaystyle{ {70 \choose 3} = 35}\)

Każde trzy różne liczby ze zbioru \(\displaystyle{ A}\) możesz na dwa sposoby ustawić w ciąg monotoniczny: w ciąg rosnący albo w ciąg malejący. Zatem wszystkich takich ciągów jest

\(\displaystyle{ 35 \cdot 2 = 70}\)

[U238]

To jest tylko część zadania maturalnego, zatem nie znam wzorów na sumowanie.

[Premislav]

No to Slup pokazał, jak to prosto i ładnie zrobić, ja nawet ze sprawdzianu z kombinatoryki w liceum dostałem kiedyś \(\displaystyle{ 4}\).

[Janusz Tracz]

Pewnie da się to sprytniej policzyć, ale ja jestem do bani z kombinatoryki.

Choć kiedyś sam wpadłeś na pomysł nawet ogólniejszy KLIK. Numeracja "książek" z linku będzie odpowiadać tworzeniu ciągów monotonicznych.

[U238]

Ale tam skąd to 70 nad 3? Nie rozumiem.

Nie rozumiem też, czemu ten dział tak trudno mi idzie. Byle tylko nie dali na maturze zadania optymalizacyjnego, w którym trzeba przedstawić pewne prawdopodobieństwo za pomocą zmiennej x i wyznaczyć coś tam.

[Slup]

Powinno być

\(\displaystyle{ {7 \choose 3} = 35}\)

Moja pomyłka. Chodzi o to, że tyle jest trójelementowych podzbiorów zbioru \(\displaystyle{ A}\).

[U238]

Ale skąd wiadomo, czy spośród tych trzech liczb utworzy się ciąg monotoniczny?

[MrCommando]

A czy trzy różne liczby z tego zbioru mogą być takie, że nie da się z nich ułożyć ciągu monotonicznego? Przecież można je posortować od najmniej do największej. Stąd dla każdych trzech liczb są dwie możliwości (rosnąco albo malejąco).

[U238]

A np. 132?

[piasek101]

Wybierasz trzy liczby - jest takich możliwych trójek \(\displaystyle{ 35}\).
Weź jedną z nich np 123 i ułóż wszystkie ciągi - zobacz ile jest monotonicznych.

[MrCommando]

A np. 132?

No z takich liczb masz \(\displaystyle{ 1,2,3}\) - rosnący oraz \(\displaystyle{ 3,2,1}\) - malejący.

[U238]

No tak, ale mi chodzi o to, że jak jest 7 nad 3, to wybieram z 7 liczb trzy dowolne. Czyli mogę wybrać 1,3,2 i to jest jeden ciąg. Ale mogę też wybrać 1,2,3 i to już inny ciąg jest.

[MrCommando]

Nie, bez sensu. Liczba \(\displaystyle{ \binom{7}{3}}\) to liczba \(\displaystyle{ 3}\)-elementowych podzbiorów zbioru \(\displaystyle{ 7}\)-elementowego. Dlatego kolejność nie ma znaczenia i zliczając w ten sposób nie odróżniamy od siebie wyników \(\displaystyle{ (1, 2, 3)}\), \(\displaystyle{ (3,2,1)}\), \(\displaystyle{ (1,3,2)}\), \(\displaystyle{ (1,2,3)}\), \(\displaystyle{ (2,3,1)}\), \(\displaystyle{ (2,1,3)}\).