Using letters from the alphabet $A = \{a, b, c, d, e, f, g\}$, how many words of length $5$ are possible when repetition is allowed but the letters must occur in alphabetical order?
Not sure how to tackle this one in the case that repetition is allowed. Any hints? Thanks! :)
On
The question can be rephrased as:
How many different sums $n_a+n_b+n_c+n_d+n_e+n_f+n_g=5$ are there for nonnegative integers $n_a,n_b,n_c,n_d,n_e,n_f,n_g$?
E.g. possibility $2+0+1+1+1+0+0=5$ corresponds with word "aacde".
This can be solved with stars and bars.
On
You can just go through the various partitions of $5$:
$$\{5\},\{4,1\},\{3,2\},\{3,1,1\},\{2,2,1\},\{2,1,1,1\},\{1,1,1,1,1\}$$
and work out the choices for each; respectively:
$$7, 7\cdot 6, 7\cdot 6, 7 {6\choose 2}, 7{6\choose 2}, 7 {6\choose 3},{7\choose 5}$$
and add those possibilities together.
Alternatively you can think of placing 6 "next letter" flags $\fbox >$ among and around 5 'report letter' flags $\fbox x$, eg:
$$\fbox >,\fbox x, \fbox >, \fbox >, \fbox x, \fbox x, \fbox >, \fbox x, \fbox >, \fbox >,\fbox x$$
here giving $bddeg$. Then it is just a matter of choosing which of the $11$ flags are which.
On
Count the number of ways $5$ balls can be placed in $7$ bins marked $a-g$, using stars and bars
A result of $\;\;\fbox{2}\fbox{0}\fbox{0}\fbox{1}\fbox{0}\fbox{1}\fbox{1}\;$, e.g. means obtaining $aadfg$.
Thus $\binom{5+7-1}{7-1}$ ways
On
Although all the other ideas presented here are great (i.e. the stars and bars method), I want to give a different approach to this question. To start, let us consider the same problem, but with two letters.
In this case, if the first letter is a, the second letter can be any of the 7 letters.
If the first letter is b, the second letter can be the 6 letters after a.
If the first letter is c, the second letter can be the 5 letters after b.
If we keep doing this, we will eventually reach the case where the first letter is g, and the second letter can only be g. As you can see, for an alphabet with $n$ letters, the number of two letter words is just the $nth$ Triangular Number, which is given by the formula $n(n+1)/2$. Now let us consider three letter words.
If the first letter is a, then the second letter can be any letter from a to g, which we can consider to be a two letter word with an alphabet $A=\{a,b,c,d,e,f,g\}$, which is the two letter word case. We therefore have $\frac{7*(7+1)}2=28$ combinations for the case starting with a.
If the first letter is b, then the alphabet for the rest of the word is $\{b,c,d,e,f,g\}$ and it has $\frac{6*(6+1)}2=21$ combinations.
If the first letter is c, then the alphabet for the rest of the word is $\{c,d,e,f,g\}$ and it has $\frac{5*(5+1)}2=15$ combinations.
If we add up all these combinations, we will get the $7th$ Tetrahedral Number, which is the sum of the first $7$ Triangular Numbers. The formula for the $nth$ Tetrahedral Number is $\frac{n*(n+1)*(n+2)}6$.
There are several important things to realize here:
https://en.wikipedia.org/wiki/Simplex
https://en.wikipedia.org/wiki/Figurate_number
Finally, from this we can see that the answer to the general problem with an alphabet with size $a$ and a word length of $n$ is the $nth$ $a$-simplex number, which has a formula $\binom{n+a-1}{a}$, which you will notice is the same answer as everyone else has given.
Hint: There's only one way to write a given set of 5 letters in alphabetical order. This allows us to deduce that there is a bijection between the number of words you can make with the conditions you want and the number of size 5 subsets of $\{a,b,c,d,e,f,g\}$ (with repitition allowed).