3
$\begingroup$

Can anyone help me out finding the number of solutions i.e. $(x,y,z)$ for the inequality $x+y+z\leq n$ where, $n$ is a constant positive value and $x,y,z$ are non-negative?

$\endgroup$
3
$\begingroup$

You have $n$ identical candies, and want to give out "some" (possibly none), up to possibly $n$, among three kids X, Y, and Z. So you might be "giving" some of the candies to yourself. Invent a fourth variable $w$ for the number of candies you give to yourself.

Then the number of ways to carry out the task of the OP is the number of solutions of $$x+y+z+w=n\tag{1}$$ in non-negative integers.

By a standard Stars and Bars argument (please see Wikipedia) the number of solutions of (1) is $\binom{n+4-1}{4-1}$, or equivalently $\binom{n+4-1}{n}$.

$\endgroup$
  • $\begingroup$ The sequence what you gave is this, but it is not a solution for the problem. What we need is this. $\endgroup$ – user153012 Sep 5 '14 at 21:43
1
$\begingroup$

Hint Count the disjoint sets of points for which $x+y+z=k$, for $k=0,\ldots,n$.

$\endgroup$
0
$\begingroup$

The solution for $n= 1$ to $50$ is

$0, 0, 1, 2, 4, 7, 11, 16, 23, 31, 41, 53, 67, 83, 102, 123, 147, 174, 204, 237, 274, 314, 358, 406, 458, 514, 575, 640, 710, 785, 865, 950, 1041, 1137, 1239, 1347, 1461, 1581, 1708, 1841, 1981, 2128, 2282, 2443, 2612, 2788, 2972, 3164, 3364, 3572.$


I solved it with Maple. I could write also pseudocodes, but I will give you my solution implemented in Maple.

First of all we need the combinat package.

with(combinat);

After that we have to know that the partition function (from combinat package) give us the partition of an arbitrary nonnegative integer number.

Now we define partition_3 function, which will give us the list of partitions of an arbitrary nonnegative integer number with exactly three elements.

partition_3 := proc(n)
 local L,K,i;
 L:=partition(n);
 K:=[];
 for i from 1 to nops(L) do
  if nops(L[i])=3 then
   K:=[op(K),L[i]];
  fi;
 od;
 K;
end proc;

Now we define an f function to count elements in the lists and sum them up.

f := proc(n)
local K,i;
 K:=[];
 for i from 0 to n do
  K:=[op(K),partition_3(i)];
 od;
 add(nops(K[i]),i=1..nops(K));
end proc;

Now for example for $f(50)$ we get $3572$ and this is exactly what we wanted.


Some fun fact about the problem. According to OEIS A000601 this numbers from $n=3$ are the coefficients of the following expansion.

$$\frac{1}{\left(1-x\right)^2\left(1-x^2\right)\left(1-x^3\right)}=1+2x+4x^2+7x^3+11x^4+16x^5+23x^6+31x^7+\dots$$

Furthermore, I have the feeling that the OEIS A181120 is the same sequence. So we can conjecture a closed-form: $$a_n=\left\lfloor \frac{1}{36}n^3 + \frac{1}{24}n^2 -\frac{1}{12}n +\frac18 \right\rfloor$$

I tested with Maple and for $n=1$ to $50$ it gives the same solution.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.