$n=k_1+2k_2+3k_3$

[jordan]

Sia $n$ un intero positivo. Trovare in quanti modi si puo' ottenere $n$ come somma (non ordinata) di $1,2,3$.

[Tess]

Ma non era già stato risolto nel forum non troppo tempo fa qui?

[jordan]

Sì, non è che leggo molto in combinatoria; bene, allora risolvete il seguente:

"Siano dati degli interi positivi distinti $a_1,\ldots,a_k$. Trovare una formula asintotica che esprime in quanti modi $n$ si puo' ottenere come somma di $a_1,\ldots,a_k$"

[Drago96]

C'è un modo che non passa per le genaratrici?

Comunque il caso $k=2$ è carino ed elementare... ed infatti è già stato risolto qua

E poi a chi interessa consiglio vivamente il libro generatingfunctionology!

[<enigma>]

C'è un modo che non passa per le genaratrici?

Sì. L'idea è che, prendendo $n$ biglie e $k-1$ sbarre indistinguibili, le puoi permutare in fila in $\binom{n+k-1}{k-1}$ modi; il numero di biglie nel primo blocco è multiplo di $a_1$ una frazione di $1/a_1$ delle volte, quello nel secondo blocco $1/a_2$ eccetera, quindi ti aspetteresti un numero di rappresentazioni pari a $\frac 1 {a_1 a_2 \dots a_k} \binom{n+k-1}{k-1} \sim \frac {n^{k-1}}{(k-1)! a_1 a_2 \dots a_k}$. Esercizio: scrivila per bene rendendo rigorosa l'argomentazione probabilistica.

[<enigma>]

Formulata in un altro modo. Supponi di voler risolvere $ax+by=n$, ovvero $x=(n-by)/a$. Per la coprimalità, $n-by$ sarà multiplo di $a$ circa $1/a$ delle volte, e inoltre $y$ non è più grande di $n/b$, dunque ci aspettiamo $n/ab$ soluzioni; da questo è un attimo passare al caso generale per induzione.