Combinatorics - How many ways are there to arrange the string of letters AAAAAABBBBBB such that each A is next to at least one other A?

Nathanial Levine 2022-09-09 Answered
Combinatorics - How many ways are there to arrange the string of letters AAAAAABBBBBB such that each A is next to at least one other A?
I found a problem in my counting textbook, which is stated above. It gives the string AAAAAABBBBBB, and asks for how many arrangements (using all of the letters) there are such that every A is next to at least one other A.
I calculated and then looked into the back for the answer, and the answer appears to be 105. My answer fell short of that by quite a bit. I broke down the string into various cases, and then used Stars and Bars to find how many possibilities there are for each. Now here's what I have got so far. First case would be all As are right next to each other, leaving 2 spots for the 6 Bs. That gives ( 7 1 ) from Stars and Bars, 7 possibilities. Second case was dividing the As into 2 groups of 3 As. There would have to be 1 B between the two, which leaves 5 Bs that can be moved. Using Stars and Bars, there are 3 possible places to place a B and 5 Bs in total, so ( 6 2 ) , 15 possibilities. Then there's a group of 4 As and another group of 2 As. 1 B would be placed inbetween, and then the calculation would be the same as the second case, except it would have to be doubled to account that the groups of As can be swapped and it would be distinct. That gives 30 possibilities. Then I found one final case of dividing the As into 3 groups of 2 As. 2 Bs would immediately be placed between the 3 groups, leaving 4 Bs to move between the 4 possible locations. I got ( 5 3 ) for that, which adds 10 possibilities. Summing it up, I only have 62 possibilities, which is quite far from the 105 answer. Any ideas where I might have miscalculated or missed a potential case? Additionally, are there any better ways to calculate this compared to this method of casework?
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (2)

Answered 2022-09-10 Author has 10 answers
Step 1
If we space Bs first, there are 7 empty positions:
Step 2
There are 4 ways to insert A:
6A group together, C 1 7 = 7 ways
4A and 2A group together, 2 C 2 7 = 42 ways
3A and 3A together, C 2 7 = 21 ways
2A,2A,2A together, C 3 7 = 35 ways
Total 105 ways.
Did you like this example?
Subscribe for all access
Shawn Peck
Answered 2022-09-11 Author has 2 answers
Step 1
One way is using generating functions:
Once you space the B's, there are seven slots for placing A's.
Each slot can have either 0, or 2 or more A's. The "generating function" for a single slot is a polynomial a 0 + a 1 x + a 2 x 2 + . . . where a k is the number of ways to put k A's into a single slot. That is, the generating function is f ( x ) = 1 + x 2 + x 3 + . . . = 1 1 x x = 1 x + x 2 1 x .
Step 2
But you don't have 1 slot, you have 7. The generating function for 7 slots is g ( x ) = f ( x ) 7 = ( 1 x + x 2 ) 7 ( 1 x ) 7 = 1 + 0 x + 7 x 2 + 7 x 3 + 28 x 4 + 49 x 5 + 105 x 6 + 196 x 7 + 37 x 8 . . .
Each term b k x k gives the number of ways b k to place k A's into the 7 slots, subject to your restriction. Since you have six A's, you need to find the coefficient of x 6 in the taylor series, which is 105.
Admittedly, the last step is messy on paper, since the 6th derivative of g(x) might get complicated, but it's easy for a computer algebra package.
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-03-02
In how many ways can 7 graduate students be assigned to 1 triple and 2 double hotel rooms during a conference
asked 2020-11-01
Solve the following problems applying Polya’s Four-Step Problem-Solving strategy.
If six people greet each other at a meeting by shaking hands with one another, how many handshakes take place?
asked 2021-01-06
Inference about cause and effect but cant
asked 2022-04-06

In a study of the accuracy of fast food​ drive-through orders, Restaurant A had


accurate orders and


that were not accurate.

a. Construct a


confidence interval estimate of the percentage of orders that are not accurate.

b. Compare the results from part​ (a) to this


confidence interval for the percentage of orders that are not accurate at Restaurant​ B:


What do you​ conclude?


asked 2021-03-09
Decide equation using only factors to solve this problem
12x2 + 5x  2=0
asked 2022-09-07
Size of automorphism group of element of Y 0 ( 5 )
The modular curve Y 0 ( 5 ) parametrizes elliptic curves E with an isogeny of degree five. So an element of Y 0 ( 5 ) can be interpreted as
E ϕ E
Suppose we are working over a finite field. An automorphism of these curves is an automorphism of the curve E, that sends the kernel G of the map ϕ to itself, over some algebraic closure. The elements of Y 0 ( 5 ) do admit automorphisms, because any curve has the hyperelliptic involution.
Because G is of order five, it can have at most four automorphisms. If the curve E has six automorphisms, it is clear, by comparing the sizes of the groups, that only the identity and the hyperelliptic involution respect the subgroup G. If E has four automorphisms, this kind of reasoning doesn't work. Is there a similar result if E has four automorphisms? To me it is not clear if there are always only two automorphisms that map G to itself, or that there could be four.
asked 2022-09-11
Fuchsian Groups of the First Kind and Lattices
First, a Fuchsian group is a discrete subgroup of PSL 2 ( R ), which we can view as a group of transformations of the upper half-plane H that acts discontinuously. A lattice is a Fuchsian group with finite covolume. In other words, it is a Fuchsian group that has a fundamental domain in H with finite hyperbolic area (and then any two fundamental domains have the same hyperbolic area).
My confusion arises with the notion of a Fuchsian group of the first kind. Every definition I have seen for this term is roughly the same. A Fuchsian group Γ is said to be of the first kind if every point in R { } (the boundary of H) is a limit point of the orbit Γz for some z H . Here, the notion of "limit point" is with respect to the topology on the Riemann sphere C .

New questions