How many 3 -digit numbers can be formed from 0 to 8 whose sum is equal to 20 for repetition and non-repetition?

Question

I have a range from $0$ to $8$ . I want to find that how many 3-digit numbers can be formed whose sum is equal to $20$.
Non-Repetition of numbers: $$ 5+7+8=20 \\ $$ Repetition of numbers: $$ 4+8+8=20, \\ 6+7+7=20, \\ 8+6+6=20, $$ I want to know the number of ways that I can represent 20 using the sum of 3- positive integers. In repetition case, there is only 1 way which is mentioned above but in non-repetition case, we can also do it on paper but I want the general solution.

Answer 1

Ameeq. The problem you posted here needs an algorithm, it cannot be solved using the plain counting techniques (i.e. combinations and permutations ). The reason behind is the counting techniques, simply count items it does not apply some selective counting or filtered counting, or count items that satisfy an objective function ( in your case it is the total sum i.e. 20). However, these counting techniques will be utilized in the algorithm for verfication's on the maximum upper bounds. My solution is listed below:

Solution :

List/Set of Symbols S = {0,1,2,3,4,5,6,7,8}

n = |S| // which is 9.

r= 3 // requirement posed by the question i.e. three items need to be selected.

Upper Bounds When repetition is not allowed: k = [n!/(r!(n-r)!)].

Upper Bounds When repetition is allowed: k = [(r+n-1)!/(r!(n-1)!)]

These upper bounds tells us the number of 3-tuples which can be formed. It does not tells us that there sum is 20. The only way is to traverse these tuples and verify. there sum.

Step1. Generate the list of all 3-tuples (employ Cartesian product to generate them, take care of repetition while generating them) .

Step2. For each of the 3-tuple in the list.

Step3. Do

Step4. Sum the elements of the tuple.

Step5. If the sum is not 20.

Step6. then

Step7. Remove the tuple item from the list.

Step8. End If

Step9. End For.

Step10.Print the list // the list will contain only those combinations whose sum is 20.

Answer 2

The problem can be transformed into a couple of related problems as follows:

---

Problem 1: Consider the non-repetition problem with no restriction on range. Here we are to find natural numbers $0\leq a<b<c$ such that: $$a+b+c=20$$ Given appropriate $x,y,z\geq0$ we could reformulate this in the following way: $$ \begin{align} a&=x \\ b&=x+1+y\\ c&=x+1+y+1+z \end{align} $$ so the equation becomes $$ 3x+2(1+y)+1+z=20 \\ \Updownarrow\\ 3x+2y+z=17 $$

---

Constraint 1: To make use of the results from problem 1, we need to identify the cases where $c\leq 8$. For this to be the case, we must have: $$ c=x+1+y+1+z\leq 8 \\ \Updownarrow \\ x+y+z \leq 6 $$

---

Solutions 1: In order to search for solutions to problem 1 subject to constraint 1, we can start from a particular solution: $$ (x,y,z)=(5,1,0) \implies (a,b,c) = (5,7,8) $$ and try adding neutral vectors (vectors with $3x+2y+z=0$) such as $(-2,3,0)$ and $(0,-1,2)$ to this in order to produce further solutions. Indeed $$ (5,1,0)+(-2,3,0)=(3,4,0)\implies(a,b,c)=(3,8,9) $$ would have been another solution, had it not been for the constraint $x+y+z\leq 6$. Since adding $(-2,3,0)$ or $(0,-1,2)$ increases $x+y+z$ by one and since $(x,y,z)=(5,1,0)$ already has sum $6$, soon one realizes that this is the only solution. Note that $(-2,3,0)$ and $(0,-1,2)$ form a basis for the nullspace of the problem since the nullspace defined by $3x+2y+z=0$ must be two-dimensional.

---

Problem 2: Consider the repetition case $0\leq a\leq b\leq c$. This can be described via: $$ \begin{align} a &= x \\ b &= x+y \\ c &= x+y+z \end{align} $$ so we have: $$ 3x+2y+z=20 $$

---

Constraint 2: Here we have: $$ c=x+y+z\leq 8 $$

---

Solutions 2: Again we start from a particular solution: $$ (x,y,z) = (6,1,0) \implies(a,b,c)=(6,7,7) $$ Note that $x+y+z=7$ so this is a valid solution. But as soon as we add $(-2,3,0)$ or $(0,-1,2)$ we increase the sum $x+y+z$ by one, so we have very little wiggle room. In fact we can add one of those exactly once, so the only two other solutions must be: $$ \begin{align} (6,1,0)+(-2,3,0) &= (4,4,0) \implies &&(a,b,c)=(4,8,8) \\ (6,1,0)+(0,-1,2) &= (6,0,2) \implies &&(a,b,c)=(6,6,8) \end{align} $$

I hope this makes sense!