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

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
emacoder
Messaggi: 19
Iscritto il: 09 apr 2014, 20:12

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

Messaggio da emacoder » 23 apr 2014, 17:34

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 $ ?
Problem solving can be learnt only by solving problems!

Avatar utente
Drago96
Messaggi: 1143
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

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

Messaggio da Drago96 » 23 apr 2014, 17:47

Dipende se vuoi contare l'ordine o no... probabilmente no, e allora il modo più sensato è probabilmente quello di andare a casi e tentativi...
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

emacoder
Messaggi: 19
Iscritto il: 09 apr 2014, 20:12

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

Messaggio da emacoder » 23 apr 2014, 21:15

Pensavo ci fosse un metodo pronto, grazie comunque!
Problem solving can be learnt only by solving problems!

Avatar utente
elianto84
Messaggi: 266
Iscritto il: 20 mag 2005, 18:35
Località: Pisa
Contatta:

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

Messaggio da elianto84 » 23 apr 2014, 23:54

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
Jack alias elianto84 alias jack202

http://www.matemate.it IL SITO

.::Achtung!!::. - Jordan causa nilpotenza -

emacoder
Messaggi: 19
Iscritto il: 09 apr 2014, 20:12

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

Messaggio da emacoder » 24 apr 2014, 20:11

Soluzione elegante quanto complessa ahah
Problem solving can be learnt only by solving problems!

Avatar utente
Drago96
Messaggi: 1143
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

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

Messaggio da Drago96 » 26 apr 2014, 21:31

elianto84 ha scritto: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...
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

Avatar utente
gpzes
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00
Contatta:

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

Messaggio da gpzes » 27 apr 2014, 16:37

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
Messaggi: 481
Iscritto il: 01 lug 2011, 22:52

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

Messaggio da Gottinger95 » 28 apr 2014, 08:04

@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. :D
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe

Avatar utente
gpzes
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00
Contatta:

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

Messaggio da gpzes » 28 apr 2014, 10:47

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 ;).
Ultima modifica di gpzes il 29 apr 2014, 02:31, modificato 1 volta in totale.

Gottinger95
Messaggi: 481
Iscritto il: 01 lug 2011, 22:52

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

Messaggio da Gottinger95 » 28 apr 2014, 22:20

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! :D

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!
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe

Avatar utente
gpzes
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00
Contatta:

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

Messaggio da gpzes » 28 apr 2014, 23:17

$
Ultima modifica di gpzes il 29 apr 2014, 02:34, modificato 3 volte in totale.

Avatar utente
gpzes
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00
Contatta:

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

Messaggio da gpzes » 28 apr 2014, 23:22

Gent.mo Gottinger,
grazie veramente per disponibilità, informazioni e programma !!! :)
In effetti sono stato un po' fumoso nell'esposizione :oops: Il programma devo studiarlo perchè non ricordo niente di C !! E sicuramente sono impedito nello scrivere qui.Alla fine finirò per allegare files :D :lol: :wink:
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!!! :wink: :shock: :shock:

Gottinger95
Messaggi: 481
Iscritto il: 01 lug 2011, 22:52

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

Messaggio da Gottinger95 » 29 apr 2014, 23:07

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ù' :D
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe

Avatar utente
gpzes
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00
Contatta:

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

Messaggio da gpzes » 29 apr 2014, 23:29

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

Gottinger95
Messaggi: 481
Iscritto il: 01 lug 2011, 22:52

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

Messaggio da Gottinger95 » 30 apr 2014, 00:14

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!
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe

Rispondi