OliForum Matematico

Alur alla gara a squadre di Roma c'era un esercizio che non sono riuscito a risolvere e non ho idea di come si faccia... Vi scrivo qui il testo provate voi e spiegatemi come fare...
"Quante parole di 8 lettere si possono fare usando solo le 5 vocali in modo che siano in ordine alfabetico???"

Teoricamente doveva essere un esercizio "facile"...

Allora, premetto che credo consideriamo il caso in cui tutte le vocali sono presenti almeno una volta, quindi dal momento che abbiamo 5 vocali da mettere in ordine alfabetico avremo uno schema del tipo:

$ \alpha a \quad \beta e \quad \gamma i \quad \delta o \quad \varepsilon u $

dove $ \alpha, \beta... $ indicano quante volte è presente quella vocale

Ora abbiamo vari casi:

1) una vocale è ripetuta 4 volte e le altre 1 da cui $ \displaystyle {5 \choose 1} $ cioè $ 5 $ casi

2) una vocale ripetuta 3 volte, una 2 e le altre 1 da cui $ \displaystyle {5 \choose 1}\cdot{4 \choose 1} $ cioè $ 20 $ casi

3) tre vocali ripetute 2 volte e 2 una volta, in questo caso si hanno $ \displaystyle {5 \choose 1}\cdot{4 \choose 1}\cdot{3 \choose 1} $ cioè 60 possibilità

La risposta credo pertanto che sia $ 5+20+60=85 $

ripeto, se è possibile che alcune vocali non siano presenti, vanno considerati altri casi...

Anch'io premetto le stesse condizioni di alex90, cioè consideriamo il caso in cui tutte le vocali sono presenti almeno una volta.
sono d'accordo sul primo e sul secondo caso di alex90.
sul terzo però sono in disaccordo:
scegliere tre vocali ripetute 2 volte e 2 una sola volta, equivale a dire: scegliere le 2 vocali ripetute una sola volta, e cioè (5 su 2) = 10 casi possibili.
nel secondo caso si è potuto fare (5 su 1) per (4 su 1), poichè erano due cose distinte, cioè scegliere la lettera fra le 5 ripetuta 3 volte, e scegliere la lettera fra le restanti 4 ripetuta 2 volte (o il contrario), ma nel terzo caso le 3 lettere vengono ripetute tutte 2 volte; d'altronde i vari casi possibili sono:
(a=1...e=2...i=3...o=4...u=5)
11223345
11223445
11223455
11233445
11233455
11234455
12233445
12233455
12234455
12334455
e mi sembra non ce ne siano altri.
quindi la soluzione dovrebbe essere:
5+20+10=35 casi possibili

Se ci si mette a dividere in casi si impazzisce abbastanza in fretta (ok, magari non con 8 lettere e 5 vocali, ma con 2009 lettere e 9002 vocali sì). Pensatela così: le scelte da fare sono solo quattro: in che posizione smetto di avere a e passo alle e? In che posizione smetto di avere e e passo alle i? e così via. In quanti posti diversi potete mettere ognuna di queste "transizioni"?
E, poi, controllino "sanity check": "generando" in questo modo le parole, le state generando tutte? Le state generando tutte una volta sola? Se no, come potete correggere il conteggio?

Se non è necessario che ogni vocale compaia almeno una volta, una stringa di $ n $ vocali in ordine alfabetico si può scrivere in $ \displaystyle{n+4\choose4} $ modi (cioè il numero di modi di piazzare 4 separatori in n+4 caselle).

Se invece devono comparire tutte, allora credo che si possa usare il principio di inclusione-esclusione per un conteggio esatto di tutte le possibilità:
$ \displaystyle{n+4\choose4}=(n+4)(n+3)(n+2)(n+1)/24 $ stringhe totali
$ \displaystyle-{5\choose4}{n+3\choose3}=-5(n+3)(n+2)(n+1)/6 $ stringhe che contengono al massimo 4 vocali
$ \displaystyle+{5\choose3}{n+2\choose2}=+10(n+2)(n+1)/2 $ stringhe che contengono al massimo 3 vocali
$ \displaystyle-{5\choose2}{n+1\choose1}=-10(n+1) $ stringhe che contengono al massimo 2 vocali
$ \displaystyle+{5\choose1}{n+0\choose0}=+5 $ stringhe che contengono 1 vocale

Totale $ \displaystyle\frac{1}{24}(n-4)(n-3)(n-2)(n-1) $

La formula funziona per n=5 , e per n=8 la soluzione coincide con quella di iademarco (35)...spero solo che sia giusta!

ha assolutamente ragione iademarco...si vede che era quasi ora di cena mentre scrivevo il tezro punto!

pak-man ha scritto:Se non è necessario che ogni vocale compaia almeno una volta, una stringa di $ n $ vocali in ordine alfabetico si può scrivere in $ \displaystyle{n+4\choose4} $ modi (cioè il numero di modi di piazzare 4 separatori in n+4 caselle).

Se invece devono comparire tutte, allora credo che si possa usare il principio di inclusione-esclusione

Soluzione giusta, ma anche nel caso in cui ogni vocale compare almeno una volta, si riesce a scrivere una formula chiusa senza bisogno di sommare parecchi termini. Hint ma che ti lascia ancora l'idea "grossa" da trovare: il ragionamento che devi fare è simile a quello di "piazzare i separatori" che hai già fatto, ma come si può adattare all'altro caso?

Effettivamente il secondo metodo è troppo contoso, forse ho capito come farlo meglio: dato che ci vuole almeno una vocale per tipo, da n lettere ne prendiamo n-5, aggiungiamo 4 spazi e piazziamo i separatori, che a questo punto possono anche essere ai lati o vicini ché tanto le lettere "escluse" compaiono già dall'esclusione fatta in precedenza.
Quindi i modi sono
$ ${n-5+4\choose4}={n-1\choose4}=\frac{1}{24}(n-1)(n-2)(n-3)(n-4) $
esattamente come nel risultato precedente, ma con meno conti di mezzo

Alur... voglio solo dire che le vocali non devono affatto comparire tutte ;)
E non ho capito la soluzione di pakman...

Cercherò di essere il più chiaro possibile al primo colpo:
-devi piazzare n vocali in ordine alfabetico in una stringa di lunghezza n
-allunghi la stringa di 4 elementi (totale n+4), e oltre alle vocali ora devi inserire 4 'x'
-quanti sono i modi di mettere 4 'x' in n+4 spazi? $ {n+4\choose4} $
-ora a sinistra della prima 'x' metti tutte 'a', a sinistra della seconda tutte 'e', ..., a destra dell'ultima tutte 'u'
-se prima di una 'x' non c'è alcuno spazio (perché la 'x' è il primo carattere o perché ci sono almeno 2 'x' vicine) la vocale corrispondente non va messa (quindi non compare nella stringa)
-fatto: abbiamo contato in questo modo tutte le combinazioni di n vocali in ordine alfabetico, e sono tutti i modi di mettere 4 separatori tra le vocali, ovvero 4 separatori in n+4 spazi

P.S.: è lo stesso metodo che si usa per trovare i modi di scrivere un intero 'm' come somma di h interi non-negativi. Si prende una serie di m+h-1 elementi di cui h-1 sono segni '+', gli altri sono unità: ogni gruppo di unità compreso tra due segni '+' è uno degli h addendi

Perfetto ho capito in pieno ;)
Ma a questo punto... dato che l'hai tirato in ballo ti propongo lo stesso problema detto da te... ma senza l'ordine:
"Trovare tutte le terne (x,y,z) Di numeri naturali tali che x+y+z=n con N naturale. Due terne sono considerate uguali se hanno gli stessi valori anche se in ordine diverso. Dato che una generalizzazione così è troppo difficile vi propongo una generalizzazione solo per i numeri divisibili per 3 ma non per 2... la formula è estremamente semplice in questo caso ;) In ultimo vi propongo questo quesito assumendo N=200... questo era una delle domande della gara a squadre di Roma ;)"
Divertitevi.

Bè quello per n=200 si può usare il binomiale:
$ {n+k-1 \choose k} $
dove k=200 n=3
Questo restituisce tutti i modi considerando l'ordine...ora togliamo le combinazioni con due numeri uguali che sono in tutto 101*3 (0,0,200-1,1,198 ecc. la moltiplicazione per 3 è il numero di posti in cui può stare in numero non uguale)

Si ottiene 19998, che dividiamo per 3! (il numero di permutazioni dei tre elementi)
Otteniamo 3333, a cui aggiungiamo di nuovo 101 per riconsiderare le combinazioni tolte precedentemente : 3434

La soluzione per 200 è perfetta e anche ben più semplice della mia xD
Vorrei capire perchè sono sempre l'unico cretino che non usa i binomiali xD
Io per risolvere ho usato una sommatoria assumendo il numero minore da 0 a 66 e guardando in quanti modi si possono disporre gli altri... il risultato è lo stesso.
Se a qualcuno va fate il caso generale ;)

dario2994 ha scritto:"Trovare tutte le terne (x,y,z) Di numeri naturali tali che x+y+z=n con N naturale. Due terne sono considerate uguali se hanno gli stessi valori anche se in ordine diverso. Dato che una generalizzazione così è troppo difficile

Esatto, per queste non esiste una formula chiusa.

bhe dipende da cosa intendi per formula chiusa... io dividendo in solo 3 casi ho trovato le formule chiuse... e non penso di essere un eminente scienziato che ha appena fatto la scoperta del secolo ;) Quindi provaci ;)
p.s. per formula chiuse intendo una formula che fa uso solo delle operazioni algebriche più il simbolo parte intera [N] che restituisce la parte intera di un numero