Semplice esercizio di combinatoria...
scusate se vi disturbo per una tale sciocchezza ma è tutto il giorno che studio analisi e sono un pò fuso..c'è questo sempice esercizio di combinatoria, ho capito la soluzione del libro, ho trovato una mia soluzione che mi sembra ugualmente giusta a livello di ragionamento, ma , purtroppo, è sbagliata.
il problema dice:
" l'alfabeto italiano contiene 16 consonanti e 5 vocali. Quante stringhe di 6 lettere si possono formare che contengono la a?
Poi ci sarebbero altri punti, ma a me per ora basta questo. Io ho ragionato così: Metto la $a$ in una delle possibili $6$ "caselle": questo lo posso fare in $6$ modi diversi. Nelle restanti $5$ caselle, posso metterci qualsiasi altra lettera (non è scritto da nessuna parte che le lettere non si possano ripetere)...questo posso farlo in $21^5$ modi diversi. Quindi i modi totali dovrebbero essere $6 * 21^5$...purtroppo però non lo sono..dov'è l'errore?
il problema dice:
" l'alfabeto italiano contiene 16 consonanti e 5 vocali. Quante stringhe di 6 lettere si possono formare che contengono la a?
Poi ci sarebbero altri punti, ma a me per ora basta questo. Io ho ragionato così: Metto la $a$ in una delle possibili $6$ "caselle": questo lo posso fare in $6$ modi diversi. Nelle restanti $5$ caselle, posso metterci qualsiasi altra lettera (non è scritto da nessuna parte che le lettere non si possano ripetere)...questo posso farlo in $21^5$ modi diversi. Quindi i modi totali dovrebbero essere $6 * 21^5$...purtroppo però non lo sono..dov'è l'errore?
Risposte
mi sembra che conti piu' di 1 volta le stringhe in cui compare 2 volte la 'a':
esempio:
amando
viene generata sia con la a all'inizio sia con la a in terza posizione
quindi sembra che nel numero da te calcolato venga contata 2 volte.
spero corretto
esempio:
amando
viene generata sia con la a all'inizio sia con la a in terza posizione
quindi sembra che nel numero da te calcolato venga contata 2 volte.
spero corretto
credo di aver capito l'errore...la soluzione del libro è davvero semplice, solo che non capivo dove sbagliavo...il libro dice che le possibili stringhe di 6 lettere, in totale, sono $21^6$. Da queste bisogna toglierci quelle in cui NON compare la a, cioè tutte le stringhe ottenute con le restanti 20 lettere dell'afabeto, che sono $20^6$. comunque codino te dici che in questo modo io considero diverse (e quindi conto più di una volta) stringhe ottenute scegliendo a in prima posizione e poi il resto ("a-mando") e stringhe generate scegliendo a in terza posizione e il resto : "am-a-ndo", mentre in realtà sono la stessa stringa..comunque sia grazie
"alvinlee88":
credo di aver capito l'errore...la soluzione del libro è davvero semplice, solo che non capivo dove sbagliavo...il libro dice che le possibili stringhe di 6 lettere, in totale, sono $21^6$. Da queste bisogna toglierci quelle in cui NON compare la a, cioè tutte le stringhe ottenute con le restanti 20 lettere dell'afabeto, che sono $20^6$. comunque codino te dici che in questo modo io considero diverse (e quindi conto più di una volta) stringhe ottenute scegliendo a in prima posizione e poi il resto ("a-mando") e stringhe generate scegliendo a in terza posizione e il resto : "am-a-ndo", mentre in realtà sono la stessa stringa..comunque sia grazie
ripensandoci, non sono piu' cosi' sicuro di quello che ho affermato, maa se t ho insinuato il dubbio, e' una buona cosa.
di niente.
allora se l'errore non si limita a questo, che altro c'è da considerare, per seguire l'altra strada e non quella del libro?
Ciao, credo che l'unico errore presente è quello notato da codino75 e che la strada del libro è quella giusta.
si oggi in facoltò ne ho parlato con un mio compagno e siamo giunti alla conclusione che l'errore sta lì...
Un'osservazione: facendo il seguente ragionamento
conti (per esempio) sei volte la stringa "aaaaaa" (perché ogni volta vedi una "a" fissata diversa).
Riadattando il ragionamento, dovresti fare così: fissi la a nella prima posizione e conti le altre possibilità, che sono $21^5$. Quindi fissi la a nella seconda posizione e conti le altre possibilità, escludendo la a nella prima posizione (perché hai già esaurito il caso "a nella prima posizione"): avrai quindi 20 scelte per la prima posizione, e 21 per le altre quattro: $20 \cdot 21^4$ in tutto. Fissi dunque la a nella terza posizione e conti le altre possibilità, escludendo la a nella prima e nella seconda posizione (avendo tu già esaurito il caso "a nella prima posizione e/o nella seconda), ottenendo quindi $20^2 \cdot 21^3$ possibilità. Alla fine - proseguendo in questo modo - ottieni che la soluzione S è:
$S=21^5+20 \cdot 21^4+20^2 \cdot 21^3+20^3 \cdot 21^2+20^4 \cdot 21+20^5 = 21^6-20^6$
L'ultima uguaglianza segue dall'identità $a^n-b^n= (a-b)\sum_{i=0}^{n-1}a^ib^{n-1-i}$.
"alvinlee88":
Metto la $a$ in una delle possibili $6$ "caselle": questo lo posso fare in $6$ modi diversi. Nelle restanti $5$ caselle, posso metterci qualsiasi altra lettera (non è scritto da nessuna parte che le lettere non si possano ripetere)...questo posso farlo in $21^5$ modi diversi. Quindi i modi totali dovrebbero essere $6 * 21^5$
conti (per esempio) sei volte la stringa "aaaaaa" (perché ogni volta vedi una "a" fissata diversa).
Riadattando il ragionamento, dovresti fare così: fissi la a nella prima posizione e conti le altre possibilità, che sono $21^5$. Quindi fissi la a nella seconda posizione e conti le altre possibilità, escludendo la a nella prima posizione (perché hai già esaurito il caso "a nella prima posizione"): avrai quindi 20 scelte per la prima posizione, e 21 per le altre quattro: $20 \cdot 21^4$ in tutto. Fissi dunque la a nella terza posizione e conti le altre possibilità, escludendo la a nella prima e nella seconda posizione (avendo tu già esaurito il caso "a nella prima posizione e/o nella seconda), ottenendo quindi $20^2 \cdot 21^3$ possibilità. Alla fine - proseguendo in questo modo - ottieni che la soluzione S è:
$S=21^5+20 \cdot 21^4+20^2 \cdot 21^3+20^3 \cdot 21^2+20^4 \cdot 21+20^5 = 21^6-20^6$
L'ultima uguaglianza segue dall'identità $a^n-b^n= (a-b)\sum_{i=0}^{n-1}a^ib^{n-1-i}$.
esatto, grazie mille!!! sinceramente mi garba molto di più questa soluzione che quella del libro..sarà perchè era la strada che avevo iniziato io e sono contento che non fosse sbagliata in partenza...ti ringrazio ancora... 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo