Calcolare, per ogni numero naturale $ n $, il valore della seguente espressione:
$ \displaystyle \sum_{k=0}^{n}\sum_{l=k+1}^{n+1}\binom{n}{k}\binom{n+1}{l} $
I gara a squadre UNIMI- Quesito 4
I gara a squadre UNIMI- Quesito 4
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
Re: I gara a squadre UNIMI- Quesito 4
intanto riscriviamo la sommatoria
$ \displaystyle \sum_{k=0}^{n}\sum_{l=k+1}^{n+1}\binom{n}{k}\binom{n+1}{l}=\sum_{n+1\geq l>k}\binom{n}{k}\binom{n+1}{l} $
noi sappiamo che
$ \displaystyle \binom{n}{k}\binom{n+1}{l}=\binom{n}{n-k}\binom{n+1}{n+1-l} $
e chiaramente se $ l>k $, allora $ n-k\geq n+1-l $
l'insieme delle coppie $ (l,k) $ tali che $ n+1\geq l>k $ contiene $ \displaystyle \binom{n+1}{2}=\frac{n(n+1)}{2} $ coppie.
ad ogni coppia di tale insieme ne corrisponde una $ (n+1-l,n-k) $ tale che
$ n\geq n-k \geq n+1-l $(e quindi diversa da una qualsiasi coppia dell'altro insieme) e tale che $ \displaystyle \binom{n}{k}\binom{n+1}{l}=\binom{n}{n-k}\binom{n+1}{n+1-l} $.
Possiamo quindi scrivere
$ \displaystyle \sum_{n+1\geq l>k}\binom{n}{k}\binom{n+1}{l}=\sum_{n+1\geq l>k}\frac{\binom{n}{k}\binom{n+1}{l}+\binom{n}{n-k}\binom{n+1}{n+1-l}}{2} $
$ \displaystyle \sum_{n+1\geq l>k}\frac{\binom{n}{k}\binom{n+1}{l}+\binom{n}{n-k}\binom{n+1}{n+1-l}}{2}=\frac{1}{2}\sum_{n+1\geq l;n\geq k}\binom{n}{k}\binom{n+1}{l} $
$ \displaystyle \frac{1}{2}\sum_{n+1\geq l;n\geq k}\binom{n}{k}\binom{n+1}{l}=\frac{1}{2}\sum_{l=0}^{n+1}\binom{n+1}{l}\sum_{k=0}^{n}\binom{n}{k} $
$ \displaystyle \frac{1}{2}\sum_{l=0}^{n+1}\binom{n+1}{l}\sum_{k=0}^{n}\binom{n}{k}=\frac{1}{2}\cdot 2^n\cdot 2^{n+1}=4^n $
puff...ciao ciao a tutti
ps. l'idea non è così complicata, il vero problema è formalizzarla senza schemi...
pps. x boll com'è andata la gara?chic'erachihavintocomeseiarrivato?
$ \displaystyle \sum_{k=0}^{n}\sum_{l=k+1}^{n+1}\binom{n}{k}\binom{n+1}{l}=\sum_{n+1\geq l>k}\binom{n}{k}\binom{n+1}{l} $
noi sappiamo che
$ \displaystyle \binom{n}{k}\binom{n+1}{l}=\binom{n}{n-k}\binom{n+1}{n+1-l} $
e chiaramente se $ l>k $, allora $ n-k\geq n+1-l $
l'insieme delle coppie $ (l,k) $ tali che $ n+1\geq l>k $ contiene $ \displaystyle \binom{n+1}{2}=\frac{n(n+1)}{2} $ coppie.
ad ogni coppia di tale insieme ne corrisponde una $ (n+1-l,n-k) $ tale che
$ n\geq n-k \geq n+1-l $(e quindi diversa da una qualsiasi coppia dell'altro insieme) e tale che $ \displaystyle \binom{n}{k}\binom{n+1}{l}=\binom{n}{n-k}\binom{n+1}{n+1-l} $.
Possiamo quindi scrivere
$ \displaystyle \sum_{n+1\geq l>k}\binom{n}{k}\binom{n+1}{l}=\sum_{n+1\geq l>k}\frac{\binom{n}{k}\binom{n+1}{l}+\binom{n}{n-k}\binom{n+1}{n+1-l}}{2} $
$ \displaystyle \sum_{n+1\geq l>k}\frac{\binom{n}{k}\binom{n+1}{l}+\binom{n}{n-k}\binom{n+1}{n+1-l}}{2}=\frac{1}{2}\sum_{n+1\geq l;n\geq k}\binom{n}{k}\binom{n+1}{l} $
$ \displaystyle \frac{1}{2}\sum_{n+1\geq l;n\geq k}\binom{n}{k}\binom{n+1}{l}=\frac{1}{2}\sum_{l=0}^{n+1}\binom{n+1}{l}\sum_{k=0}^{n}\binom{n}{k} $
$ \displaystyle \frac{1}{2}\sum_{l=0}^{n+1}\binom{n+1}{l}\sum_{k=0}^{n}\binom{n}{k}=\frac{1}{2}\cdot 2^n\cdot 2^{n+1}=4^n $
puff...ciao ciao a tutti
ps. l'idea non è così complicata, il vero problema è formalizzarla senza schemi...
pps. x boll com'è andata la gara?chic'erachihavintocomeseiarrivato?
Re: I gara a squadre UNIMI- Quesito 4
Allora, riguardo alla prima affermazione, io ho mandato appunto la soluzione con gli schemi, non so se sarei riuscito a formalizzarla bene quanto te, non credo... comunque l'idea è esattamente la stessa.frengo ha scritto: ps. l'idea non è così complicata, il vero problema è formalizzarla senza schemi...
pps. x boll com'è andata la gara?chic'erachihavintocomeseiarrivato?
Riguardo alla seconda domanda, allora
- questi erano i quesiti della Gara a Squadre Telematica, cioè una gara a squadre, i cui testi vengono pubblicati e le cui soluzioni vengono mandate via mail dalle scuole, personalmente io ne ho mandati 4 (manca il gioco) e spero siano giuste.
- per quanto riguarda la gara individuale, che organizza sempre l'UNIMI, ma in un luogo preciso (l'uni di Milano), i quesiti non li ricordo tutti perfettamente, quindi non li posto, io sono andato male, come al solito nelle gare "in loco", c'erano una trentina di persone, fra quelli che hanno fatto meglio direi Leblanc, Masso, thematrix (spero non si offendano perchè gufo....)
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)