I am trying to solve this question from The Book of Proof, and I solved it in a different way than the author. The question is as follows:
How many length-6 lists can be made from the symbols $\{A,B,C,D,E,F,G\}$ if repetition is allowed and the list is in alphabetical order? (Ex. BBCEGG, but not BBBAGG).
My Solution
Since we want this to be in alphabetical order we need to think of what the starting letter is. If the starting letter is $A$ then we are free to choose $A$ as many times after that. If we choose $B$ to be our first letter than we can never choose $A$ in that list.
Using "stars and bars," let's say we choose $A$ to be our first letter, then we have $5$ more spots to from our selection of symbols. Thus, we have $5$ stars and $6$ bars, $\binom{11}{5}$.
Using the same idea for choosing $B$ being the first letter, we have $5$ more spots to fill in, but we cannot choose $A$. This leads to the consequence of loosing a bar. So, we have $5$ stars and now $5$ bars leading to $\binom{10}{5}$
Continuing with this choosing the first letter from $A$ to $G$ we get:
$$\binom{11}{5} + \binom{10}{5} + \binom{9}{5} + \binom{8}{5} + \binom{7}{5} + \binom{6}{5} + \binom{5}{5} = 924$$
Authors Solution:
Any such list corresponds to a 6-element multiset made from the
symbols $\{A,B,C,D,E,F,G \}$. For example, the list AACDDG corresponds to the multiset $[A,A,C,D,D,G]$. Thus the number of lists equals the number of multisets, which is $\binom{12}{6}$.
My Question:
Is my solution a correct way to use Stars and Bars?
The way the author solved it, how can you enforce the idea that the lists are in alphabetical order without explicitly telling it so?
Best Answer
What you are doing starting at the second letter is the same as what author is doing starting at the first letter. When you fix the first letter to be $A$ and then apply stars and bars for the remaining $5$ letters, you are essentially counting number of occurrences of each alphabet from $A, B, C, D, E, F$ and $G$ in $5$ letters. Once you choose number of their occurrences, their positions are fixed in alphabetical order.
You can do the same starting at the first letter. You need $6$ letters from alphabets $A, B, C, D, E, F$ and $G$ with repetition so count number of occurrences of each of them. If number of times they occur is denoted by the corresponding small letters then you are looking for solution to,
$a + b + c + d + e + f + g = 6$ where $a, b, c, d, e, f$ and $g$ are non-negative integers.
And that is given by $ \displaystyle {6 + 7 - 1 \choose 7-1}$