Binomial coefficients galore

N = a = 0 50 b = 0 a c = 0 a d = 0 50 a e = 0 c + d f = 0 50 a d ( 50 a ) ( a b ) ( a c ) ( 50 a d ) ( c + d e ) ( 50 a d f ) . N = \sum_{a=0}^{50} \sum_{b=0}^a \sum_{c=0}^a \sum_{d=0}^{50-a} \sum_{e = 0}^{c+d} \sum_{f = 0}^{50-a-d} \binom{50} a \binom a b \binom a c \binom {50 - a} d \binom {c + d} e \binom {50-a-d} f. How many digits does N N have?


Inspiration


The answer is 51.

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.

3 solutions

Arjen Vreugdenhil
Jan 14, 2018

We interpret each sum k = 0 n ( n k ) \sum_{k=0}^n \binom n k as choosing an arbitrary number k k out of n n items of a set, and counting in how many ways that may be done. Extending this idea gives an interpretation for the value of N N : Consider a collection of 50 sheets of paper, which are initially blank.

First, choose a a out of these 50 sheets and draw a circle on each of them.

Of the a a sheets with a circle, pick b b and draw a square on each of them.

Of the a a sheets with a circle, pick c c and draw a triangle on each of them.

Of the 50 a 50 - a sheets without a circle, pick d d and draw an semicircle on each of them.

Of the c c sheets with a triangle and the d d sheets with a semicircle, pick e e and draw a star on each of them.

Of the 50 a d 50 - a - d sheets without circle or semicircle, pick f f sheets and draw a dot on them.

After this process, each of the 50 sheets belongs to precisely one of the following categories:

  • only a circle

  • a circle and a square

  • a circle and a triangle

  • a circle, a triangle, and a star

  • a circle, a square, and a triangle

  • a circle, a square, a triangle, and a star

  • only a semicircle

  • a semicircle and a star

  • only a dot

  • blank

Since each of the 50 sheets belongs to precisely one out of 10 categories, there are N = 1 0 50 N = 10^{50} ways of making these choices. This number has 51 \boxed{51} digits.

Mark Hennings
Jan 15, 2018

For any a , d 0 a,d \ge 0 we have b = 0 a c = a a e = 0 c + d ( a b ) ( a c ) ( c + d e ) = b = 0 a c = 0 a ( a b ) ( a c ) 2 c + d = 2 a × 3 a × 2 d = 6 a × 2 d \sum_{b=0}^a \sum_{c=a}^a \sum_{e=0}^{c+d} \binom{a}{b}\binom{a}{c}\binom{c+d}{e} \; = \; \sum_{b=0}^a \sum_{c=0}^a\binom{a}{b}\binom{a}{c}2^{c+d} \; = \; 2^a \times 3^a \times 2^d \; = \; 6^a \times 2^d and hence N = a + d + f 50 50 ! a ! d ! f ! ( 50 a d f ) ! × 6 a × 2 d = ( 6 + 2 + 1 + 1 ) 50 = 1 0 50 N \; = \; \sum_{a+d+f \le 50} \frac{50!}{a!\, d! \, f! \, (50-a-d-f)!} \times 6^a \times 2^d \; = \; (6 + 2 + 1 + 1)^{50} \; = \; 10^{50} which has 51 \boxed{51} digits.

Jon Haussmann
Jan 15, 2018

By repeated use of the Binomial Theorem, a = 0 50 b = 0 a c = 0 a d = 0 50 a e = 0 c + d f = 0 50 a d ( 50 a ) ( a b ) ( a c ) ( 50 a d ) ( c + d e ) ( 50 a d f ) = a = 0 50 b = 0 a c = 0 a d = 0 50 a e = 0 c + d ( 50 a ) ( a b ) ( a c ) ( 50 a d ) ( c + d e ) 2 50 a d = a = 0 50 b = 0 a c = 0 a d = 0 50 a ( 50 a ) ( a b ) ( a c ) ( 50 a d ) 2 c + d 2 50 a d = a = 0 50 b = 0 a c = 0 a d = 0 50 a ( 50 a ) ( a b ) ( a c ) ( 50 a d ) 2 50 + c a = a = 0 50 b = 0 a c = 0 a ( 50 a ) ( a b ) ( a c ) 2 50 a 2 50 + c a = a = 0 50 b = 0 a c = 0 a ( 50 a ) ( a b ) ( a c ) 2 100 + c 2 a = a = 0 50 b = 0 a ( 50 a ) ( a b ) 2 100 2 a c = 0 a ( a c ) 2 c = a = 0 50 b = 0 a ( 50 a ) ( a b ) 2 100 2 a 3 a = a = 0 50 ( 50 a ) 2 a 2 100 2 a 3 a = a = 0 50 2 100 a 3 a = 2 50 a = 0 50 2 50 a 3 a = 2 50 5 50 = 1 0 50 , \begin{aligned} &\sum_{a = 0}^{50} \sum_{b = 0}^a \sum_{c = 0}^a \sum_{d = 0}^{50 - a} \sum_{e = 0}^{c + d} \sum_{f = 0}^{50 - a - d} \binom{50}{a} \binom{a}{b} \binom{a}{c} \binom{50 - a}{d} \binom{c + d}{e} \binom{50 - a - d}{f} \\ &= \sum_{a = 0}^{50} \sum_{b = 0}^a \sum_{c = 0}^a \sum_{d = 0}^{50 - a} \sum_{e = 0}^{c + d} \binom{50}{a} \binom{a}{b} \binom{a}{c} \binom{50 - a}{d} \binom{c + d}{e} 2^{50 - a - d} \\ &= \sum_{a = 0}^{50} \sum_{b = 0}^a \sum_{c = 0}^a \sum_{d = 0}^{50 - a} \binom{50}{a} \binom{a}{b} \binom{a}{c} \binom{50 - a}{d} 2^{c + d} \cdot 2^{50 - a - d} = \sum_{a = 0}^{50} \sum_{b = 0}^a \sum_{c = 0}^a \sum_{d = 0}^{50 - a} \binom{50}{a} \binom{a}{b} \binom{a}{c} \binom{50 - a}{d} 2^{50 + c - a} \\ &= \sum_{a = 0}^{50} \sum_{b = 0}^a \sum_{c = 0}^a \binom{50}{a} \binom{a}{b} \binom{a}{c} 2^{50 - a} \cdot 2^{50 + c - a} = \sum_{a = 0}^{50} \sum_{b = 0}^a \sum_{c = 0}^a \binom{50}{a} \binom{a}{b} \binom{a}{c} 2^{100 + c - 2a} \\ &= \sum_{a = 0}^{50} \sum_{b = 0}^a \binom{50}{a} \binom{a}{b} 2^{100 - 2a} \sum_{c = 0}^a \binom{a}{c} 2^c = \sum_{a = 0}^{50} \sum_{b = 0}^a \binom{50}{a} \binom{a}{b} 2^{100 - 2a} \cdot 3^a \\ &= \sum_{a = 0}^{50} \binom{50}{a} 2^a \cdot 2^{100 - 2a} \cdot 3^a = \sum_{a = 0}^{50} 2^{100 - a} \cdot 3^a \\ &= 2^{50} \sum_{a = 0}^{50} 2^{50 - a} \cdot 3^a = 2^{50} \cdot 5^{50} = 10^{50}, \end{aligned} which has 51 digits.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...