primi passi e prima sorpresa

L'idea base per il mio calcolo fu questa:

quante sono le sequenze che al passo n presentano un valore ripetuto k volte e gli altri ripetuti meno volte ? Se dovessimo simulare le sequenze con lanci casuali, fissato un k, dovremmo fare lanci finché una delle facce esce k volte: il conto che voglio fare è quante possibili sequenze si fermano al lancio n.

Esempio: con k=3 e n=9 : mettiamo che al nono lancio esca il terzo 6; vuol dire che prima ne sono usciti altri due e che gli altri numeri sono usciti meno di 3 volte ciascuno. Concentrando l'attenzione sui restanti 5 numeri, mi resta da calcolare il numero di sequenze di sei numeri in cui nessuna delle cinque facce rimaste compare più di due volte.

Un po' per distrazione un po' per inesperienza, presi una strada che poi scoprii errata, però fu quasi una fortuna: infatti mi dimenticai che le sequenze sono ordinate e pensai di descrivere ogni sequenza con una cinquina di valori indicanti quante volte ogni faccia compariva, con la clausola che tali valori potevano essere solo 0 1 2 e che la loro somma doveva essere 6. Nella prossima tabella alcuni esempi:

facce	1	2	3	4	5
	2	0	0	2	2
	1	1	1	2	1
	0	2	1	2	1
	0	0	2	2	2

in cui la prima riga si legge così: l'1 c'è due volte, il 4 anche e il 5 pure; invece la seconda riga dice che l'1 il 2 il 3 e il 5 ci sono una volta e il 4 due volte; ecc.

Il problema si poteva così riformulare (e mi piaceva anche di più): quanti sono i numeri di 5 cifre in base 3 tali che la somma delle cifre sia 6? (si contano anche gli zeri iniziali) 

In mancanza di una formula, mi sono messo a contare, variando il valore della somma:
per somma 0, ne viene uno solo 00000
per somma 1, ne vengono 5  10000 01000 00100 00010 00001
per somma 2 la cosa si complica un po', perché posso avere tre 0 e due 1 oppure quattro 0 e un 2: in totale viene 15
per somma 3 viene 30, per somma 4 viene 45, per somma 5 viene 51 e per somma 6 viene 45 e poi si prosegue fino a somma 10 per cui viene 1

I numeri in fila sono 1, 5, 15, 30,45, 51, 45, 30, 15, 5, 1

A me non dicevano niente, però avevo visto qualche anno prima un sito straordinario dove si raccolgono proprio le sequenze di numeri interi che sembrano non dire niente: si intitola On-Line Encyclopedia of Integer Sequences (per gli amici OEIS) e si trova a oeis.org : ho scritto nell'apposita casella i miei primi sei numeri, come suggerito nella guida, e, meraviglia, mi è uscita una pagina ricca di spiegazioni (provare per credere): i miei numeri appartengono alla sequenza A027907 Coefficienti del triangolo trinomiale etc. Già sapere che esiste un triangolo trinomiale (io conoscevo solo quello binomiale di Pascal o Tartaglia) mi metteva curiosità, ma andando avanti c'era anche di meglio, perché dice che i numeri si possono generare mediante le potenze di (1+x+x²), cosa che verificai subito con Derive: infatti (1+x+x²)⁵=1+5x+15x²+30x³+45x⁴+51x⁵+45x⁶+30x⁷+15x⁸+5x⁹+1x¹⁰ . Se non bastasse, tra i riferimenti ci trovai anche un articolo di Eulero che fu il primo a studiare le potenze di questi polinomi, e lo potete leggere qui sia in versione inglese tradotta che in versione latina originale (che onestamente capisco meglio dell'inglese). Naturalmente il triangolo trinomiale ha le sue belle proprietà come quello binomiale, ma ovviamente c'è anche quello quadrinomiale generato dal quadrinomio e calcola il numero di sequenze formate da 0,1,2,3 (base 4) e così via. Il polinomio con le sue potenze fa da funzione generatrice per le righe del triangolo trinomiale. Mi ricordai che tanti anni fa avevo già letto qualcosa sulle funzioni generatrici in quello che per me è rimasto il più bel libro sotto il profilo editoriale: N. VILENKIN - COMBINATORIAL MATHEMATICS FOR RECREATION - edito dalle edizioni russe MIR. Adoro il suo formato atipico, le illustrazioni simpatiche, l'impaginazione, i caratteri, e ovviamente anche il contenuto, che non è affatto banale anche se comprensibilissimo. Per chi ha forza e voglia di addentrarsi nel calcolo combinatorio penso che sia un ottimo punto di partenza. Le ultime trenta pagine della teoria (poi ci sono moltissimi esercizi, con soluzioni al seguito) sono dedicate alle funzioni generatrici e sono illuminanti: è trattato anche il nostro caso, dove si fa notare che, siccome i nostri polinomi sono la somma di una progressione geometrica, si possono riscrivere come frazione, e se ne ricava una nuova funzione generatrice compatta che si può vedere nel riassunto di pag. 122 al punto 7.

Giusto quando pensavo di aver fatto tombola, mi sono reso conto che non basta sapere quanti 1 ci sono nella sequenza, ma anche dove sono; e così mi sono ritrovato al punto di partenza, però con qualche conoscenza in più (per esempio ho capito come risolvere questo problemino: quanti sono i numeri minori di un milione per i quali la somma delle cifre è 15?). Per fare un esempio del nuovo problema, nella tabella qui sopra in ogni cella della colonna 2 non dovrei scrivere quante volte si ripete il 2 nella sequenza ma dovrei mettere i numeri che indicano le posizioni in cui si trova il 2. Il problema potrebbe essere così riformulato (con un po' di fantasia): in quanti modi posso sistemare 6 persone in 5 camere ognuna con 2 letti? (le persone sono le posizioni nella sequenza, le camere sono le facce 1 2 3 4 5 e i due letti rappresentano il numero massimo di persone in una camera). Il problema si potrebbe rovesciare (come è tipico della combinatoria) distribuendo le camere alle persone e formulandolo in questo modo: quante sequenze di 6 cifre prese da {1,2,3,4,5} posso formare se ogni cifra può comparire nella sequenza al massimo 2 volte?

Speravo che nel Vilenkin ci fosse la risposta con la sua bella funzione generatrice, ma non l'ho trovata, forse perché non ho guardato bene. E così ho ricominciato da qualche esempio semplice.