aggiustiamo il tiro e nuova sorpresa
Ho iniziato semplificando il problema usando un dado con solo due facce (una moneta con facce T e C).
Ho deciso, fissato k, di contare nell'insieme delle serie di n lanci quante presentano al massimo k facce ripetute. (in termini di persone e camere, ci sono n persone da sistemare in due camere T e C ognuna con k letti)
Esempi:
se k=1, n può valere al massimo 2 (altrimenti una faccia deve ripetersi almeno due volte); se n=1 ho 2 serie buone (T e C), se n=2 ho ancora 2 serie buone (TC e CT) su 4 possibili (perché TT e CC hanno due ripetizioni)
se k=2, n può valere al massimo 4 (altrimenti una faccia deve ripetersi 3 volte); per n=1 ho 2 serie buone, per n=2 ne ho 4 (perché TT e CC ora sono buone), per n=3 dal totale di 8=23 devo scartare TTT e CCC e me ne restano 6, per n=4 invece di ragionare scartando posso ricorrere alle mie note permutazioni con ripetizione, perché devo avere per forza due T e due C da rimescolare e quindi viene 4!/(2!*2!)=6
se k=3, n può valere al massimo 6 e i calcoli sono ancora ragionevoli: variando n da 1 a 6 vengono questi numeri 2 4 8 14 20 20
Aumentando k i calcoli cominciano ad intricarsi e allora ho deciso di rivolgermi di nuovo all'oracolo OEIS dandogli in pasto l'ultima serie di numeri. Anche questa volta, miracolo! la serie appartiene a A172021 . Qui le spiegazioni apparivano un po' più criptiche, perché non conoscevo bene il significato di alcune sigle o termini come la trasformata binomiale di 1^n, e non riuscivo a capire come passare al caso di 3 o più facce. Ho notato però un riferimento alle funzioni generatrici, benché quella riportata non mi fosse ben chiara, accanto al nome di chi l'ha proposta, Geoffrey Critzer: sono andato a leggere il suo profilo e, visto che si tratta di un docente di scuola superiore con interesse per le funzioni generatrici, ho pensato di scrivergli per aiuto. Questa è la mail che gli ho mandato:
Dear Geoffrey,
I am an italian retired high school Math teacher, with no experience in combinatorics.
Playing with words I met this problem:Count the words of length N formed with two letters each occurring at most K times in the word
I found that sequence A172021 gives the correct answer.
The question is: if we use more letters is there some way to calculate the number of words? I was amazed by the triangle generating sequence A172021 and wonder if something analog exists for 3 or more letters.
If you have any idea I would be grateful to know.
Due giorni dopo è arrivata la gentile risposta, mentre nel frattempo io calcolavo con fatica alcune righe per il caso di 3 facce:
I am a high school math teacher. I have no formal education in combinatorics but I have been highly engaged in self study for about 6 years.
Playing with words I met this problem:
Count the words of length N formed with two letters each occurring at most K times in the word.
Your description here of this problem is equivalent to (but much better) than my comment in A172021. I think it would be a welcome addition as an equivalent comment. Be aware that the index n marks the rows of the triangle while k marks the columns. So something like: Equivalently the number length k words on {0,1} with at most n occurences of each letter.
I found that sequence A172021 gives the correct answer.
The question is: if we use more letters is there some way to calculate the number of words?
For the number of length k words on {0,1,2} with at most n occurrences of each letter
n>=0, 0<=k<=3n we have
1
1, 3, 6, 6
1, 3, 9, 24, 54, 90, 90
1, 3, 9, 27, 78, 210, 510, 1050, 1680, 1680
The e.g.f. for row n is ( 1 + x + x^2/2! + ... + x^n/n!) ^3
I was amazed by the triangle generating sequence A172021 and wonder if something analog exists for 3 or more letters.
For such words on a larger alphabet we merely change the exponent in the e.g.f. I am continuously amazed at how efficiently generating functions can answer combinatorial questions.
If you have any idea I would be grateful to know.
Thanks for your inquiry. I think you should add an appropriate comment to A172021 and submit a new sequence giving the triangular array for such words on {0,1,2}.
I numeri per il caso di tre facce erano uguali ai miei, calcolati con fatica, ma non capivo come uscissero da quella funzione generatrice con i denominatori. All'inizio pensai che andassero eliminati mediante denominatore comune, ma niente. Finché rimuginando sulla sigla e.g.f. mi resi conto che poteva significare exponential generating function e cercando in rete alla fine capii che per avere i numeri corretti bisognava, dopo aver sviluppato la potenza, moltiplicare ogni coefficiente per il fattoriale dell'esponente della x. Provai con Derive, e come per miracolo la formula sputava facilmente i numeri che faticosamente avevo raccolto. Troppo bello! Incredibile che una formula così semplice risolvesse un problema così complicato.
Finalmente avevo una formula valida per tutti i valori. Ora non restava che completare l'opera mettendo insieme i pezzi e creare un foglio di calcolo per qualche CAS.
Versione stampabile
Menu
Home
Utenti: 362
