Ilość liczb z niemalejącym ciągiem cyfr

[vtvs]

Ile jest liczb n-cyfrowych takich, że cyfry są ustawione w niemalejącym porządku?

[Crizz]

Rozumiem, że dopuszczamy początkowe zera? Jeśli tak, to jest ich tyle, ile n-elementowych kombinacji z powtórzeniami zbioru k-elementowego, gdzie \(\displaystyle{ k}\) to ilość cyfr w danym systemie liczbowym. Zastanów się, dlaczego.

Jeśli nie dopuszczamy początkowych zer, to istnieje prosty sposób na "poprawienie" powyższej metody. Jeśli dobrze się zastanowisz, dlaczego odpowiedź na to pytanie jest taka, jak powyżej, to wpadniesz na to, jak zrobić poprawkę .

[vtvs]

Dzięki, chyba skapowałem.

Wydaje mi się, że nie uwzględniamy liczb zaczynających się od zera. Czy w takim wypadku odpowiedzią będzie \(\displaystyle{ {{n+9}\choose 9}-{{n-1+9}\choose 9}}\) (ilość wszystkich możliwości minus opcja z początkowym zerem)?

[Crizz]

A opcja z początkowymi dwoma, trzema, ..., \(\displaystyle{ n}\) zerami? Rozumiem, że chcesz jako pierwszej cyfry nie mieć zera, ale Twój wzór i tak uwzględnia możliwość wylosowania zer (a liczba ma mieć cyfry w niemalejącym porządku).

Dam w takim razie dużą podpowiedź: załóżmy, ze w ogóle uwzględniamy zero jako możliwą cyfrę takiej liczby. Wylosowaliśmy konkretny multizbiór, w którym są jakieś zera. Gdzie musimy je postawić?

[vtvs]

Hmm, czyli rozumiem, że zer w ogóle nie mogę używać, bo musiałyby stać na początku, ale to wykluczamy, zgadza się? Czyli mamy do wyboru tylko 9 cyfr: od 1 do 9.

Czyli odpowiedzią jest:
\(\displaystyle{ {n+8 \choose 8}}\)?

[Crizz]

Zgadza się.