Forma una parola di 8 lettere usando A,B,C,D,E, se le lettere della parola devono apparire in ordine alfabetico

Question

Forma una parola di 8 lettere usando A,B,C,D,E, dove ogni lettera può essere usata più volte . Quante parole posso formare se le lettere della parola devono apparire in ordine alfabetico?

Ad esempio: AABBDDDEè accettabile, BBBACCCEnon è accettabile.

L'unico modo che mi viene in mente per contarlo è disegnare una tabella con il numero di occorrenze di ogni lettera, quindi calcolare le permutazioni delle posizioni delle lettere per ogni riga.

C'è un modo più semplice per risolvere questa domanda?

Answer 1

La risposta è la stessa se conti le parole alfabetiche di lunghezza$13$in cui ogni lettera deve comparire almeno una volta (aggiungendo/togliendo una copia di ogni lettera).

Per contarli, immagina un elenco di$13$slot (alias "stelle") che conterranno le lettere. Per specificare una parola, devi solo scegliere$4$lacune dal$12$spazi interni tra gli slot per specificare il$4$luoghi (ovvero "barre") in cui la lettera cambia nella parola (cioè da A a B, da B a C, ecc.).

Questo può essere fatto dentro$C(12,4) = 495$modi.

Answer 2

Osserva che il tipo di parola che vuoi è univocamente deciso dai numeri delle lettere A,B,C,D ed E. Allora il problema è lo stesso di chiedere in quanti modi si può scrivere 8 come somma di 5 numeri, e la risposta è${12\choose 8}$, sai perché?

Answer 3

Approccio diretto, dove quasi non hai bisogno di pensare (le risposte di Alex e Alessandro Cigna richiedono un po' di riflessione).
Permettere$f(n,k)$essere il numero delle stringhe desiderate con$n$lunghezza lettere con$k$lettere consentite. abbiamo$$f(1,k)=k,\quad f(n,k)=\sum\limits_{i=0}^{k-1}f(n-1,k-i).$$

Tabella per f(n,k)
n\k| 1 | 2 | 3 | 4 | 5
---+--------+--------+--------+--------+--------
 1 | 1 | 2 | 3 | 4 | 5
 2 | 1 | 3 | 6 | 10 | 15
 3 | 1 | 4 | 10 | 20 | 35
 4 | 1 | 5 | 15 | 35| 70
 5 | 1 | 6 | 21 | 56 | 126
 6 | 1 | 7 | 28 | 84 | 210
 7 | 1 | 8 | 36 | 120| 330
 8 | | | | | 495

Answer 4

Hai$8+5-1=12$slot, da cui è necessario scegliere$4$. Wach tale scelta determina il numero di volte che ogni lettera viene ripetuta. Ad esempio, se scegli gli slot da 1 a 4, ottieni tutti gli Es. Puoi gestire da qui?