2

I have 4 objects in group A and 4 objects in group B.

One by one I need to add the 8 objects from the two different groups in a line.

But the condition is that as the line is being created, the amount of "A" objects is always >= the amount of "B" objects.

What I have 4 objects in group A and 4 objects in group B.

One by one I need to add the 8 objects from the two different groups in a line.

But the condition is that as the line is being created, the amount of "A" objects is always >= the amount of "B" objects.

I need to count the total number of possible arrangements

What theorem or concept should I use? or concept should I use?

RobPratt
  • 45,619
Sabas
  • 75
  • 1
    So reading left to right, AABBABAB is OK, yes? But BAAAABBB is not, because after the first step, the B count is greater than the A count. Have I got this right? – John Hughes Jan 27 '20 at 02:40
  • 1
    One more thing...are you trying to count the total number of possible arrangements that satisfy these requirements? If all you need is AN arrangement, then the one in my previous comment suffices as does AAAABBBB, – John Hughes Jan 27 '20 at 02:42
  • 1
    One more thing...are you trying to count the total number of possible arrangements that satisfy these requirements? If all you need is AN arrangement, then the one in my previous comment suffices as does AAAABBBB, – John Hughes Jan 27 '20 at 02:42
  • I apologize, I need the total count, the total number of possible arrangements. – Sabas Jan 27 '20 at 02:43
  • yes @JohnHughes thats right – Sabas Jan 27 '20 at 02:44

2 Answers2

2

This is one of the many things counted by the Catalan numbers $\frac{1}{n+1}\binom{2n}{n}$. In particular, $n=4$ yields $\frac{1}{5}\binom{8}{4}=14$. Explicitly, the arrangements are:

  1. AAAABBBB
  2. AAABABBB
  3. AAABBABB
  4. AAABBBAB
  5. AABAABBB
  6. AABABABB
  7. AABABBAB
  8. AABBAABB
  9. AABBABAB
  10. ABAAABBB
  11. ABAABABB
  12. ABAABBAB
  13. ABABAABB
  14. ABABABAB

More generally, if the counts of the two objects can be different, this is the ballot problem.

RobPratt
  • 45,619
1

This can also be posed as counting the number of unilateral walks of type $n$; that is, strings of $n$ '$+1$'s and $n$ '$-1$'s whose partial sum is never negative. Let $w(n)$ be the number of such walks. Furthermore, let $2k$ be the number of steps at which the walk first returns to the starting point. Such a walk looks like $$ \left<+1\right>\left<\text{walk of type $k-1$}\right>\left<-1\right>\left<\text{walk of type $n-k$}\right> $$ Thus, we get the recurrence $$ w(n)=\sum_{k=1}^nw(k-1)w(n-k) $$ In the answer cited, Generating Functions are used to compute $$ w(n)=\frac1{n+1}\binom{2n}{n} $$ which is the $n^\text{th}$ Catalan number.

robjohn
  • 345,667