Summation over 7 variables? Piece of Cake.

1 0 a b c d e f g 8 \Large \sum { 1 } \\ 0\le a\le b\le c\le d\le e\le f\le g\le 8

Find the sum over all ordered tuples of integers.


The answer is 6435.

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

Calvin Lin Staff
Jan 8, 2016

The question is asking for the number of non-decreasing sequences of 7 numbers from 0 to 8.
Define A = a + 1 , B = b + 2 , C = c + 3 , , G = g + 7 A = a + 1, B = b + 2, C = c + 3, \ldots, G = g + 7 .
This transforms a non-decreasing sequence of 7 numbers from 0 to 8, to a strictly increasing sequence of 7 numbers from 1 to 15.

How many ways are there to pick a strictly increasing sequence of 7 number out of 15? Well, if we were to choose any 7 numbers, then there is a unique arrangement into an increasing sequence. Hence, the answer is ( 15 7 ) × 1 = 6435 { 15 \choose 7 } \times 1 = 6435 .

That one was pretty neat.

Kunal Verma - 5 years, 4 months ago

I viewed this as a balls-in-urns problem using the same logic as your final paragraph.

Trevor B. - 5 years, 4 months ago

how do you get to know The question is asking for the number of non-decreasing sequences of 7 numbers from 0 to 8 ? pl. tell sir :}

A Former Brilliant Member - 4 years, 4 months ago

Log in to reply

Read up on summation notation .

The condition is exactly "non-decreasing sequences of 7 numbers from 0 to 8". For each of these sequences, what is the contrbution to the count?

Calvin Lin Staff - 4 years, 4 months ago

Log in to reply

n+1 ? nd the pge is till not there sir :}

A Former Brilliant Member - 4 years, 4 months ago
Rachit Shukla
Oct 24, 2015

The given connected summation can be divided into following summations :

Along with inequality , consider permutations of:

0 equality b/w a a and g g

1 equality b/w a a and g g

2 equalities b/w a a and g g

3 equalities b/w a a and g g

4 equalities b/w a a and g g

5 equalities b/w a a and g g

6 equalities b/w a a and g g

Adding the above cases we get,

( 9 7 ) + ( 6 × ( 9 6 ) ) + ( 15 × ( 9 5 ) ) + ( 20 × ( 9 4 ) ) + ( 15 × ( 9 3 ) ) + ( 6 × ( 9 2 ) ) + ( 9 1 ) = 6435 {9 \choose 7}+(6\times{9 \choose 6})+(15\times{9 \choose 5})+(20\times{9 \choose 4})+(15\times{9 \choose 3})+(6\times{9 \choose 2})+{9 \choose 1} = 6435

A n s : 6435 \Rightarrow Ans: 6435 ¨ \ddot\smile

P.S. I am not good at explaining.

With another interpretation, there is a one-line solution to this problem.

Hint: ( 15 8 ) = 6435 { 15 \choose 8 } = 6435 .

Calvin Lin Staff - 5 years, 7 months ago

First I am going to prove the Hockey-Stick identity.
Lemma:
( r r ) + ( r + 1 r ) + ( r + 2 r ) + ( n r ) = ( n + 1 r + 1 ) \dbinom{r}{r} + \dbinom{r+1}{r} + \dbinom{r+2}{r} + \ldots \dbinom{n}{r} = \dbinom{n+1}{r+1}

Proof :
( r r ) = ( r + 1 r + 1 ) \dbinom{r}{r} = \dbinom{r+1}{r+1}
L . H S = ( r r ) + ( r + 1 r ) + ( r + 2 r ) + ( n r ) = ( r + 1 r + 1 ) + ( r + 1 r ) + ( r + 2 r ) + ( n r ) L.HS = \dbinom{r}{r} + \dbinom{r+1}{r} + \dbinom{r+2}{r} + \ldots \dbinom{n}{r} = \dbinom{r+1}{r+1} + \dbinom{r+1}{r} + \dbinom{r+2}{r} + \ldots \dbinom{n}{r}
Using the property,
( n m ) + ( n m 1 ) = ( n + 1 m ) \dbinom{n}{m} + \dbinom{n}{m-1} = \dbinom{n+1}{m}
L . H . S = ( r + 2 r + 1 ) + ( r + 2 r ) + ( n r ) = ( r + 3 r + 1 ) + ( n r ) L.H.S = \dbinom{r+2}{r+1} + \dbinom{r+2}{r} + \ldots \dbinom{n}{r} = \dbinom{r+3}{r+1} + \ldots \dbinom{n}{r}
Using this repeatedly we get,
L . H . S = ( n + 1 r + 1 ) L.H.S = \dbinom{n+1}{r+1}
Q.E.D
Moving on to the question,
The sum can be written as,
S = g = 0 8 f = 0 g e = 0 f d = 0 e c = 0 d b = 0 c a = 0 b 1 S =\displaystyle \sum_{g=0}^{8}\sum_{f=0}^{g}\sum_{e=0}^{f}\sum_{d=0}^{e}\sum_{c=0}^{d}\sum_{b=0}^{c}\sum_{a=0}^{b}1
S = g = 0 8 f = 0 g e = 0 f d = 0 e c = 0 d b = 0 c ( b + 1 ) S = \displaystyle \sum_{g=0}^{8}\sum_{f=0}^{g}\sum_{e=0}^{f}\sum_{d=0}^{e}\sum_{c=0}^{d}\sum_{b=0}^{c}(b+1)
b = 0 c ( b + 1 ) \displaystyle \sum_{b=0}^{c}(b+1) the sum of first ( c + 1 ) (c+1) integers and is given by ( c + 1 ) ( c + 2 ) 2 = ( c + 2 2 ) \dfrac{(c+1)(c+2)}{2} = \dbinom{c+2}{2}
S = g = 0 8 f = 0 g e = 0 f d = 0 e c = 0 d ( c + 2 2 ) \therefore S = \displaystyle \sum_{g=0}^{8}\sum_{f=0}^{g}\sum_{e=0}^{f}\sum_{d=0}^{e}\sum_{c=0}^{d}\dbinom{c+2}{2}
Now using our lemma,
S = g = 0 8 f = 0 g e = 0 f d = 0 e ( d + 3 3 ) \therefore S = \displaystyle \sum_{g=0}^{8}\sum_{f=0}^{g}\sum_{e=0}^{f}\sum_{d=0}^{e}\dbinom{d+3}{3}
S = g = 0 8 f = 0 g e = 0 f ( e + 4 4 ) S = \displaystyle \sum_{g=0}^{8}\sum_{f=0}^{g}\sum_{e=0}^{f}\dbinom{e+4}{4}
S = g = 0 8 f = 0 g ( f + 5 5 ) S =\displaystyle \sum_{g=0}^{8}\sum_{f=0}^{g}\dbinom{f+5}{5}
S = g = 0 8 ( g + 6 6 ) S = \displaystyle \sum_{g=0}^{8}\dbinom{g+6}{6}
S = ( 8 + 7 7 ) = ( 15 7 ) S = \dbinom{8+7}{7} = \dbinom{15}{7}
S = 15 ! 7 ! 8 ! = 6435 \therefore S = \dfrac{15!}{7!8!} = 6435
I know there's a better combinatoric approach, I just preferred the algebraic one!

Moderator note:

Yes, the hockey stick identity is the way for this summation to telescope.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...