Esercizio matematica discreta..quanti numeri?

[fragor]

Vi propongo questo esercizio a cui non riesco a trovare una soluzione plausibile.

Quanti sono i numeri di 6 cifre nei quali ogni cifra è maggiore o uguale alla successiva? (es. 755420, 555555, 654321)

Credo che il primo passo sia calcolare il numero totale di numeri a 6 cifre. Dato che per la sesta cifra lo 0 non è accettabile avremo 9 cifre per la 6° posizione e 10 cifre per le altre cinque. Cioè 900.000 cifre. Non riesco però a stabilire una regola che divida i numeri accettabili da quelli non accettabili.

Grazie in anticipo,
fragor

[orazioster]

Provai a pensare:
quanti sono i numeri di due cifre in cui la seconda...?
poi: quanti sono
i numeri di tre in cui la terza?

penso (ora sono stanco per verificare) $\sum_{r=1}^9(\sum_{m=1}^r(\sum_{l=1}^m(\sum_{k=1}^l(\sum_{j=1}^k(\sum_{n=1}^j(n+1) +1)+1)+1)+1)$
-qualcosa così, comunque.

il $+1$ ogni
volta è
perchè conti la anche il finale zero, poi il finale $...00$, $...000$...

Ed è interessante provare a calcolare la somma

[Stickelberger]

Sia M = #{ numeri di 6 cifre ai con a6 \ge a5 \ge ... \ge a1}

scrivo a5 = a6 - d1, a4 = a5 -d2, ...., a1 = a2 -d5.

Allora d1, d2, .., d5 sono \ge 0. Se pongo anche d6 = a1, allora

M = #{ (d1,d2,...,d6) con d1,d2,...,d6 \ge 0 e d1 + d2 + ... + d6 < 10} - 1

perche' la somma d1 + d2 + ... + d6 deve essere uguale
alla prima cifra a1 ed e' quindi < 10.
Sottraggo 1 perche' la prima cifra a6 = d1 + d2 + ... + d6 non e' zero
perche' abbiamo a che fare con numeri di 6 cifre.

E quindi

M = #{ (d1,d2,...,d6,d7) con d1,d2,...,d6,d7 \ge 0 e d1 + d2 + ... + d6 + d7 = 9} - 1.

Questo e' un problema standard della matematica discreta. Si ha che

M = coefficiente binomiale (9 + 6 su 6) - 1 = (15 su 6) - 1 = 5004

[Umby2]

Vedi qui