How many length-6 lists can be made from the symbols {A,B,C,D,E,F,G} if repetition is allowedI...

Savanah Boone

Savanah Boone

Answered

2022-07-07

How many length-6 lists can be made from the symbols {A,B,C,D,E,F,G} if repetition is allowed
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, (115).
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
Continuing with this choosing the first letter from A to G we get:
( 11 5 ) + ( 10 5 ) + ( 9 5 ) + ( 8 5 ) + ( 7 5 ) + ( 6 5 ) + ( 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 ( 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?

Answer & Explanation

Jaelynn Cuevas

Jaelynn Cuevas

Expert

2022-07-08Added 16 answers

Step 1
This 6-element lists that can be formed by the set{A,B,C,D,E,F,G} ,it's called a multisets , so the number of 6-element multisets is the numbers of weak composition of 6 into 7 parts , and that is the number of solutions of this equation a + b + c + d + e + f + g = 6. note that the solution (3,2,1,0,0,0,0) is mean we choose 3 A and 2 B and 1 c so this multiset is AAABBC
Step 2
As we say the numbers of 6-elemnt multisets is the number of weak composition of 6 into 7 part so it is ( 6 + 7 1 7 1 )
Addison Trujillo

Addison Trujillo

Expert

2022-07-09Added 6 answers

Step 1
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.
Step 2
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 ( 6 + 7 1 7 1 )

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get your answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?