Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: integer solutions for x_1+x_2+...+x_n = k
Date: Mon, 3 Nov 2008 19:09:02 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 28
Message-ID: <geni8e$ajn$1@fred.mathworks.com>
References: <geku21$eku$1@fred.mathworks.com> <gel0b6$3li$1@fred.mathworks.com> <gelbfg$72h$1@fred.mathworks.com> <gelf99$84m$1@fred.mathworks.com> <gemb7o$hib$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1225739342 10871 172.30.248.37 (3 Nov 2008 19:09:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Mon, 3 Nov 2008 19:09:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:498718


"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gemb7o$hib$1@fred.mathworks.com>...
> "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gelf99$84m$1@fred.mathworks.com>...
> >   In general the total number of solutions is (k+n-1)!/k!/(n-1)! 

> Hi Roger,
> what is your way to derive this formula ?
> Bruno

Hi Bruno,

  Probably the easiest way is to use mathematical induction.  Let P(n) be the proposition that the number of solutions for n non-negative integers with a sum of k is equal to

 (k+n-1)!/k!/(n-1)!

for all non-negative integers k.  It is obvious that this is true for n = 1 since there is clearly only one possible solution in that case.  Suppose that it holds for n = N.  Then we try to prove it for n = N+!.  The value of the last (the N+1 st) term may be any integer value j from j = 0 to j = k.  The remaining terms must then have a sum of k-j and by our inductive hypothesis there are

 (j+N-1)!/j!/(N-1)!

solutions for that j.  The sum of all of these,

 sum, j = 0 to k, of (j+N-1)!/j!/(N-1)! ,

is identically equal to (k+N)!/k!/N! which proves P(N+1).  This establishes the proposition P(n) for all integers n.

  This last sum equality is a known identity about the sum in a Pascal triangle along a diagonal and can be easily be proved using a further mathematical induction on k.

Roger Stafford