I bambini in fila

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
laviniafd
Messaggi: 12
Iscritto il: 08 apr 2016, 17:18

I bambini in fila

Messaggio da laviniafd »

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!! :D
Avatar utente
Lasker
Messaggi: 440
Iscritto il: 02 mag 2013, 20:47
Località: Udine

Re: I bambini in fila

Messaggio da Lasker »

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).
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)

"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)

Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?

PRIMA FILA TUTTI SBIRRI!
laviniafd
Messaggi: 12
Iscritto il: 08 apr 2016, 17:18

Re: I bambini in fila

Messaggio da laviniafd »

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...
Avatar utente
Lasker
Messaggi: 440
Iscritto il: 02 mag 2013, 20:47
Località: Udine

Re: I bambini in fila

Messaggio da Lasker »

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!
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)

"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)

Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?

PRIMA FILA TUTTI SBIRRI!
laviniafd
Messaggi: 12
Iscritto il: 08 apr 2016, 17:18

Re: I bambini in fila

Messaggio da laviniafd »

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
Messaggi: 12
Iscritto il: 08 apr 2016, 17:18

Re: I bambini in fila

Messaggio da laviniafd »

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?
Avatar utente
Lasker
Messaggi: 440
Iscritto il: 02 mag 2013, 20:47
Località: Udine

Re: I bambini in fila

Messaggio da Lasker »

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 :lol: ):
$$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.
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)

"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)

Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?

PRIMA FILA TUTTI SBIRRI!
laviniafd
Messaggi: 12
Iscritto il: 08 apr 2016, 17:18

Re: I bambini in fila

Messaggio da laviniafd »

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 :lol: ):
$$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 :D
Proverò a leggere qualcosa sulle ricorrenze lineari sperando di capirci qualcosa :lol:
Rispondi