numero di numeri ordinati

[pa]

c'e' qualcuno che saprebbe trovare una formula chiusa per dire quanti sono i numeri di n cifre tali che le cifre sono ordinate?
es 1123478 e' un numero ordinato 1213478 no etc...
mi sono dovuto porre questa domanda spesso per calcolare la complessita' di alcuni algoritmi utili nelle oli di informatica ma non ho mai trovato una risposta...
grazie per le risposte!!

[g(n)]

Prima di tutto con una cifra ci sono 9 numeri ordinati. In particolare ce n'è uno per ogni cifra.

Poi: se hai un numero di $ n $ cifre ordinato, allora puoi ottenere un numero di $ n+1 $ cifre ordinato aggiungendo all'inizio una cifra minore o uguale alla prima.
Quindi per trovare i numeri ordinati di due cifre prendi 1 e ci puoi aggiungere prima solo un altro uno. Poi prendi il 2 e ci puoi aggiungere 1 o 2, e così via (quindi con 2 cifre hai 1+2+..+9=45 numeri ordinati, e in particolare uno che inizia per 9, due che iniziano per 8 ecc.)

Facendo così dovresti ottenere tutti e soli i numeri ordinati. Che si ottengano solo numeri ordinati è facile da vedere. Che siano tutti forse un po' meno ma penso si possa fare così: prendi il minimo numero ordinato $ m $ che con il mio metodo non becco (che deve avere almeno due cifre perchè quelli ad una cifra sappiamo che sono tutti e soli). Adesso togli la prima cifra, e quello che rimane è ancora ordinato, però neanche lui lo devo beccare con il mio metodo, perchè altrimenti a partire da questo potrei ottenere $ m $ anteponendogli una cifra. Questo però contraddice la minimalità di $ m $.

Detto questo bisogna trovare un modo di contare quanti sono. Se usi il triangolo di Tartaglia non è difficile vedere che sono $ \binom{n+8}8 $, e lo si potrebbe dimostrare rigorosamente per induzione.
Se hai domande non hai che da chiedere!

Ciao

[Tibor Gallai]

Cesenatico 2001, problema 4.

[pa]

ok grazie mille mi siete stati molto di aiuto!