_Number of nonnegative integral solutions to equation
qsymmetry
x_1 + x_2 + x_3 + x_4 + x_5 = 30
It would seem as though we'd, at least, need to count
the number of partitions of 30 into 5 'nonnegative parts, i.e. tuples (x_1, ..., x_5) s.t.
30 = \sum_i x_i where x_1 =>...= > x_5.
This becomes a little unwieldy after a while.
I would appreciate any suggestions at this time (or a completely different line of attack).
Thank you.
Robert Israel
> I want to show that there are 46, 376 solutions in non-negative integers
> to the following equation
>
> x_1 + x_2 + x_3 + x_4 + x_5 = 30
>
Hint:
Let F_n(x) be the number of non-negative integer solutions of
x_1 + x_2 + ... + x_n = x.
Then F_1(x) = 1 for all non-negative integers x, and
F_n(x) = sum_{j=0}^x F_{n-1}(j).
Look for a simple formula.
--
Robert Israel isr...@math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
Mike Terry
news:1670837832.24734.12589...@gallium.mathforum.org...
This is equivalent to assigning 30 balls into 5 distinguishable boxes, so
that each box contains at least one ball.
The secret is to number each of the balls, and number each of the boxes,
then assign the balls to the boxes in order. Note that the 1st ball has to
go into the 1st box. Observe which balls are the first to go into each of
the other boxes.
(BTW, I don't get the answer 46376...)
Mike.
Mike Terry
news:RJudnVgYOfNsW5fW...@brightview.co.uk...
Sorry - I'd missed the restriction x_1 =>...= > x_5
This complicates my approach so it's probably not going to be any use!
Mike.
Mike Terry
Umm, sorry - please ignore my last post, upon closer reading I see there is
no such restriction, so my original post is OK - phew! :)
Ray Vickson
<news.dead.person.sto...@darjeeling.plus.com> wrote:
> "Mike Terry" <news.dead.person.sto...@darjeeling.plus.com> wrote in message
>
> news:RJudnVgYOfNsW5fW...@brightview.co.uk...
>
>
>
> > "qsymmetry" <qsymme...@email.com> wrote in message
> >news:1670837832.24734.12589...@gallium.mathforum.org...
> > > I want to show that there are 46, 376 solutions in non-negative
> integers
> > to the following equation
>
> > > x_1 + x_2 + x_3 + x_4 + x_5 = 30
>
> > > It would seem as though we'd, at least, need to count
> > > the number of partitions of 30 into 5 'nonnegative parts, i.e. tuples
> > (x_1, ..., x_5) s.t.
>
> > > 30 = \sum_i x_i where x_1 =>...= > x_5.
>
> > > This becomes a little unwieldy after a while.
>
> > > I would appreciate any suggestions at this time (or a completely
> different
> > line of attack).
>
> > > Thank you.
>
> > This is equivalent to assigning 30 balls into 5 distinguishable boxes, so
> > that each box contains at least one ball.
He said he wanted non-negative solutions, so some boxes are allowed to
be empty.
>
> > The secret is to number each of the balls, and number each of the boxes,
> > then assign the balls to the boxes in order. Note that the 1st ball has
> to
> > go into the 1st box. Observe which balls are the first to go into each of
> > the other boxes.
>
> Sorry - I'd missed the restriction x_1 =>...= > x_5
> This complicates my approach so it's probably not going to be any use!
His original statement of the problem did not have the requirement x_1
=>...= > x_5.
R.G. Vickson
Arturo Magidin
> I want to show that there are 46, 376 solutions in non-negative integers to the following equation
>
> x_1 + x_2 + x_3 + x_4 + x_5 = 30
>
> It would seem as though we'd, at least, need to count
> the number of partitions of 30 into 5 'nonnegative parts, i.e. tuples (x_1, ..., x_5) s.t.
>
> 30 = \sum_i x_i where x_1 =>...= > x_5.
It seems this has generated some confusion. I interpreted it as
meaning that you were looking for the partitions of 30 of length at
most 5, with the condition on the x_i given so that you are counting
partitions. Others have interpreted your "at least" above to mean that
the original problem does *not* restrict itself to partitions, so that
the solutions (10,9,8,2,1) would count as a "different" solution to
(9,10,2,1,8).
If this is the case (a permutation of the solution counts as
different), then you want to count the number of ways of distributing
30 undistintiguishable objects into 5 distinguishable containers, with
repetitions allowed. This is again a combinations-with-repetitions
problem, so the answer is C(30+5-1,30), which gives the answer you
provide.
It seems you are doing a lot of exercises that come down to counting
combinations-with-repetitions. Do you know a proof of the formula I've
mentioned?
--
Arturo Magidin
Mike Terry
news:RJudnVgYOfNsW5fW...@brightview.co.uk...
> "qsymmetry" <qsym...@email.com> wrote in message
> news:1670837832.24734.12589...@gallium.mathforum.org...
> > I want to show that there are 46, 376 solutions in non-negative
integers
> to the following equation
> >
> > x_1 + x_2 + x_3 + x_4 + x_5 = 30
> >
> >
> > It would seem as though we'd, at least, need to count
> > the number of partitions of 30 into 5 'nonnegative parts, i.e. tuples
> (x_1, ..., x_5) s.t.
> >
> > 30 = \sum_i x_i where x_1 =>...= > x_5.
> >
> >
> > This becomes a little unwieldy after a while.
> >
> > I would appreciate any suggestions at this time (or a completely
different
> line of attack).
> >
> > Thank you.
>
> This is equivalent to assigning 30 balls into 5 distinguishable boxes, so
> that each box contains at least one ball.
Ray has pointed out that your x_i can be zero, i.e. in my ball analogy it's
OK for the boxes to be empty.
That's OK - my approach still works, but you have to add in 4 "separator"
balls which are subsequently taken out again. (In fact this is easier to
understand than the version of the problem I was considering.)
>
> The secret is to number each of the balls, and number each of the boxes,
> then assign the balls to the boxes in order. Note that the 1st ball has
to
> go into the 1st box. Observe which balls are the first to go into each of
> the other boxes.
>
> (BTW, I don't get the answer 46376...)
My approach gives this answer now I understand boxes can be empty...
Mike.
Gerry Myerson
<1670837832.24734.12589...@gallium.mathforum.org>,
qsymmetry <qsym...@email.com> wrote:
> I want to show that there are 46, 376 solutions in non-negative integers to
> the following equation
>
> x_1 + x_2 + x_3 + x_4 + x_5 = 30
Here are 34 objects:
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Choose 4 of them and change them from x to some other symbol.
Can you see how the new array corresponds to a solution of your
equation?
--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)
Ray Vickson
Take Robert Israel's suggestion: let f_k(n) = number of non-neg
solutions to x_1 + ... + x_k = n and let g_k(z) = moment-generating
function (mgf) of {f_k(0),f_k(1),f_k(2),...}. We have f_1(n) = n+1 for
all n >= 0 so g_1(z) = 1/(1-z)^2. Now f_{k+1}(n) = sum{f_k(j),j=0..n}
implies g_{k+1}(z) = g_k(z)/(1-z) [standard property of mgs's], hence
g_k(z) = 1/(1-z)^(k+1) = (1-z)^(-k-1). Expand using the Binomial to
get f_k(n) = (-1)^n * C(-k,n) = C(n+k,k) = (n+1)(n+2)...(n+k)/k!.
R.G. Vickson
Achava Nakhash, the Loving Snake
You might want to take a look at the book Mathematics of Choice by
Ivan Niven. The discussion of the problem with positive x_1 starts on
page 54, and the solutions for nonnegative x_i are covered starting on
page 55. The ultimate proof of the more general result of any number
of variables and any number that they sum to is remarkably easy, once
you look at the problem the right way.
Regads,
Achava
Regards,
Achava
sttsc...@tesco.net
> I want to show that there are 46, 376 solutions in non-negative integers to the following equation
>
> x_1 + x_2 + x_3 + x_4 + x_5 = 30
>
> It would seem as though we'd, at least, need to count
> the number of partitions of 30 into 5 'nonnegative parts, i.e. tuples (x_1, ..., x_5) s.t.
>
> 30 = \sum_i x_i where x_1 =>...= > x_5.
You seem to be ordering the solutions, but to get the answer
you want you would have to treat (2,28,0,0,0) as a different solution
to (28,2,0,0,0)
If you consider the product
(1 + x + x^2 +x ^3 +..+ x^n +.)^5 = (1-x)-5
The coefficient of x^30 is the number of solutions you want.
(1 + x + x^2 +x ^3 +..+ x^n +.) = (1-x)-1
Differentiate 4 times
..+nx^(n-1)+ ... = (1-x)-2
..+n(n-1)x^(n-2)+ ... = 2(1-x)-3
..+n(n-1)(n-2)x^(n-3)+ ... = 2x3(1-x)-4
..+n(n-1)(n-2)(n-3)x^(n-4)+ ... = 2x3x4(1-x)-5
etc. which gives your answer.