numero di numeri ordinati

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
pa
Messaggi: 81
Iscritto il: 14 feb 2008, 16:14
Località: Genova

numero di numeri ordinati

Messaggio da pa » 08 ago 2008, 19:51

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... :roll:
grazie per le risposte!! :)
paolo

g(n)
Messaggi: 109
Iscritto il: 14 ott 2007, 19:24
Località: Codroipo, il paese più anagrammato d'Italia

Messaggio da g(n) » 08 ago 2008, 22:36

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
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 09 ago 2008, 01:43

Cesenatico 2001, problema 4.

Avatar utente
pa
Messaggi: 81
Iscritto il: 14 feb 2008, 16:14
Località: Genova

Messaggio da pa » 12 ago 2008, 08:41

ok grazie mille mi siete stati molto di aiuto! :D
paolo

Rispondi