Nathanial Levine

2022-09-09

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 $(}\genfrac{}{}{0ex}{}{7}{1}{\textstyle )$ 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 $(}\genfrac{}{}{0ex}{}{6}{2}{\textstyle )$, 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 $(}\genfrac{}{}{0ex}{}{5}{3}{\textstyle )$ 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?

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 $(}\genfrac{}{}{0ex}{}{7}{1}{\textstyle )$ 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 $(}\genfrac{}{}{0ex}{}{6}{2}{\textstyle )$, 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 $(}\genfrac{}{}{0ex}{}{5}{3}{\textstyle )$ 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?

bewagox7

Beginner2022-09-10Added 10 answers

Step 1

If we space Bs first, there are 7 empty positions:

−B−B−B−B−B−B−

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.

If we space Bs first, there are 7 empty positions:

−B−B−B−B−B−B−

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.

Shawn Peck

Beginner2022-09-11Added 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}+...=\frac{1}{1-x}-x=\frac{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}=\frac{(1-x+{x}^{2}{)}^{7}}{(1-x{)}^{7}}=1+0x+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.

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}+...=\frac{1}{1-x}-x=\frac{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}=\frac{(1-x+{x}^{2}{)}^{7}}{(1-x{)}^{7}}=1+0x+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.

The product of the ages, in years, of three (3) teenagers os 4590. None of the have the sane age. What are the ages of the teenagers???

Use the row of numbers shown below to generate 12 random numbers between 01 and 99

78038 18022 84755 23146 12720 70910 49732 79606

Starting at the beginning of the row, what are the first 12 numbers between 01 and 99 in the sample?How many different 10 letter words (real or imaginary) can be formed from the following letters

H,T,G,B,X,X,T,L,N,J.Is every straight line the graph of a function?

For the 1s orbital of the Hydrogen atom, the radial wave function is given as: $R(r)=\frac{1}{\sqrt{\pi}}(\frac{1}{{a}_{O}}{)}^{\frac{3}{2}}{e}^{\frac{-r}{{a}_{O}}}$ (Where ${a}_{O}=0.529$ ∘A)

The ratio of radial probability density of finding an electron at $r={a}_{O}$ to the radial probability density of finding an electron at the nucleus is given as ($x.{e}^{-y}$). Calculate the value of (x+y).Find the sets $A$ and $B$ if $\frac{A}{B}=\left(1,5,7,8\right),\frac{B}{A}=\left(2,10\right)$ and $A\cap B=\left(3,6,9\right)$. Are they unique?

What are the characteristics of a good hypothesis?

If x is 60% of y, find $\frac{x}{y-x}$.

A)$\frac{1}{2}$

B)$\frac{3}{2}$

C)$\frac{7}{2}$

D)$\frac{5}{2}$The numbers of significant figures in $9.1\times {10}^{-31}kg$ are:

A)Two

B)Three

C)Ten

D)Thirty oneWhat is positive acceleration?

Is power scalar or vector?

What is the five-step process for hypothesis testing?

How to calculate Type 1 error and Type 2 error probabilities?

How long will it take to drive 450 km if you are driving at a speed of 50 km per hour?

1) 9 Hours

2) 3.5 Hours

3) 6 Hours

4) 12.5 HoursWhat is the square root of 106?