1
$\begingroup$

Question 1. Find all non-negative integer a, b, c,d, e such that $$ a+b+c+d+e = 8$$


Question 2. Find all non-negative integer a, b, c,d such that $$ a+b+c+d = 8$$


Question 3. Find all non-negative integer a, b, c such that $$a+b+c = 8$$


Is there any method for this? I have no idea. I can just fix the limit. Thanks!

I think must calculate on Maple or Sage math program. I hope that that someone can help.

Thanks!

$\endgroup$
1
$\begingroup$

The problem is asking to find all the partitions (with a specified number of parts).

You want to partition the number 8 in 5, 4, and 3 pieces, so the answer is in the section "Restricted part size or number of parts" of that wikipedia page.

Here is a maple example

$\endgroup$
  • $\begingroup$ While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - From Review $\endgroup$ – TheGeekGreek Feb 11 '17 at 11:48
  • $\begingroup$ I wanted to make a comment. The problem is which I need 50 reputation to make a comment, and I do not have the reputation, so I was obligated to write the links as answers. $\endgroup$ – zugatevej Feb 11 '17 at 12:37
1
$\begingroup$

Hint: for any type of problem see how many ways you can put the number of plus signs thinking it as a divider in the set of $n$ points.

Let us take the first problem. Here you have $4$ plus signs and have $8$ dots. So the total number of possibility is $$\binom{8+5-1}{5-1}$$

and the resulting 4 groups of dots will then correspond to the $4$ variables you reqd.

$\endgroup$
1
$\begingroup$

The number of nonnegative integer solutions of $x_1 + x_2 + \cdots + x_n = 8$ is the coefficient of $t^8$ in the following generating function [JDL]

$$\dfrac{1}{(1-t)^n}$$

Using SymPy:

>>> from sympy import *
>>> t = Symbol('t')
>>> f1 = 1 / (1-t)**5
>>> f2 = 1 / (1-t)**4
>>> f3 = 1 / (1-t)**3
>>> f1.series(t,0,9)
1 + 5*t + 15*t**2 + 35*t**3 + 70*t**4 + 126*t**5 + 210*t**6 + 330*t**7 + 495*t**8 + O(t**9)
>>> f2.series(t,0,9)
1 + 4*t + 10*t**2 + 20*t**3 + 35*t**4 + 56*t**5 + 84*t**6 + 120*t**7 + 165*t**8 + O(t**9)
>>> f3.series(t,0,9)
1 + 3*t + 6*t**2 + 10*t**3 + 15*t**4 + 21*t**5 + 28*t**6 + 36*t**7 + 45*t**8 + O(t**9)

Hence, if, say, $n=5$, there should be $495$ solutions. Brute-forcing in Haskell:

Prelude> let tuples = [ (x1,x2,x3,x4,x5) | x1 <- [0,1..8], x2 <- [0,1..8], x3 <- [0,1..8], x4 <- [0,1..8], x5 <- [0,1..8] ] 
Prelude> filter (\(x1,x2,x3,x4,x5)->(x1+x2+x3+x4+x5==8)) tuples
[(0,0,0,0,8),(0,0,0,1,7),(0,0,0,2,6),(0,0,0,3,5),(0,0,0,4,4),(0,0,0,5,3),(0,0,0,6,2),(0,0,0,7,1),(0,0,0,8,0),(0,0,1,0,7),(0,0,1,1,6),(0,0,1,2,5),(0,0,1,3,4),(0,0,1,4,3),(0,0,1,5,2),(0,0,1,6,1),(0,0,1,7,0),(0,0,2,0,6),(0,0,2,1,5),(0,0,2,2,4),(0,0,2,3,3),(0,0,2,4,2),(0,0,2,5,1),(0,0,2,6,0),(0,0,3,0,5),(0,0,3,1,4),(0,0,3,2,3),(0,0,3,3,2),(0,0,3,4,1),(0,0,3,5,0),(0,0,4,0,4),(0,0,4,1,3),(0,0,4,2,2),(0,0,4,3,1),(0,0,4,4,0),(0,0,5,0,3),(0,0,5,1,2),(0,0,5,2,1),(0,0,5,3,0),(0,0,6,0,2),(0,0,6,1,1),(0,0,6,2,0),(0,0,7,0,1),(0,0,7,1,0),(0,0,8,0,0),(0,1,0,0,7),(0,1,0,1,6),(0,1,0,2,5),(0,1,0,3,4),(0,1,0,4,3),(0,1,0,5,2),(0,1,0,6,1),(0,1,0,7,0),(0,1,1,0,6),(0,1,1,1,5),(0,1,1,2,4),(0,1,1,3,3),(0,1,1,4,2),(0,1,1,5,1),(0,1,1,6,0),(0,1,2,0,5),(0,1,2,1,4),(0,1,2,2,3),(0,1,2,3,2),(0,1,2,4,1),(0,1,2,5,0),(0,1,3,0,4),(0,1,3,1,3),(0,1,3,2,2),(0,1,3,3,1),(0,1,3,4,0),(0,1,4,0,3),(0,1,4,1,2),(0,1,4,2,1),(0,1,4,3,0),(0,1,5,0,2),(0,1,5,1,1),(0,1,5,2,0),(0,1,6,0,1),(0,1,6,1,0),(0,1,7,0,0),(0,2,0,0,6),(0,2,0,1,5),(0,2,0,2,4),(0,2,0,3,3),(0,2,0,4,2),(0,2,0,5,1),(0,2,0,6,0),(0,2,1,0,5),(0,2,1,1,4),(0,2,1,2,3),(0,2,1,3,2),(0,2,1,4,1),(0,2,1,5,0),(0,2,2,0,4),(0,2,2,1,3),(0,2,2,2,2),(0,2,2,3,1),(0,2,2,4,0),(0,2,3,0,3),(0,2,3,1,2),(0,2,3,2,1),(0,2,3,3,0),(0,2,4,0,2),(0,2,4,1,1),(0,2,4,2,0),(0,2,5,0,1),(0,2,5,1,0),(0,2,6,0,0),(0,3,0,0,5),(0,3,0,1,4),(0,3,0,2,3),(0,3,0,3,2),(0,3,0,4,1),(0,3,0,5,0),(0,3,1,0,4),(0,3,1,1,3),(0,3,1,2,2),(0,3,1,3,1),(0,3,1,4,0),(0,3,2,0,3),(0,3,2,1,2),(0,3,2,2,1),(0,3,2,3,0),(0,3,3,0,2),(0,3,3,1,1),(0,3,3,2,0),(0,3,4,0,1),(0,3,4,1,0),(0,3,5,0,0),(0,4,0,0,4),(0,4,0,1,3),(0,4,0,2,2),(0,4,0,3,1),(0,4,0,4,0),(0,4,1,0,3),(0,4,1,1,2),(0,4,1,2,1),(0,4,1,3,0),(0,4,2,0,2),(0,4,2,1,1),(0,4,2,2,0),(0,4,3,0,1),(0,4,3,1,0),(0,4,4,0,0),(0,5,0,0,3),(0,5,0,1,2),(0,5,0,2,1),(0,5,0,3,0),(0,5,1,0,2),(0,5,1,1,1),(0,5,1,2,0),(0,5,2,0,1),(0,5,2,1,0),(0,5,3,0,0),(0,6,0,0,2),(0,6,0,1,1),(0,6,0,2,0),(0,6,1,0,1),(0,6,1,1,0),(0,6,2,0,0),(0,7,0,0,1),(0,7,0,1,0),(0,7,1,0,0),(0,8,0,0,0),(1,0,0,0,7),(1,0,0,1,6),(1,0,0,2,5),(1,0,0,3,4),(1,0,0,4,3),(1,0,0,5,2),(1,0,0,6,1),(1,0,0,7,0),(1,0,1,0,6),(1,0,1,1,5),(1,0,1,2,4),(1,0,1,3,3),(1,0,1,4,2),(1,0,1,5,1),(1,0,1,6,0),(1,0,2,0,5),(1,0,2,1,4),(1,0,2,2,3),(1,0,2,3,2),(1,0,2,4,1),(1,0,2,5,0),(1,0,3,0,4),(1,0,3,1,3),(1,0,3,2,2),(1,0,3,3,1),(1,0,3,4,0),(1,0,4,0,3),(1,0,4,1,2),(1,0,4,2,1),(1,0,4,3,0),(1,0,5,0,2),(1,0,5,1,1),(1,0,5,2,0),(1,0,6,0,1),(1,0,6,1,0),(1,0,7,0,0),(1,1,0,0,6),(1,1,0,1,5),(1,1,0,2,4),(1,1,0,3,3),(1,1,0,4,2),(1,1,0,5,1),(1,1,0,6,0),(1,1,1,0,5),(1,1,1,1,4),(1,1,1,2,3),(1,1,1,3,2),(1,1,1,4,1),(1,1,1,5,0),(1,1,2,0,4),(1,1,2,1,3),(1,1,2,2,2),(1,1,2,3,1),(1,1,2,4,0),(1,1,3,0,3),(1,1,3,1,2),(1,1,3,2,1),(1,1,3,3,0),(1,1,4,0,2),(1,1,4,1,1),(1,1,4,2,0),(1,1,5,0,1),(1,1,5,1,0),(1,1,6,0,0),(1,2,0,0,5),(1,2,0,1,4),(1,2,0,2,3),(1,2,0,3,2),(1,2,0,4,1),(1,2,0,5,0),(1,2,1,0,4),(1,2,1,1,3),(1,2,1,2,2),(1,2,1,3,1),(1,2,1,4,0),(1,2,2,0,3),(1,2,2,1,2),(1,2,2,2,1),(1,2,2,3,0),(1,2,3,0,2),(1,2,3,1,1),(1,2,3,2,0),(1,2,4,0,1),(1,2,4,1,0),(1,2,5,0,0),(1,3,0,0,4),(1,3,0,1,3),(1,3,0,2,2),(1,3,0,3,1),(1,3,0,4,0),(1,3,1,0,3),(1,3,1,1,2),(1,3,1,2,1),(1,3,1,3,0),(1,3,2,0,2),(1,3,2,1,1),(1,3,2,2,0),(1,3,3,0,1),(1,3,3,1,0),(1,3,4,0,0),(1,4,0,0,3),(1,4,0,1,2),(1,4,0,2,1),(1,4,0,3,0),(1,4,1,0,2),(1,4,1,1,1),(1,4,1,2,0),(1,4,2,0,1),(1,4,2,1,0),(1,4,3,0,0),(1,5,0,0,2),(1,5,0,1,1),(1,5,0,2,0),(1,5,1,0,1),(1,5,1,1,0),(1,5,2,0,0),(1,6,0,0,1),(1,6,0,1,0),(1,6,1,0,0),(1,7,0,0,0),(2,0,0,0,6),(2,0,0,1,5),(2,0,0,2,4),(2,0,0,3,3),(2,0,0,4,2),(2,0,0,5,1),(2,0,0,6,0),(2,0,1,0,5),(2,0,1,1,4),(2,0,1,2,3),(2,0,1,3,2),(2,0,1,4,1),(2,0,1,5,0),(2,0,2,0,4),(2,0,2,1,3),(2,0,2,2,2),(2,0,2,3,1),(2,0,2,4,0),(2,0,3,0,3),(2,0,3,1,2),(2,0,3,2,1),(2,0,3,3,0),(2,0,4,0,2),(2,0,4,1,1),(2,0,4,2,0),(2,0,5,0,1),(2,0,5,1,0),(2,0,6,0,0),(2,1,0,0,5),(2,1,0,1,4),(2,1,0,2,3),(2,1,0,3,2),(2,1,0,4,1),(2,1,0,5,0),(2,1,1,0,4),(2,1,1,1,3),(2,1,1,2,2),(2,1,1,3,1),(2,1,1,4,0),(2,1,2,0,3),(2,1,2,1,2),(2,1,2,2,1),(2,1,2,3,0),(2,1,3,0,2),(2,1,3,1,1),(2,1,3,2,0),(2,1,4,0,1),(2,1,4,1,0),(2,1,5,0,0),(2,2,0,0,4),(2,2,0,1,3),(2,2,0,2,2),(2,2,0,3,1),(2,2,0,4,0),(2,2,1,0,3),(2,2,1,1,2),(2,2,1,2,1),(2,2,1,3,0),(2,2,2,0,2),(2,2,2,1,1),(2,2,2,2,0),(2,2,3,0,1),(2,2,3,1,0),(2,2,4,0,0),(2,3,0,0,3),(2,3,0,1,2),(2,3,0,2,1),(2,3,0,3,0),(2,3,1,0,2),(2,3,1,1,1),(2,3,1,2,0),(2,3,2,0,1),(2,3,2,1,0),(2,3,3,0,0),(2,4,0,0,2),(2,4,0,1,1),(2,4,0,2,0),(2,4,1,0,1),(2,4,1,1,0),(2,4,2,0,0),(2,5,0,0,1),(2,5,0,1,0),(2,5,1,0,0),(2,6,0,0,0),(3,0,0,0,5),(3,0,0,1,4),(3,0,0,2,3),(3,0,0,3,2),(3,0,0,4,1),(3,0,0,5,0),(3,0,1,0,4),(3,0,1,1,3),(3,0,1,2,2),(3,0,1,3,1),(3,0,1,4,0),(3,0,2,0,3),(3,0,2,1,2),(3,0,2,2,1),(3,0,2,3,0),(3,0,3,0,2),(3,0,3,1,1),(3,0,3,2,0),(3,0,4,0,1),(3,0,4,1,0),(3,0,5,0,0),(3,1,0,0,4),(3,1,0,1,3),(3,1,0,2,2),(3,1,0,3,1),(3,1,0,4,0),(3,1,1,0,3),(3,1,1,1,2),(3,1,1,2,1),(3,1,1,3,0),(3,1,2,0,2),(3,1,2,1,1),(3,1,2,2,0),(3,1,3,0,1),(3,1,3,1,0),(3,1,4,0,0),(3,2,0,0,3),(3,2,0,1,2),(3,2,0,2,1),(3,2,0,3,0),(3,2,1,0,2),(3,2,1,1,1),(3,2,1,2,0),(3,2,2,0,1),(3,2,2,1,0),(3,2,3,0,0),(3,3,0,0,2),(3,3,0,1,1),(3,3,0,2,0),(3,3,1,0,1),(3,3,1,1,0),(3,3,2,0,0),(3,4,0,0,1),(3,4,0,1,0),(3,4,1,0,0),(3,5,0,0,0),(4,0,0,0,4),(4,0,0,1,3),(4,0,0,2,2),(4,0,0,3,1),(4,0,0,4,0),(4,0,1,0,3),(4,0,1,1,2),(4,0,1,2,1),(4,0,1,3,0),(4,0,2,0,2),(4,0,2,1,1),(4,0,2,2,0),(4,0,3,0,1),(4,0,3,1,0),(4,0,4,0,0),(4,1,0,0,3),(4,1,0,1,2),(4,1,0,2,1),(4,1,0,3,0),(4,1,1,0,2),(4,1,1,1,1),(4,1,1,2,0),(4,1,2,0,1),(4,1,2,1,0),(4,1,3,0,0),(4,2,0,0,2),(4,2,0,1,1),(4,2,0,2,0),(4,2,1,0,1),(4,2,1,1,0),(4,2,2,0,0),(4,3,0,0,1),(4,3,0,1,0),(4,3,1,0,0),(4,4,0,0,0),(5,0,0,0,3),(5,0,0,1,2),(5,0,0,2,1),(5,0,0,3,0),(5,0,1,0,2),(5,0,1,1,1),(5,0,1,2,0),(5,0,2,0,1),(5,0,2,1,0),(5,0,3,0,0),(5,1,0,0,2),(5,1,0,1,1),(5,1,0,2,0),(5,1,1,0,1),(5,1,1,1,0),(5,1,2,0,0),(5,2,0,0,1),(5,2,0,1,0),(5,2,1,0,0),(5,3,0,0,0),(6,0,0,0,2),(6,0,0,1,1),(6,0,0,2,0),(6,0,1,0,1),(6,0,1,1,0),(6,0,2,0,0),(6,1,0,0,1),(6,1,0,1,0),(6,1,1,0,0),(6,2,0,0,0),(7,0,0,0,1),(7,0,0,1,0),(7,0,1,0,0),(7,1,0,0,0),(8,0,0,0,0)]

Let us count the number of nonnegative integer solutions to see if there are $495$ of them:

Prelude> tuples' = filter (\(x1,x2,x3,x4,x5)->(x1+x2+x3+x4+x5==8)) tuples
Prelude> length tuples'
495

[JDL] Jesús A. De Loera, The Many Aspects of Counting Lattice Points in Polytopes.

$\endgroup$
  • $\begingroup$ Can you give me explicit results for n = 4? Thanks! $\endgroup$ – Mary Feb 11 '17 at 12:13
  • $\begingroup$ All 165 of them? $\endgroup$ – Rodrigo de Azevedo Feb 11 '17 at 12:16
  • $\begingroup$ Can you give me result list for n = 4 same as n=5 above? Thanks! $\endgroup$ – Mary Feb 11 '17 at 12:26
  • $\begingroup$ Go to Try Haskell and type filter (\(x1,x2,x3,x4)->(x1+x2+x3+x4==8)) [ (x1,x2,x3,x4) | x1 <- [0,1..8], x2 <- [0,1..8], x3 <- [0,1..8], x4 <- [0,1..8] ] and length $ filter (\(x1,x2,x3,x4)->(x1+x2+x3+x4==8)) [ (x1,x2,x3,x4) | x1 <- [0,1..8], x2 <- [0,1..8], x3 <- [0,1..8], x4 <- [0,1..8] ] $\endgroup$ – Rodrigo de Azevedo Feb 11 '17 at 12:33
  • $\begingroup$ de Azevedoi.Thank you very much! $\endgroup$ – Mary Feb 11 '17 at 12:42
0
$\begingroup$

Hint: One of the possibilities is to take in Q3 $a$ to be the smallest non-negativ integer and try to find all the possible non-negativ integers for $b$ and $c$. Then add one to $a$ and find $b$ and $c$ again and proceed in this manner by adding one with each step till $a$ is the biggest integer equal or less 8.

Q1 and Q2 can be solved similarly.

$\endgroup$
0
$\begingroup$

It's a combinatorial problem. We consider the third question. There are 8 possibilities for a to be a non negative integer summing up to 8 with two futher ones. Explicitly we can choose

$$a\in \{0,\dots,8\}$$.

Once we've done that we can choose

$$b\in \{0,\dots, 8-a\}$$.

For $c$ there are no further choices possible since $c=8-b-a$ to satisfy the equation. Note all choices of $a$ and $b$ while going through this procedure you will find all "non-negative" integers.

Note that the question how many possible choices there are for $a,b,c$ is way more easy/ less work to answer.

I hope you can apply this method to Q1 and Q2.

best X

$\endgroup$
0
$\begingroup$

I will answer to question 3. For the other answers you can follow a similar reasoning but probably using sage would be a better solution.

1) assume $a,b,c>0$.

Then by stars and bars method you know that there are $\binom{8-1}{3-1}=21$ possible combinations of values between $1$ and $6$ to form you solutions.

(1, 1, 6), (1, 2, 5), (1, 3, 4), (1, 4, 3), (1, 5, 2), (1,6,1)

(2, 1, 5), (2, 2, 4), (2, 3, 3), (2, 4, 2), (2, 5, 1)

(3, 1, 4), (3, 2, 3), (3, 3, 2), (3, 4, 1)

(4, 1, 3), (4, 2, 2), (4, 3, 1)

(5, 1, 2), (5, 2, 1)

(6, 1, 1)

2) assume that either that there is one (and only one) $0$ in $a, b, c$

Then you should find $\binom{3}{1}\binom{8-1}{2-1}=21$ solutions:

(0, 1, 7), (0, 2, 6), (0, 3, 5), (0, 4, 4), (0, 5, 3), (0, 6, 2), (0, 7, 1)

  • same as before but exchange the first two components

  • same as before but exchange the first and last components

3) assume that 2 variables out of 3 are zero. Then you should look for $\binom{3}{2}\binom{8-1}{1-1}=3$ solutions

(8, 0, 0), (0, 8, 0), (0, 0, 8)

and you are done. But as you can see Sage would be much quicker!

Edit:

Here it is the Sage script for creating the list of all solutions for the case of 5 variables:

for j in range(5):
    pippo = Partitions(8, length=j)
    for i in pippo:
        Permutations(i+[0]*j).list()

Solutions are listed according to the number of variables that are set to 0.

$\endgroup$
  • $\begingroup$ Can you give me explicit results for questions 1 and 2 on the Sage? Thank you very much! $\endgroup$ – Mary Feb 11 '17 at 11:40
  • $\begingroup$ @Mary ok, I will edit my answer adding the Sage instructions $\endgroup$ – Maczinga Feb 11 '17 at 16:36
0
$\begingroup$

In Sage, if you care about the order of the variables (that is, if $a=7$, $b=1$ should be considered a different solution from $a=1$, $b=7$), then for Question 1 use:

sage: IntegerVectors(8, 5)

If you don't care about the order:

sage: Partitions(8, max_length=5)
$\endgroup$
  • $\begingroup$ I have a question at math.stackexchange.com/questions/2140368/…. Can you help me? Thank you very much! $\endgroup$ – Mary Feb 13 '17 at 1:30
  • $\begingroup$ There are several good answers there already. The one by Rodrigo de Azevedo can easily be adapted to Sage; in fact, you can almost copy his definition of A straight into Sage: just change it to Matrix(GF(2), [[1,1,1,....) to specify the base ring. Then ask for its right kernel. $\endgroup$ – John Palmieri Feb 13 '17 at 3:00
  • $\begingroup$ I do not understand. Can you help me? $\endgroup$ – Mary Feb 13 '17 at 4:33
  • $\begingroup$ File "<ipython-input-1-d25a490f3db8>", line 1 sage:Matrix(GF(Integer(2)), [[Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),Integer(1),Integer(1)], ^ SyntaxError: invalid syntax $\endgroup$ – Mary Feb 13 '17 at 4:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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