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:

$(}\genfrac{}{}{0ex}{}{11}{5}{\textstyle )}+{\textstyle (}\genfrac{}{}{0ex}{}{10}{5}{\textstyle )}+{\textstyle (}\genfrac{}{}{0ex}{}{9}{5}{\textstyle )}+{\textstyle (}\genfrac{}{}{0ex}{}{8}{5}{\textstyle )}+{\textstyle (}\genfrac{}{}{0ex}{}{7}{5}{\textstyle )}+{\textstyle (}\genfrac{}{}{0ex}{}{6}{5}{\textstyle )}+{\textstyle (}\genfrac{}{}{0ex}{}{5}{5}{\textstyle )}=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 $(}\genfrac{}{}{0ex}{}{12}{6}{\textstyle )$

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?

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:

$(}\genfrac{}{}{0ex}{}{11}{5}{\textstyle )}+{\textstyle (}\genfrac{}{}{0ex}{}{10}{5}{\textstyle )}+{\textstyle (}\genfrac{}{}{0ex}{}{9}{5}{\textstyle )}+{\textstyle (}\genfrac{}{}{0ex}{}{8}{5}{\textstyle )}+{\textstyle (}\genfrac{}{}{0ex}{}{7}{5}{\textstyle )}+{\textstyle (}\genfrac{}{}{0ex}{}{6}{5}{\textstyle )}+{\textstyle (}\genfrac{}{}{0ex}{}{5}{5}{\textstyle )}=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 $(}\genfrac{}{}{0ex}{}{12}{6}{\textstyle )$

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

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 $(}\genfrac{}{}{0ex}{}{6+7-1}{7-1}{\textstyle )$

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 $(}\genfrac{}{}{0ex}{}{6+7-1}{7-1}{\textstyle )$

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 $\textstyle (}\genfrac{}{}{0ex}{}{6+7-1}{7-1}{\textstyle )$

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 $\textstyle (}\genfrac{}{}{0ex}{}{6+7-1}{7-1}{\textstyle )$

Most Popular Questions