Three's a crowd

How many ways can we arrange 10 identical black balls and 10 identical red balls in a line, such that no more than 2 balls of the same color ever appear in a row?


Inspiration .


The answer is 8196.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

4 solutions

Mark Hennings
Feb 8, 2017

Let B m , n B_{m,n} be the number of acceptable sequences containing m m black balls and n n red balls, where the first ball is black, and let R m , n R_{m,n} be the number of acceptable sequences containing m m black balls and n n red balls, where the first ball is red. Then we have B m , 0 = { 1 0 m 2 0 m 3 R 0 , n = { 1 0 n 2 0 n 3 B 0 , n = δ n , 0 R m , 0 = δ m , 0 B 1 , n = R 0 , n R m , 1 = B m , 0 \begin{array}{rclcrcl} B_{m,0} & = & \left\{ \begin{array}{ll} 1 & 0 \le m \le 2 \\ 0 & m \ge 3 \end{array} \right. & \hspace{2cm} & R_{0,n} & = & \left\{ \begin{array}{ll} 1 & 0 \le n \le 2 \\ 0 & n \ge 3 \end{array} \right. \\[2ex] B_{0,n} & = & \delta_{n,0} & & R_{m,0} & = & \delta_{m,0} \\[1ex] B_{1,n} & = & R_{0,n} & & R_{m,1} & = & B_{m,0} \end{array} Moreover we have B m , n = R m 1 , n + R m 2 , n m 2 , n 0 R m , n = B m , n 1 + B m , n 2 m 0 , n 2 \begin{array}{rclcl} B_{m,n} & = & R_{m-1,n} + R_{m-2,n} & \hspace{2cm} & m \ge 2\,,\,n \ge 0 \\[1ex] R_{m,n} & = & B_{m,n-1} + B_{m,n-2} & & m \ge 0\,,\, n \ge 2 \end{array} Consider the generating functions B ( x , y ) = m , n 0 B m , n x m y n R ( x , y ) = m , n 0 R m , n x m y n B(x,y) \; = \; \sum_{m,n \ge 0} B_{m,n}x^m y^n \hspace{2cm} R(x,y) \; = \; \sum_{m,n \ge 0} R_{m,n} x^m y^n Then ( y + y 2 ) B ( x , y ) = m , n 0 B m , n ( x m y n + 1 + x m y n + 2 ) = m 0 , n 1 B m , n 1 x m y n + m 0 , n 2 B m , n 2 x m y n = m 0 , n 2 R m , n x m y n + m 0 B m , 0 x m y = R ( x , y ) m 0 , 0 n 1 R m , n x m y n + ( 1 + x + x 2 ) y = R ( x , y ) 1 ( 1 + x + x 2 ) y + ( 1 + x + x 2 ) y = R ( x , y ) 1 \begin{aligned} (y+y^2)B(x,y) & = \sum_{m,n \ge 0} B_{m,n}\big(x^my^{n+1} + x^my^{n+2}\big) \; = \; \sum_{m \ge 0, n \ge 1} B_{m,n-1} x^my^n + \sum_{m \ge 0,n \ge 2} B_{m,n-2}x^m y^n \\ & = \sum_{m\ge0,n\ge2}R_{m,n}x^my^n + \sum_{m\ge0}B_{m,0}x^my \\ & = R(x,y) - \sum_{m \ge 0,0 \le n \le 1}R_{m,n}x^my^n + (1+x+x^2)y \\ & = R(x,y) - 1 - (1 + x + x^2)y + (1 + x + x^2)y \; = \; R(x,y) - 1 \end{aligned} and, similarly, ( x + x 2 ) R ( x , y ) = B ( x , y ) 1 (x + x^2)R(x,y) \; = \; B(x,y) - 1 Thus we obtain B ( x , y ) = 1 + x + x 2 1 ( x + x 2 ) ( y + y 2 ) R ( x , y ) = 1 + y + y 2 1 ( x + x 2 ) ( y + y 2 ) B(x,y) \; = \; \frac{1 + x + x^2}{1 - (x + x^2)(y + y^2)} \hspace{2cm} R(x,y) \; = \; \frac{1 + y + y^2}{1 - (x + x^2)(y + y^2)} If Z m , n = B m , n + R m , n Z_{m,n} = B_{m,n} + R_{m,n} is the number of acceptable sequences containing m m black balls and n n red balls (starting with either colour), then Z m , n Z_{m,n} is the coefficient of x m y n x^my^n in the series B ( x , y ) + R ( x , y ) = 2 + x + x 2 + y + y 2 1 ( x + x 2 ) ( y + y 2 ) B(x,y) + R(x,y) \; = \; \frac{2 + x + x^2 + y + y^2}{1 - (x + x^2)(y + y^2)} Expanding this series (initially as a double series in x + x 2 x+x^2 and y + y 2 y+y^2 , and then getting our hands dirty), we can evaluate the coefficient of x 10 y 10 x^{10}y^{10} as 8196 \boxed{8196} .


An alternative approach is to note that the black balls must occur in N N blocks, where 5 N 10 5 \le N \le 10 , and that the red balls must occur in M M blocks, where 5 M 10 5 \le M \le 10 . The numbers N , M N,M of blocks of black and red balls must be compatible with each other, in that M N 1 |M-N| \le 1 . Thus the set of possible pairs ( M , N ) (M,N) of block counts is S = { ( 5 , 5 ) , ( 5 , 6 ) , ( 6 , 5 ) , ( 6 , 6 ) , ( 6 , 7 ) , ( 7 , 6 ) , ( 7 , 7 ) , ( 7 , 8 ) , ( 8 , 7 ) , ( 8 , 8 ) , ( 8 , 9 ) , ( 9 , 8 ) , ( 9 , 9 ) , ( 9 , 10 ) , ( 10 , 9 ) , ( 10 , 10 ) } \mathcal{S} \;=\; \left\{ \begin{array}{l} (5,5),(5,6),(6,5),(6,6),(6,7),(7,6),(7,7),(7,8),\\ (8,7),(8,8),(8,9),(9,8),(9,9),(9,10),(10,9),(10,10)\end{array}\right\} The number of acceptable sequences containing N N black blocks and M M red blocks is X N , M = { ( N 10 N ) ( M 10 M ) N M 2 ( N 10 N ) ( M 10 M ) N = M X_{N,M} \; = \; \left\{ \begin{array}{ll} \binom{N}{10-N}\binom{M}{10-M} & N \neq M \\[2ex] 2\binom{N}{10-N}\binom{M}{10-M} & N = M \end{array} \right. To see this, put 1 1 black ball in each of the N N blocks, and then choose which 10 N 10-N of these N N blocks will contain a second black ball. A similar argument applies to the red blocks. When N M N \neq M , the colour with the larger number of blocks must come first, and it is clear that the number of acceptable sequences is X N , M = ( N 10 N ) ( M 10 M ) X_{N,M} = \binom{N}{10-N}\binom{M}{10-M} . If N = M N=M then either colour could occur first, and so we need to double this expression to determine X N , M X_{N,M} .

Elementary computation now tells us that ( N , M ) S X N , M = 8196 \sum_{(N,M) \in \mathcal{S}}X_{N,M} \; = \; 8196

Moderator note:

Generalizing the problem to m m black balls and n n red balls allowed us to easily set up the recurrence relation, compared to considering just m = n m = n black/red balls. This trick of relaxing a constraint is useful when we feel that it is overly / unnecessarily restrictive, and relaxing it could lead to more flexibility.

Once we have a workable recurrence relation, we can they try and for the closed form (Mark), or evaluate sufficient terms to get the numerical answer (Laurent).

Terrific solutions! Thank you for posting them. The second "blocking" solution was how I was proceeding, and you've formalized it in a much cleaner way than I could have. (Having seen your solutions in the past I was actually hoping you were going to post one for this problem. :) )

Brian Charlesworth - 4 years, 4 months ago

Log in to reply

If you want a concrete formula for the number of ways of putting 2 n 2n balls in a line, n n of each, try 2 k = 0 2 u = 0 1 2 n k b = 0 m i n ( u , n 2 k 2 u ) ( n u k ) ! b ! ( b + k ) ! ( u b ) ! ( n b 2 u 2 k ) ! 2\sum_{k=0}^2 \sum_{u=0}^{\lfloor\frac12n\rfloor - k}\; \sum_{b=0}^{\mathrm{min}(u,n-2k-2u)}\frac{(n-u-k)!}{b!(b+k)!(u-b)!(n-b-2u-2k)!} Try putting together a number of dominoes of different shapes: B R B B R B R R B B R R BR \hspace{0.5cm} BBR \hspace{0.5cm} BRR \hspace{0.5cm} BBRR possibly followed by up to 2 2 dominoes of the shape B B Count how many of each type you need to get the right total length 2 n 2n and equal numbers of R and B, and add up the associated multinomials. Then times by 2 2 , since you could have started with R instead of B. In the above sum, k k is the number of B dominoes, b b is the number of BBR dominoes, and u u is the number of BBR and BBRR dominoes together.

On the other hand, simply generalising the blocking argument gives the simpler formula: C n = 2 m = 1 2 n n ( m n m ) 2 + 2 m = 1 2 n n 1 ( m n m ) ( m + 1 n m 1 ) C_n \; = \; 2\sum_{m=\lceil \frac12n\rceil}^n \binom{m}{n-m}^2 + 2\sum_{m=\lceil \frac12n\rceil}^{n-1} \binom{m}{n-m}\binom{m+1}{n-m-1}

Mark Hennings - 4 years, 4 months ago
Laurent Shorts
Feb 21, 2017

Using same notation as Mark Hennings, and as we have R m , n = B n , m R_{m,n}=B_{n,m} by symmetry, we can make a unique function S t ( x ) = B x , t x = R t x , x S_t(x)=B_{x,t-x}=R_{t-x,x} that gives the number of sequences of t t balls that begins with a color present x x times. And thus we have the relation: S t ( x ) = S t 1 ( t x ) + S t 2 ( t x ) S_t(x)=S_{t-1}(t-x)+S_{t-2}(t-x) .

Starting point is S t ( x ) = 0 S_t(x)=0 if x < 0 x<0 or x > t x>t , S 0 ( 0 ) = 1 , S 1 ( 0 ) = 0 , S 1 ( 1 ) = 1 S_0(0)=1,~S_1(0)=0,~S_1(1)=1 .

We're looking for S 20 ( 10 ) = 4 , 098 S_{20}(10)=4,098 . As the sequences can begin with a red or a black ball, we multiply by 2: 2 4 098 = 8 196 2·4\,098=\boxed{8\,196} .


A python program:

def S(t,x):
    if x < 0 or x > t:
        return 0
    if t == 0:
        return 1
    if t == 1:
        return x
    return S(t-1,t-x) + S(t-2,t-x)

print 2*S(20,10)

An Excel formula:

* Not a solution, just an entry so that others can comment on the problem *

This scenario is analogous to a grid path from ( 0 , 0 ) (0,0) to ( 10 , 10 ) (10,10) avoiding any 3 or more consecutive steps either to the right or up. The OEIS entry is here . I used the grid path approach up to n = 5 n = 5 and then accessed OEIS to find the rest of the pattern, but more formally we can use the method outlined here . Any more elegant solutions are welcome.

[Edit: As pointed out by Mark, this comment is not valid because I didn't add the condition of equal balls.]

The approach that I would consider is to set up a recurrence relation for the number of suitable arrangements conditional on the color of the last 2 balls. IE Let A n A_n be the number of arrangments of n n balls that end with B B BB , and B n , C n D n B_n, C_n D_n defined for B R , R B , R R BR, RB, RR respectively. Then we have A n + 1 = C n A_{n+1} = C_n and similar equations, while we want to find A n \sum A_n .

We have a one-step linear recurrence, and can verify that the matrix is diagonalizable with eigenvalues 1 2 ( 1 ± 5 ) , 1 2 ( 1 ± 3 i ) \frac{1}{2} ( 1 \pm \sqrt{5} ), \frac{1}{2} ( -1 \pm \sqrt{3} i) .

Calvin Lin Staff - 4 years, 4 months ago

Log in to reply

But how does this take account of the need for an equal number of red and black balls? The expression A n + B n + C n + D n A_n + B_n + C_n + D_n is the number of sequences of length n n that contain no more than two red or black balls in a row, but such a sequence of length 20 20 does not necessarily have 10 10 red and 10 10 black balls.

Mark Hennings - 4 years, 4 months ago

Log in to reply

Ah true. I didn't account for that condition.

Calvin Lin Staff - 4 years, 4 months ago
Peter Macgregor
Feb 26, 2017

The answer is the coefficient of b 10 r 10 b^{10} r^{10} in 2 ( i = 5 10 ( b + b 2 ) i ( r + r 2 ) i + i = 6 10 ( b + b 2 ) i ( r + r 2 ) ( i 1 ) ) 2\left(\sum_{i=5}^{10}(b+b^2)^{i}(r+r^2)^{i}+\sum_{i=6}^{10}(b+b^2)^{i}(r+r^2)^{(i-1)}\right) .

Once this is granted a computer algebra package can do the work to find the answer 8196 \boxed{8196} .

Explanation.

My idea was to extend the formula for restricted compositions in what I hope is an obvious way (at least for those who understand why the restricted partition formula works!). For the restricted compositions formula see the end of this article

Here are some pointers to help explain the connection.

An acceptable line consists of sections of alternating colour, with one or two balls in each section. There must be no fewer than ten sections (with two balls in each section) and no more than twenty sections (with one ball in each section). This explains the limits in the sums.

The sums inside the large parenthesis refer to lines starting with a black ball, which is why the initial factor of two is needed to find the answer for lines staring with either colour.

The first sum refers to lines with an even number of sections, the second sum to lines with an odd number of sections.

Wow, great approach! I liked how you translated all the conditions in the problem into a polynomial. If we changed the limits of the sums to i = 1 \sum _{i=1} ^\infty , then the coefficient of b m w n b^m w^n would give us the number of arrangements with m m black balls and n n red balls for any m , n m, n .

Pranshu Gaba - 4 years, 3 months ago

Thanks for your comments Pranshu.

I particularly liked your observation that my solution is easily generalised by pushing the limits down to 1 and up to \infty . The answer can be generalised in another direction as well. If, for instance, each black section can contain two or three balls, and each red section can contain one or four balls, then the brackets in the sums become ( b 2 + b 3 ) (b^2+b^3) and ( r + r 4 ) (r+r^4) .

Peter Macgregor - 4 years, 3 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...