∑ 1 0 ≤ a ≤ b ≤ c ≤ d ≤ e ≤ f ≤ g ≤ 8
Find the sum over all ordered tuples of integers.
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.
That one was pretty neat.
I viewed this as a balls-in-urns problem using the same logic as your final paragraph.
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 :}
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?
Log in to reply
n+1 ? nd the pge is till not there sir :}
The given connected summation can be divided into following summations :
Along with inequality , consider permutations of:
0 equality b/w a and g
1 equality b/w a and g
2 equalities b/w a and g
3 equalities b/w a and g
4 equalities b/w a and g
5 equalities b/w a and g
6 equalities b/w a and g
Adding the above cases we get,
( 7 9 ) + ( 6 × ( 6 9 ) ) + ( 1 5 × ( 5 9 ) ) + ( 2 0 × ( 4 9 ) ) + ( 1 5 × ( 3 9 ) ) + ( 6 × ( 2 9 ) ) + ( 1 9 ) = 6 4 3 5
⇒ A n s : 6 4 3 5 ⌣ ¨
P.S. I am not good at explaining.
First I am going to prove the Hockey-Stick identity.
Lemma:
(
r
r
)
+
(
r
r
+
1
)
+
(
r
r
+
2
)
+
…
(
r
n
)
=
(
r
+
1
n
+
1
)
Proof :
(
r
r
)
=
(
r
+
1
r
+
1
)
L
.
H
S
=
(
r
r
)
+
(
r
r
+
1
)
+
(
r
r
+
2
)
+
…
(
r
n
)
=
(
r
+
1
r
+
1
)
+
(
r
r
+
1
)
+
(
r
r
+
2
)
+
…
(
r
n
)
Using the property,
(
m
n
)
+
(
m
−
1
n
)
=
(
m
n
+
1
)
L
.
H
.
S
=
(
r
+
1
r
+
2
)
+
(
r
r
+
2
)
+
…
(
r
n
)
=
(
r
+
1
r
+
3
)
+
…
(
r
n
)
Using this repeatedly we get,
L
.
H
.
S
=
(
r
+
1
n
+
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
=
g
=
0
∑
8
f
=
0
∑
g
e
=
0
∑
f
d
=
0
∑
e
c
=
0
∑
d
b
=
0
∑
c
(
b
+
1
)
b
=
0
∑
c
(
b
+
1
)
the sum of first
(
c
+
1
)
integers and is given by
2
(
c
+
1
)
(
c
+
2
)
=
(
2
c
+
2
)
∴
S
=
g
=
0
∑
8
f
=
0
∑
g
e
=
0
∑
f
d
=
0
∑
e
c
=
0
∑
d
(
2
c
+
2
)
Now using our lemma,
∴
S
=
g
=
0
∑
8
f
=
0
∑
g
e
=
0
∑
f
d
=
0
∑
e
(
3
d
+
3
)
S
=
g
=
0
∑
8
f
=
0
∑
g
e
=
0
∑
f
(
4
e
+
4
)
S
=
g
=
0
∑
8
f
=
0
∑
g
(
5
f
+
5
)
S
=
g
=
0
∑
8
(
6
g
+
6
)
S
=
(
7
8
+
7
)
=
(
7
1
5
)
∴
S
=
7
!
8
!
1
5
!
=
6
4
3
5
I know there's a better combinatoric approach, I just preferred the algebraic one!
Yes, the hockey stick identity is the way for this summation to telescope.
Problem Loading...
Note Loading...
Set Loading...
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 .
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 ( 7 1 5 ) × 1 = 6 4 3 5 .