Mixing
Counting permutations of the string ABABABBB in two different ways
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
I have a string ABABABBB, I want to find the number of permutations of the string. I tried to do it in two ways but the answers don't match and I am a bit confused.
First method:
There are $8$ slots and I need to choose $3$ positions to fill in the As (and the Bs go in the rest). So its just $binom83 = 56$.
Second method:
I can ignore the As and write the string as:
.B.B.B.B.B.
The dots are bins and each A can go in any of the $6$ bins. If all $3$ As go into the first bin, I get AAABBBBB and so on. So in this representation each A has $6$ choices to land in and total choices would be $6 cdot 6 cdot 6$. Why is this answer wrong?
combinatorics permutations
edited Jul 23 at 8:36
N. F. Taussig
38.2k93053
asked Jul 23 at 5:45
Lin Endian
132
add a comment |Â
up vote
2
down vote
favorite
I have a string ABABABBB, I want to find the number of permutations of the string. I tried to do it in two ways but the answers don't match and I am a bit confused.
First method:
There are $8$ slots and I need to choose $3$ positions to fill in the As (and the Bs go in the rest). So its just $binom83 = 56$.
Second method:
I can ignore the As and write the string as:
.B.B.B.B.B.
The dots are bins and each A can go in any of the $6$ bins. If all $3$ As go into the first bin, I get AAABBBBB and so on. So in this representation each A has $6$ choices to land in and total choices would be $6 cdot 6 cdot 6$. Why is this answer wrong?
combinatorics permutations
edited Jul 23 at 8:36
N. F. Taussig
38.2k93053
asked Jul 23 at 5:45
Lin Endian
132
3
Your bin method counts ABABABBB six times
– Lord Shark the Unknown
Jul 23 at 5:48
1
Your second way counts putting the first A in slot 1 and the second A in slot 2 as different from putting the first A in slot 2 and the second A in slot 1; but these are the same strings.
– jschnei
Jul 23 at 5:48
Welcome to MathSE. Please read this tutorial on how to typeset mathematics on this site.
– N. F. Taussig
Jul 23 at 8:37
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I have a string ABABABBB, I want to find the number of permutations of the string. I tried to do it in two ways but the answers don't match and I am a bit confused.
First method:
There are $8$ slots and I need to choose $3$ positions to fill in the As (and the Bs go in the rest). So its just $binom83 = 56$.
Second method:
I can ignore the As and write the string as:
.B.B.B.B.B.
The dots are bins and each A can go in any of the $6$ bins. If all $3$ As go into the first bin, I get AAABBBBB and so on. So in this representation each A has $6$ choices to land in and total choices would be $6 cdot 6 cdot 6$. Why is this answer wrong?
combinatorics permutations
edited Jul 23 at 8:36
N. F. Taussig
38.2k93053
asked Jul 23 at 5:45
Lin Endian
132
I have a string ABABABBB, I want to find the number of permutations of the string. I tried to do it in two ways but the answers don't match and I am a bit confused.
First method:
There are $8$ slots and I need to choose $3$ positions to fill in the As (and the Bs go in the rest). So its just $binom83 = 56$.
Second method:
I can ignore the As and write the string as:
.B.B.B.B.B.
The dots are bins and each A can go in any of the $6$ bins. If all $3$ As go into the first bin, I get AAABBBBB and so on. So in this representation each A has $6$ choices to land in and total choices would be $6 cdot 6 cdot 6$. Why is this answer wrong?
combinatorics permutations
edited Jul 23 at 8:36
N. F. Taussig
38.2k93053
asked Jul 23 at 5:45
Lin Endian
132
edited Jul 23 at 8:36
N. F. Taussig
38.2k93053
edited Jul 23 at 8:36
N. F. Taussig
38.2k93053
edited Jul 23 at 8:36
N. F. Taussig
38.2k93053
38.2k93053
asked Jul 23 at 5:45
Lin Endian
132
asked Jul 23 at 5:45
Lin Endian
132
asked Jul 23 at 5:45
Lin Endian
132
132
3
Your bin method counts ABABABBB six times
– Lord Shark the Unknown
Jul 23 at 5:48
1
Your second way counts putting the first A in slot 1 and the second A in slot 2 as different from putting the first A in slot 2 and the second A in slot 1; but these are the same strings.
– jschnei
Jul 23 at 5:48
Welcome to MathSE. Please read this tutorial on how to typeset mathematics on this site.
– N. F. Taussig
Jul 23 at 8:37
add a comment |Â
3
Your bin method counts ABABABBB six times
– Lord Shark the Unknown
Jul 23 at 5:48
1
Your second way counts putting the first A in slot 1 and the second A in slot 2 as different from putting the first A in slot 2 and the second A in slot 1; but these are the same strings.
– jschnei
Jul 23 at 5:48
Welcome to MathSE. Please read this tutorial on how to typeset mathematics on this site.
– N. F. Taussig
Jul 23 at 8:37
3
3
Your bin method counts ABABABBB six times
– Lord Shark the Unknown
Jul 23 at 5:48
Your bin method counts ABABABBB six times
– Lord Shark the Unknown
Jul 23 at 5:48
1
1
Your second way counts putting the first A in slot 1 and the second A in slot 2 as different from putting the first A in slot 2 and the second A in slot 1; but these are the same strings.
– jschnei
Jul 23 at 5:48
Your second way counts putting the first A in slot 1 and the second A in slot 2 as different from putting the first A in slot 2 and the second A in slot 1; but these are the same strings.
– jschnei
Jul 23 at 5:48
Welcome to MathSE. Please read this tutorial on how to typeset mathematics on this site.
– N. F. Taussig
Jul 23 at 8:37
Welcome to MathSE. Please read this tutorial on how to typeset mathematics on this site.
– N. F. Taussig
Jul 23 at 8:37
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
You correctly found that there are $binom83 = 56$ possible permutations of the string ABABABBB.
The reason you did not obtain this answer with your second method is that the As are indistinguishable, so you are counting each string multiple times.
$$square B square B square B square B square B square$$
Placing five Bs in a row creates six spaces, four between successive Bs and two at the ends of the row in which we can place a B. A permutation of ABABABBB is distinguished by how many As are placed in each space. Let $x_k$ be the number of As placed in the $k$th space. Then
$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 3$$
is an equation in the nonnegative integers. A particular solution corresponds to the placement of three ones in a row of five addition signs. For instance,
$$1 1 + + + 1 + +$$
corresponds to the solution $x_1 = 2$, $x_2 = x_3 = 0$, $x_4 = 1$, $x_5 = x_6 = 0$ and the permutation $AABBBABB$. The number of such solutions is the number of ways we can choose which three of the eight positions required for three ones and five addition signs will be filled with ones, which is
$$binom3 + 53 = binom83$$
Notice that the As correspond to the ones and the Bs correspond to the addition signs in the equation $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 3$.
Alternatively, there are $binom63$ ways to place the three As in three different spaces, $6 cdot 5$ ways to place two As in one space and the other A in a different space, and $6$ ways to place all the As in one space.
$$binom63 + 6 cdot 5 + 6 = 20 + 30 + 6 = 56$$
Since your method treats the As as distinguishable, you count strings in which the three As are each placed in a different space six times (corresponding to the $3!$ permutations of the As in those spaces), strings in which two As are placed in one space and one A is placed in another three times (corresponding to which A is placed by itself), and strings in which all the As are placed in the same space once. Notice that
$$colorred6binom63 + colorred3 cdot 6 cdot 5 + 6 = 120 + 90 + 6 = 216 = 6^3$$
answered Jul 23 at 8:33
N. F. Taussig
38.2k93053
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
You correctly found that there are $binom83 = 56$ possible permutations of the string ABABABBB.
The reason you did not obtain this answer with your second method is that the As are indistinguishable, so you are counting each string multiple times.
$$square B square B square B square B square B square$$
Placing five Bs in a row creates six spaces, four between successive Bs and two at the ends of the row in which we can place a B. A permutation of ABABABBB is distinguished by how many As are placed in each space. Let $x_k$ be the number of As placed in the $k$th space. Then
$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 3$$
is an equation in the nonnegative integers. A particular solution corresponds to the placement of three ones in a row of five addition signs. For instance,
$$1 1 + + + 1 + +$$
corresponds to the solution $x_1 = 2$, $x_2 = x_3 = 0$, $x_4 = 1$, $x_5 = x_6 = 0$ and the permutation $AABBBABB$. The number of such solutions is the number of ways we can choose which three of the eight positions required for three ones and five addition signs will be filled with ones, which is
$$binom3 + 53 = binom83$$
Notice that the As correspond to the ones and the Bs correspond to the addition signs in the equation $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 3$.
Alternatively, there are $binom63$ ways to place the three As in three different spaces, $6 cdot 5$ ways to place two As in one space and the other A in a different space, and $6$ ways to place all the As in one space.
$$binom63 + 6 cdot 5 + 6 = 20 + 30 + 6 = 56$$
Since your method treats the As as distinguishable, you count strings in which the three As are each placed in a different space six times (corresponding to the $3!$ permutations of the As in those spaces), strings in which two As are placed in one space and one A is placed in another three times (corresponding to which A is placed by itself), and strings in which all the As are placed in the same space once. Notice that
$$colorred6binom63 + colorred3 cdot 6 cdot 5 + 6 = 120 + 90 + 6 = 216 = 6^3$$
answered Jul 23 at 8:33
N. F. Taussig
38.2k93053
add a comment |Â
up vote
1
down vote
accepted
You correctly found that there are $binom83 = 56$ possible permutations of the string ABABABBB.
The reason you did not obtain this answer with your second method is that the As are indistinguishable, so you are counting each string multiple times.
$$square B square B square B square B square B square$$
Placing five Bs in a row creates six spaces, four between successive Bs and two at the ends of the row in which we can place a B. A permutation of ABABABBB is distinguished by how many As are placed in each space. Let $x_k$ be the number of As placed in the $k$th space. Then
$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 3$$
is an equation in the nonnegative integers. A particular solution corresponds to the placement of three ones in a row of five addition signs. For instance,
$$1 1 + + + 1 + +$$
corresponds to the solution $x_1 = 2$, $x_2 = x_3 = 0$, $x_4 = 1$, $x_5 = x_6 = 0$ and the permutation $AABBBABB$. The number of such solutions is the number of ways we can choose which three of the eight positions required for three ones and five addition signs will be filled with ones, which is
$$binom3 + 53 = binom83$$
Notice that the As correspond to the ones and the Bs correspond to the addition signs in the equation $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 3$.
Alternatively, there are $binom63$ ways to place the three As in three different spaces, $6 cdot 5$ ways to place two As in one space and the other A in a different space, and $6$ ways to place all the As in one space.
$$binom63 + 6 cdot 5 + 6 = 20 + 30 + 6 = 56$$
Since your method treats the As as distinguishable, you count strings in which the three As are each placed in a different space six times (corresponding to the $3!$ permutations of the As in those spaces), strings in which two As are placed in one space and one A is placed in another three times (corresponding to which A is placed by itself), and strings in which all the As are placed in the same space once. Notice that
$$colorred6binom63 + colorred3 cdot 6 cdot 5 + 6 = 120 + 90 + 6 = 216 = 6^3$$
answered Jul 23 at 8:33
N. F. Taussig
38.2k93053
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
You correctly found that there are $binom83 = 56$ possible permutations of the string ABABABBB.
The reason you did not obtain this answer with your second method is that the As are indistinguishable, so you are counting each string multiple times.
$$square B square B square B square B square B square$$
Placing five Bs in a row creates six spaces, four between successive Bs and two at the ends of the row in which we can place a B. A permutation of ABABABBB is distinguished by how many As are placed in each space. Let $x_k$ be the number of As placed in the $k$th space. Then
$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 3$$
is an equation in the nonnegative integers. A particular solution corresponds to the placement of three ones in a row of five addition signs. For instance,
$$1 1 + + + 1 + +$$
corresponds to the solution $x_1 = 2$, $x_2 = x_3 = 0$, $x_4 = 1$, $x_5 = x_6 = 0$ and the permutation $AABBBABB$. The number of such solutions is the number of ways we can choose which three of the eight positions required for three ones and five addition signs will be filled with ones, which is
$$binom3 + 53 = binom83$$
Notice that the As correspond to the ones and the Bs correspond to the addition signs in the equation $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 3$.
Alternatively, there are $binom63$ ways to place the three As in three different spaces, $6 cdot 5$ ways to place two As in one space and the other A in a different space, and $6$ ways to place all the As in one space.
$$binom63 + 6 cdot 5 + 6 = 20 + 30 + 6 = 56$$
Since your method treats the As as distinguishable, you count strings in which the three As are each placed in a different space six times (corresponding to the $3!$ permutations of the As in those spaces), strings in which two As are placed in one space and one A is placed in another three times (corresponding to which A is placed by itself), and strings in which all the As are placed in the same space once. Notice that
$$colorred6binom63 + colorred3 cdot 6 cdot 5 + 6 = 120 + 90 + 6 = 216 = 6^3$$
answered Jul 23 at 8:33
N. F. Taussig
38.2k93053
You correctly found that there are $binom83 = 56$ possible permutations of the string ABABABBB.
The reason you did not obtain this answer with your second method is that the As are indistinguishable, so you are counting each string multiple times.
$$square B square B square B square B square B square$$
Placing five Bs in a row creates six spaces, four between successive Bs and two at the ends of the row in which we can place a B. A permutation of ABABABBB is distinguished by how many As are placed in each space. Let $x_k$ be the number of As placed in the $k$th space. Then
$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 3$$
is an equation in the nonnegative integers. A particular solution corresponds to the placement of three ones in a row of five addition signs. For instance,
$$1 1 + + + 1 + +$$
corresponds to the solution $x_1 = 2$, $x_2 = x_3 = 0$, $x_4 = 1$, $x_5 = x_6 = 0$ and the permutation $AABBBABB$. The number of such solutions is the number of ways we can choose which three of the eight positions required for three ones and five addition signs will be filled with ones, which is
$$binom3 + 53 = binom83$$
Notice that the As correspond to the ones and the Bs correspond to the addition signs in the equation $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 3$.
Alternatively, there are $binom63$ ways to place the three As in three different spaces, $6 cdot 5$ ways to place two As in one space and the other A in a different space, and $6$ ways to place all the As in one space.
$$binom63 + 6 cdot 5 + 6 = 20 + 30 + 6 = 56$$
Since your method treats the As as distinguishable, you count strings in which the three As are each placed in a different space six times (corresponding to the $3!$ permutations of the As in those spaces), strings in which two As are placed in one space and one A is placed in another three times (corresponding to which A is placed by itself), and strings in which all the As are placed in the same space once. Notice that
$$colorred6binom63 + colorred3 cdot 6 cdot 5 + 6 = 120 + 90 + 6 = 216 = 6^3$$
answered Jul 23 at 8:33
N. F. Taussig
38.2k93053
answered Jul 23 at 8:33
N. F. Taussig
38.2k93053
answered Jul 23 at 8:33
N. F. Taussig
38.2k93053
answered Jul 23 at 8:33
N. F. Taussig
38.2k93053
38.2k93053
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2860042%2fcounting-permutations-of-the-string-abababbb-in-two-different-ways%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
3
Your bin method counts ABABABBB six times
– Lord Shark the Unknown
Jul 23 at 5:48
1
Your second way counts putting the first A in slot 1 and the second A in slot 2 as different from putting the first A in slot 2 and the second A in slot 1; but these are the same strings.
– jschnei
Jul 23 at 5:48
Welcome to MathSE. Please read this tutorial on how to typeset mathematics on this site.
– N. F. Taussig
Jul 23 at 8:37