MATHEMATICS
PROBLEM 129
a.
How many
sequences of ten positive integers have a sum less than or equal to a
thousand?
b. How many sequences of ten
nonnegative integers have a sum less than or equal to a
thousand?
(For example, 210 sequences of four positive integers
have a sum less than or equal to ten.
Three examples of such sequences are (1,2,5,2), (2,2,5,1), and
(1,2,3,4).)
Hint:
Similar to Math Prob 128 – see solution on
back!
Each midshipman submitting a correct solution with a
correct explanation to part a or to part b
of Problem 129 by 1700 Friday 28 February 2003 will win a cookie. (Two cookies for both a
and b!) Submit solutions to Prof. Wardlaw at
mathprob@usna.edu (please no attachments!) or via his mailbox in Chauvenet
301.
A correct solution to Mathematics Problem 128 was submitted by Prof. Craig Bailey. His solution is posted on the board. The problem is a classical combinatorics question and many solutions appear in the literature.
My solution is on the back and on the board.
Mathematics Problem
128
a.
How many
sequences of ten positive integers sum to a
thousand?
b.
How many
sequences of ten nonnegative integers sum to a
thousand?
(For example, 84 sequences of four positive integers sum
to ten. Three examples of such
sequences are (1,2,5,2), (2,2,5,1),
and (1,2,3,4).)
Solution. a.
Consider the general problem:
How many sequences 
of
positive integers have sum 
?
This is clearly the number of ways we can put balls (or counters) in boxes while leaving no box
empty. If we line all balls up in a single row, we can
choose how many balls go into each of the
boxes by laying 
sticks in spaces chosen among
the 
spaces between the balls. (For 
,
the sequences (1,2,5,2),
(2,2,5,1), and (1,2,3,4) are given
by “ball and stick” diagrams
·|··|·····|·· ,
··|··|·····|· ,
·|··|···|···· , respectively.)
There are “
choose ” ways to do this. Thus there are C(s-1,k-1) = (s-1)!/((s-k)!(k-1)!)
sequences of k positive integers which sum to s.
Thus, there are C(9,3) =
9x8x7/(3x2x1) = 84 sequences of
four positive integers which sum to ten and C(999,9) = 999x998x…x991/(9x8x…x1) =
2634095604619702128324 sequences of
ten positive integers which sum to 1000.
b. Consider the general
problem: How many sequences 
of
nonnegative integers have sum ?
We can convert this problem to the positive integer problem in part a
by taking 
and
replacing by 
.
Hence thare are C(s+k-1,k-1)
= (s+k-1)!/((s)!(k-1)!) sequences of
k nonnegative integers which
sum to s. Thus there are C(1009,9) = 1009x1008x…x1001/(9x8x…x1) =
2882163562453289940826 sequences of
ten nonnegative integers which sum to 1000.