Kombinatoryka

[Belf]

Ile jest \(\displaystyle{ n}\)−cyfrowych liczb naturalnych, w których cyfry występują w porządku niemalejącym ?

[Premislav]

Powiedzmy, że w takiej liczbie ma wystąpić \(\displaystyle{ k}\) różnych cyfr, przy czym \(\displaystyle{ k\in \left\{1,2,3,4,5,6,7,8,9\right\}}\) (bo oczywiście nie może się pojawić zero, gdyż musiałoby być na początku, a wtedy nie otrzymamy poprawnej liczby). Na \(\displaystyle{ {9\choose k}}\) sposobów wybieramy \(\displaystyle{ k}\) spośród dziewięciu możliwych cyfr, jakie mają się pojawić w zapisie liczby. Następnie w celu podzielenia na bloki z tymi samymi cyframi możemy spojrzeć na sprawę tak, że jest \(\displaystyle{ n}\) pozycji cyfr, więc mamy między nimi \(\displaystyle{ n-1}\) przerw (między pierwszą a drugą, między drugą a trzecią pozycją i tak dalej). By uzyskać \(\displaystyle{ k}\) bloków cyfr, potrzebujemy wstawić niejako przegródki w \(\displaystyle{ k-1}\) spośród tych \(\displaystyle{ n-1}\) przerw, co możemy uczynić na \(\displaystyle{ {n-1\choose k-1}}\) sposobów. Czyli odpowiedź to
\(\displaystyle{ \sum_{k=1}^{9}{9\choose k}{n-1\choose k-1}}\)
Rzecz jasna, gdy \(\displaystyle{ n<9}\), to niektóre z tych składników będą zerami, ale to w niczym nie przeszkadza.

Czy ja to umiem jakoś zwinąć? Nie umiem i nie wiem, czy warto. No jest to jakiś wielomian ósmego stopnia od zmiennej \(\displaystyle{ n}\), niespecjalnie urokliwy.

[kerajs]

Jak zwykle jestem spóźniony. A mój post miał brzmieć tak:

Sądzę, iż ta ilość to: \(\displaystyle{ \sum_{i=1}^{9}(10-i) {n-2+i-1 \choose i-1} }\)

[FasolkaBernoulliego]

Kurczę, też robiłem równolegle z Wami i mi wyszło \(\displaystyle{ {n + 8 \choose n}}\). Teraz pytanie czy to jest to samo co u Was, czy źle zrobiłem?

[Tmkk]

Kurczę, też robiłem równolegle z Wami i mi wyszło \(\displaystyle{ {n + 8 \choose n}}\). Teraz pytanie czy to jest to samo co u Was, czy źle zrobiłem?

Dobrze zrobiłeś i wychodzi to samo. Wystarczy po prostu wybrać \(\displaystyle{ n}\) liczb ze zbioru \(\displaystyle{ \left\{ 1,2,3,4,5,6,7,8,9\right\} }\) i ustawić je w sposób niemalejący (jest to możliwe na jeden sposób). Czyli takich liczb jest tyle, ile rozwiązań \(\displaystyle{ x_1+x_2+\ldots +x_9 = n}\), gdzie \(\displaystyle{ x_i \ge 0}\) oznacza, ile wybrano liczb równych \(\displaystyle{ i}\).

[FasolkaBernoulliego]

Faktycznie, jakie to proste! Ja robiłem w drugą stronę - rozważałem n+1 miejsc wokół kolejnych cyfr i wstawiałem tam liczby całkowite nieujemne, które mają sumować się do 8 i odpowiadają wielkościom skoku pomiędzy cyfrą poprzednią a następną (nieistniejące cyfry zerowa to 1 a n+1-sza to 9)...

[janusz47]

Aby odpowiedzieć na pytanie zawarte w treści zadania i scharakteryzować liczbę spełniającą warunki zadania, wystarczy odpowiedzieć na pytanie, ile w niej występuje jedynek, dwójek, trójek, ..., dziewiątek.

Dlatego wszystkich takich liczb jest

\(\displaystyle{ C_{(9)}^{n} = {n +9 -1 \choose n} = { n +8 \choose n}. }\)