a + b + c + d = n , contare i modi

[emacoder]

In quandi modi posso scrivere n come somma di 4 interi$( a+b+c+d=n)$ avendo il vincolo che $ 0<=a,b,c,d<=9 $ ?

[Drago96]

Dipende se vuoi contare l'ordine o no... probabilmente no, e allora il modo più sensato è probabilmente quello di andare a casi e tentativi...

[emacoder]

Pensavo ci fosse un metodo pronto, grazie comunque!

[elianto84]

Tentativi? Naaah.
Se quello che ti interessa sono gli elementi di $[0,9]^4$ a somma $n$, questi possono essere contati calcolando il coefficiente di $x^n$ nel prodotto:
$\prod_{j=1}^{4}(1+x+\ldots+x^9)$, ossia il coefficiente di $x^n$ in $\frac{(1-x^{10})^4}{(1-x)^4}$. Ora si dà il caso che:
$$ (1-x^{10})^4 = \sum_{j=0}^{4}\binom{4}{j}(-1)^j x^{10j}, $$
mentre:
$$ (1-x)^{-4} = \sum_{j=0}^{+\infty}\binom{3+j}{3}x^j. $$
Moltiplicando tra di loro le due somme abbiamo che il coefficiente di $x^n$ risulta pari a:
$$ \sum_{j=0}^{+\infty}(-1)^j\binom{4}{j}\binom{3+n-10j}{3}. $$

Consiglio una lettura che, sono pronto a scommettere, molti di voi troveranno stimolante e illuminante: http://www.math.upenn.edu/~wilf/DownldGF.html

[emacoder]

Soluzione elegante quanto complessa ahah

[Drago96]

Tentativi? Naaah.
Se quello che ti interessa sono gli elementi di $[0,9]^4$ a somma $n$, questi possono essere contati calcolando il coefficiente di $x^n$ nel prodotto:
$\prod_{j=1}^{4}(1+x+\ldots+x^9)$

Beh, ma così conti l'ordine!
Infatti è la prima domanda che ho fatto; se va bene contare $(1, 2, 3, 4) $ come cosa distinta da $(4, 3, 2, 1) $ allora quello è sicuramente il modo migliore (non ho aperto il link, se è il libro di Wilf lo consiglio anch'io dal basso della mia inesperienza), altrimenti è un po' un casino -tant'è vero che una formula generale per le partizioni è arrivata dal cielo per mezzo di Ramanujan...

[gpzes]

Salve a tutti,
volevo sottoporre alla vostra attenzione la formula seguente:

$\left( \begin{array}{l}
n + 3\\
\;\;3
\end{array} \right) - 4\left( {\sum\limits_{k = 0}^{n - 10} {\frac{{(k + 2)(k + 1)}}{2}} } \right) + \left\{ \begin{array}{l}
0\quad se\quad 10 > \frac{n}{2}\\
6\quad se\quad 10 \le \frac{n}{2}
\end{array} \right.$

Sarebbe utile verificarla con qualche software (Ovvio invito causa personali difficoltà !!!
Penso sia stessa formula di elianto 84 anche se trovata senza utilizzo di serie formali.
Grazie mille per link al testo di Wilf!!!SUPER libro!!!

[Gottinger95]

@gpzes: proverò a scrivere un programmino e ti dico! Curiosità: come l'hai ottenuta?
Si può fare una cosa simile a quella di elianto ma scegliendo solo quali numeri (con "quante volte") compaiono nella quaterna per fregarcene dell'ordine, ossia
\[ [x^ny^4] f(x,y) = [x^ny^4](1+xy+x^2y^2+x^3y^3)(1+x^2y+x^4y^2 +x^6y^3 + x^8y^4) \ldots (1+x^9y+ \ldots + x^{36}y^4) \]
dove in ogni parentesi il monomio \(x^{nk}y^k\) significa "prendo il numero \(n\) per \(k\) volte". E' la prima volta che mi avventuro in generatrici con due variabili (ma soprattutto è un prodotto stile "partizioni di un numero" che è bruttissimo), perciò non so come andare avanti. Al massimo so ingenously dire che
\[f(x,y) = \prod_{k=1}^9 \frac{1-(yx^k)^4}{1-yx^k} \]
ma qui mi blocco e invoco voi prodi cavalieri for further thoughts.

[gpzes]

Gent.mo Gottinger, grazie per pronto riscontro!!! ad essere onesto qui uso solo carta e penna. In generale non vado a pensare cose molto complicate. L'idea era eliminare da tutte le somme possibili dei quattro numeri le quaterne, con le loro permutazioni, che hanno termini non ammessi dal vincolo!! Es: a= n, b+c+d= n-1 . a=n-1, b+c+d=1 e così via... a= n-k e b+c+d= k , dove n-k >=10. Alla fine arrivo a a=10 e b+c+d=1. Le somme possibili per b+c+d sono coeffbinomiale (k+2 , 2):questo spiega la sommatoria Ripeto ragionamento per le altre tre quantità a,b,c,d e questo spiega il coefficiente 4 ma NON rischio di ripetere combinazioni perchè n-k>k. L'unica complicazione é quando n-k=k=n/2 e si arriva per esempio a a=10 e b+c+d=10 e vi sono quaterne con due zeri e due termini pari a n/2: allora devo compensare il numero totale perchè era stato moltiplicato per 4 e sottratto. Allora aggiungo il termine 0 oppure 6 dipendendo se il vincolo é sopra o sotto la metà di n.
Il termine 6 si trova usando formula principio inclusione-esclusione.
Mi scuso per non usare Latex .

[Gottinger95]

Mi devi perdonare, gzpes, ma non sono sicuro di aver capito bene il tuo discorso! Innanzitutto: per te la quaterna \( (1,3,3,5)\) è uguale alla quaterna \((5,3,1,3)\), oppure le conti come distinte? Poi su certi passaggi mi sa che ti è scappato qualche typo: ad esempio, credo che tu intendessi - nella serie di esempi - contare le quaterne con un "termine proibito", perciò ad esempio con \(a=n, \ldots, 10\) e \(b+c+d = n-a\). "Le somme possibili sono \( \displaystyle \binom{k+2}{2}\)": in che senso le somme possibili? \(b+c+d\) non faceva \(k\) fissato?
Aspetto intanto una risposta per proseguire nel tuo ragionamento!

P.S. Per usare LaTex, basta mettere tra \ ( e \ ) - senza spazio tra \ e ( - quello che vuoi scrivere fico tipo formula. Poi per le istruzioni principali puoi vedere qui (http://it.wikipedia.org/wiki/Aiuto:Form ... atiche_TeX), e se non trovi quello che cerchi spesso basta google

P.S 2: Se le quaterne che hai contato sono ordinate ( quindi \(1,2,3,4\) è diversa da \(4,2,31\) ) puoi usare questo programmino che ho scritto:
http://codepad.org/vpLZenRd
inserendo il valore di \(n\) che ti interessa nella parte in fondo alla pagina, all'altezza di "INSERISCI IL VALORE DI N". Ah, e benvenuto nel forum!

[gpzes]

$

[gpzes]

Gent.mo Gottinger,
grazie veramente per disponibilità, informazioni e programma !!!
In effetti sono stato un po' fumoso nell'esposizione Il programma devo studiarlo perchè non ricordo niente di C !! E sicuramente sono impedito nello scrivere qui.Alla fine finirò per allegare files
Ad ogni modo, sì, considero le quaterne distinte!!! Ho provato programma per n=10 e le restrizioni 0<=a,b,c,d<=9 ma a me vengono 282 possibilità e non 283...

$\left( \begin{align}
& n+3 \\
& \ \ n \\
\end{align} \right)-4\left( \sum\limits_{k=0}^{n-10}{\frac{(k+2)(k+1)}{2}} \right)+$ (+3 se a=b=c=d=n/4) ???????????

Chissà se così ci azzecco!!!

[Gottinger95]

E di che, tranquillo il forum c'è anche per aiutarsi! (comunque puoi darmi del tu, chè io sono piccino)
Per quanto riguarda il nuovo tentativo, ti sconsiglio vivamente di cercare di inseguire la "formula magica" con ragionamenti "probabili": piuttosto rivedi il tuo ragionamento, controllando se c'è proprio un errore di fondo o se magari ti è scappato solo un dettaglio; se c'è un passaggio logico un po' frettoloso, svisceralo e sezionalo finchè non capisci dove sbagli. Il bello della matematica è proprio che se il ragionamento funziona allora deve venir giusto alla fine!
P.S. Potrei aver anche toppato il programma eh! Prova altri casi piccoli (pure a mano) e vedi se c'è un errore stupido tipo 'sempre uno in più'

[gpzes]

Grazie mille ancora!!
stavo guardando manuale di C ++ in internet
ehh si,,stavo cercando alternativa ad uso funzioni generatrici perché se uno non le vede applicate è una tragedia

[Gottinger95]

Coomunque ti do una bella notizia e una brutta: la buona è che per \(n <20\) la tua formula è equivalente a quella di elianto (e l'aggiunta del 6 aggiusta il caso \(n=20\)), mentre la brutta è che per \(n \ge 20\) è sbagliata Infatti la tua somma si può riscrivere come
\[ \binom{n+3}{3} -4\sum_{k=2}^{n-8} \binom{k}{2} = \binom{n+3}{3}-4 \binom{n-7}{3}\]
D'altronde la somma di elianto, ricordandosi che \( \binom{n}{k} = 0\) se \(n< k\), è
\[ \sum_{j=0}^{\infty} (-1)^j \binom{4}{j} \binom {n+3-10j}{3} = \binom{n+3}{3}-4\binom{n-7}{3} +6 \binom{n-17}{3}-4\binom{n-27}{3} \]
(considerando anche \(n \le 36\)). Come puoi vedere per \(n< 20\) contano solo i primi due termini, e per \(n=20\) il terzo termine vale 6.
Ah! Vedendo come hai trovato quel 6, mi pare che abbia sbagliato il principio di inclusione-esclusione. Infatti
\[ |A_1 \cup \ldots \cup A_4| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k | - |A_1 \cap \ldots \cap A_4 | \]
In pratica ti sei dimenticato le intersezioni a tre a tre e l'intersezione di tutti e quattro. Prova ad aggiustarlo!