$2n \text{-uple}$

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

$2n \text{-uple}$

Messaggioda Rho33 » 08/06/2016, 11:04

Determinare il numero delle $2n \text{-uple}$ $(x_1,...,x_n,y_1,...,y_n)$ tali che:

(i)tutti gli $x_i,y_i$ siano $0 $ oppure $1$

(ii)$\displaystyle \sum_{i=1}^n x_iy_i$ sia pari


P.S.Io non mi trovo con il risultato ufficiale (è un Cortona del 2000) quindi cerco qualche soluzione diversa per esserne sicuro, in caso tra un poco posto la mia "finta" soluzione.
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: $2n \text{-uple}$

Messaggioda Gerald Lambeau » 08/06/2016, 15:28

Testo nascosto:
Siano $P_n$ e $D_n$ il numero di $2n$-uple con somme rispettivamente pari e dispari. Chiaramente $P_1=3, D_1=1$.
Abbiamo anche che
$P_{n+1}=3P_n+D_n$;
$D_{n+1}=3D_n+P_n$.
Consideriamo la successione $A_n=P_n-D_n$. Abbiamo che $A_{n+1}=P_{n+1}-D_{n+1}=2(P_n-D_n)=2A_n$. Da ciò si ricava facilmente per induzione che $A_n=2^n$, inoltre $B_n=P_n+D_n=4^n$ (è il numero di tutte le possibili $2n$-uple).
Da cui si ha $P_n=(A_n+B_n)/2=2^{n-1}(2^n+1)$.
Analogamente possiamo trovare $D_n=(B_n-A_n)/2=2^{n-1}(2^n-1)$. Curiosamente vale $D_6=2016$.
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: $2n \text{-uple}$

Messaggioda Rho33 » 09/06/2016, 10:02

Eh, caro Gerald, concordo sul risultato! Il punto è che nella soluzione ufficiale il numero è $2^n(2^{n-1}+1)$ che chiaramente non va bene, basta fare i primi casi d'esempio :?: :?:
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