OliForum Matematico

Abbiamo due gruppi composti da molti bambini. Il primo gruppo e' formato da bambini senza zaino che occupano 1 spazio, il secondo gruppo da bambini con lo zaino che occupano 2 spazi. In quanti modi si può' formare con i bambini una fila di n spazi?

Sono alle prime armi con la combinatoria e mi servirebbe una mano a risolvere questo esercizio. Grazie!!

Ti conviene chiamare $a_n$ la quantità cercata e definire una ricorsione per $a_n$! Inoltre ti consiglierei di fare i casi piccoli prima per capire com'è fatta!

Lasker ha scritto:Ti conviene chiamare $a_n$ la quantità cercata e definire una ricorsione per $a_n$! Inoltre ti consiglierei di fare i casi piccoli prima per capire com'è fatta!

Testo nascosto:

il primo bambino puoi o sceglierlo senza zaino, completando in gli spazi rimanenti in $a_{n-1}$ modi, oppure con lo zaino, completando in $a_{n-2}$ modi; ottieni dunque $a_{n}=a_{n-1}+a_{n-2}$ e qui ti basta calcolare $a_1$ e $a_2$ a mano per determinare tutto ciò che ti serve (al massimo potresti volere la soluzione esplicita della ricorrenza lineare, la soluzione viene l'n-esimo numero di Fibonacci).

Non ho capito perché possiamo completare la fila in $a_{n-1}$ o in $a_{n-2}$ modi. Non dovrebbero essere di più'? Ci sono tutti i casi in cui c'e' un bambino con la zaino e gli altri senza, due bambini con lo zaino e gli altri senza ecc. considerando che conta l'ordine in cui sono posizionati i bambini. Io avevo anche provato a fare una distinzione tra n dispari e n pari ma non sono riuscita ad andare avanti...

laviniafd ha scritto:considerando che conta l'ordine in cui sono posizionati i bambini

Cosa intendi con questo? Consideri diversi due bambini con lo zaino diversi (cioè se li scambi fra loro e viene una configurazione diversa)? Io ho inteso invece che due bambini senza zaino sono indistinguibili, così come due bambini con lo zaino, mentre se scambio un bambino con lo zaino con uno senza la nuova configurazione è intesa come distinta. Non capisco molto il tuo dubbio, provo a rispiegare più chiaramente la mia soluzione:

Supponiamo di chiamare, per ogni $n$, $a_n$ la soluzione al nostro problema con $n$ spazi. Questi $a_n$ modi li puoi ripartire in due insiemi disgiunti, quelli in cui il primo bambino (=quello posto nel primo spazio) ha lo zaino (e occupa due posti) e quelli in cui il primo bambino non ha lo zaino (e occupa solo un posto). Dopo aver sistemato il primo bambino, nel primo caso rimangono $n-2$ spazi liberi, che puoi riempire per ipotesi in $a_{n-2}$ modi distinti, mentre nel secondo caso ne rimangono $n-1$. Visto che hai contato la cardinalità dello stesso insieme (i modi distinti di riempire $n$ spazi), $a_n=a_{n-1}+a_{n-2}$. I casi che stai citando mi sembra di contarli!

Lasker ha scritto:

laviniafd ha scritto:considerando che conta l'ordine in cui sono posizionati i bambini

Cosa intendi con questo? Consideri diversi due bambini con lo zaino diversi (cioè se li scambi fra loro e viene una configurazione diversa)? Io ho inteso invece che due bambini senza zaino sono indistinguibili, così come due bambini con lo zaino, mentre se scambio un bambino con lo zaino con uno senza la nuova configurazione è intesa come distinta. Non capisco molto il tuo dubbio, provo a rispiegare più chiaramente la mia soluzione:

Supponiamo di chiamare, per ogni $n$, $a_n$ la soluzione al nostro problema con $n$ spazi. Questi $a_n$ modi li puoi ripartire in due insiemi disgiunti, quelli in cui il primo bambino (=quello posto nel primo spazio) ha lo zaino (e occupa due posti) e quelli in cui il primo bambino non ha lo zaino (e occupa solo un posto). Dopo aver sistemato il primo bambino, nel primo caso rimangono $n-2$ spazi liberi, che puoi riempire per ipotesi in $a_{n-2}$ modi distinti, mentre nel secondo caso ne rimangono $n-1$. Visto che hai contato la cardinalità dello stesso insieme (i modi distinti di riempire $n$ spazi), $a_n=a_{n-1}+a_{n-2}$. I casi che stai citando mi sembra di contarli!

No, non intendevo quello, avevi capito bene. Ho capito il tuo ragionamento, ma come faresti a calcolare $a_{n-1}$ o $a_{n-2}$ ?

laviniafd ha scritto: ma come faresti a calcolare $a_{n-1}$ o $a_{n-2}$ ?

Forse ho un'idea, poi dimmi se sbaglio. Dato che $a_n=a_{n-1}+a_{n-2}$, $a_{n-1}=a_{n-2}+a_{n-3}$ e cosi' via. Questo fatto si potrebbe indicare con una formula secondo te?

Si, esatto, il concetto fondamentale è che vuoi ridurre tutto fino ad un caso banale che sai trattare (in questo caso $a_1=1$ e $a_2=2$). Questo genere di problema è molto studiato, quindi sì, esiste una formula chiusa (anche se probabilmente ti farà schifo ):
$$a_n=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}}{\sqrt{5}}$$
Se vuoi imparare come ricavarla, c'è tutta una teoria dietro, e alcuni casi (come questo) sono abbastanza semplici; basta che cerchi "ricorrenze lineari" e dovrebbe saltare fuori subito.

Lasker ha scritto:Si, esatto, il concetto fondamentale è che vuoi ridurre tutto fino ad un caso banale che sai trattare (in questo caso $a_1=1$ e $a_2=2$). Questo genere di problema è molto studiato, quindi sì, esiste una formula chiusa (anche se probabilmente ti farà schifo ):
$$a_n=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}}{\sqrt{5}}$$
Se vuoi imparare come ricavarla, c'è tutta una teoria dietro, e alcuni casi (come questo) sono abbastanza semplici; basta che cerchi "ricorrenze lineari" e dovrebbe saltare fuori subito.

Grazie mille! Mi sei stato di enorme aiuto
Proverò a leggere qualcosa sulle ricorrenze lineari sperando di capirci qualcosa