Quante soluzioni?

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

Quante soluzioni?

Messaggioda Nadal01 » 01/04/2016, 21:43

Determinare quante sono le soluzioni di
[tex]x_0 + x_1 + x_2 + x_3 = 100[/tex] con [tex]x_0 \neq x_1[/tex] e [tex]x_i \in \mathbb N[/tex]
Nadal01
 
Messaggi: 68
Iscritto il: 16/01/2015, 17:12

Re: Quante soluzioni?

Messaggioda Rho33 » 01/04/2016, 21:58

Hint:
Testo nascosto:
se non ci fosse il vincolo $x_0 \not = x_1$ sarebbero $ \displaystyle {103 \choose 3} $ (perchè?) , ora occupati del vincolo ed hai finito.
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Quante soluzioni?

Messaggioda Nadal01 » 01/04/2016, 22:08

Grazie per l'Hint, ma senza il vincolo non avevo problemi (vedi Callegari!).
Il mio problema è proprio il vincolo... :oops:
Nadal01
 
Messaggi: 68
Iscritto il: 16/01/2015, 17:12

Re: Quante soluzioni?

Messaggioda Rho33 » 06/04/2016, 17:24

Ok, allora ti scrivo velocemente la soluzione:

Chiaramente senza vincolo il numero di soluzioni è $\displaystyle {103 \choose 3}$ . Troviamo ora il numero di soluzioni quando accade l'opposto, ovvero $x_0=x_1$ , basterà poi sottrarre tale numero da quello iniziale. Bisogna però precisare che, ovviamente, $0 \leq x_0,x_1,x_2,x_3 \leq 100 $ . Voglio quindi il numero di soluzioni di $2x_1+x_2+x_3=100$ .

$\bullet x_0=x_1=0 \rightarrow x_2+x_3=100 \rightarrow \displaystyle {101 \choose 1}$

$\bullet x_0=x_1=1 \rightarrow x_2+x_3=98 \rightarrow \displaystyle {99 \choose 1}$

$...$

$\bullet x_0=x_1=50 \rightarrow x_2+x_3=0 \rightarrow \displaystyle {1 \choose 1}$

Allora ovviamente il numero cercato è:

$\displaystyle \sum ^{50}_{i=0} {\displaystyle {2i+1 \choose 1}}=(51)^2$ e quindi il numero di soluzioni è:

$\displaystyle {103 \choose 3}-(51)^2$

P.S. Questo problema era facile per il numero basso di variabili, quando esse aumentano sinceramente non saprei come trovare una formula chiusa della somma dei binomiali, però le funzioni generatrici dovrebbero poter essere comode come sostitute.
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Quante soluzioni?

Messaggioda Nadal01 » 07/04/2016, 10:21

Il fatto è che il problema originario era

Determinare quante sono le soluzioni di
[tex]x_0 + x_1 + x_2 + x_3 + x_4 = 9996[/tex] con [tex]x_0 \neq x_1[/tex] e [tex]x_i \in \mathbb N[/tex]

ed io, sbagliando, lo avevo semplificato per vedere se qualcuno mi aiutava a capire come calcolare in modo semplice la sommatoria dei binomiali.

Infatti, nel problema originario, la sommatoria diventa

[tex]\sum_{i=1}^{4999} \binom{2i}{2}[/tex]

che da calcolare è un po' ..... meno semplice. :cry:
Nadal01
 
Messaggi: 68
Iscritto il: 16/01/2015, 17:12

Re: Quante soluzioni?

Messaggioda Nadal01 » 08/04/2016, 14:34

In realtà in questo caso si riesce a calcolare abbastanza facilmente perché abbiamo

${2i \choose 2}=\frac{(2i)!}{(2i-2)!\cdot 2!}=2i^2-i$
quindi
$$\sum_{i=1}^{n}{2i \choose 2}=2\sum_{i=1}^{n}i^2-\sum_{i=1}^{n}i=2\cdot\frac{n\cdot(n+1)\cdot(2\cdot n+1)}{6}-\frac{n\cdot(n+1)}{2}=\frac23 n^3+\frac12 n^2-\frac16 n$$

Il calcolo sarebbe molto .... molto più complicato se l'esercizio avesse anche solo un'altra variabile in più!
Nadal01
 
Messaggi: 68
Iscritto il: 16/01/2015, 17:12

Re: Quante soluzioni?

Messaggioda Rho33 » 11/05/2016, 18:39

Ieri ,abbastanza per caso, mi sono ricordato di questo problema. In realtà, oltre a ripetere che con le generatrici viene di sicuro, indipendentemente dal numero di variabili, basta soltanto fare i conti e sapere la somma delle prime potenze $h-$ esime. Cioè: ti sporchi le mani a trovare la somma dei binomiali, dopo di che, dato che hai sempre $k$ fissato, come vedo hai fatto nell'ultimo post, trovi un binomiale generico, ed infine lo scomponi usando le somme delle potenze. Ti faccio l'esempio con una variabile in più:

$x_0 + x_1 + x_2 + x_3 + x_4+x_5 = 100$ con $x_0 \not = x_1$ .

$\bullet x_0=x_1=0 \rightarrow x_2+x_3+x_4+x_5=100 \rightarrow \displaystyle {103 \choose 3}$

$\bullet x_0=x_1=1 \rightarrow x_2+x_3+x_4+x_5=98 \rightarrow \displaystyle {101 \choose 3}$

Ecc..

Quindi:

$\displaystyle \sum ^{51}_{i=1} {\displaystyle {2i+1 \choose 3}}$ .

Ora si vede che: $\displaystyle{2i+1 \choose 3}=\frac{(2i+1)!}{(2i+1-3)!\cdot 3!}= \dfrac {4i^3-i}{3}$

Quindi: $\displaystyle \sum ^{n}_{i=1} {\displaystyle {2i+1 \choose 3}}= \dfrac {1}{3} \cdot (4 \sum_{i=1}^{n}i^3-\sum_{i=1}^{n}i)= \dfrac {1}{6} \cdot n(n+1)(2n^2+2n-1)$

E fine, quindi facendo i conti, e sapendo le varie somme, trovi sempre la somma dei binomiali.
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite