# find the number of integral solutions a+b+c+d+e+f = 18 [duplicate]

This question already has an answer here:

Find the number of integral solutions of

a + b + c + d + e + f = 18


where a, b, c, d, e, f are elements of the range {0, 9}.
What are the various possibilities in terms of permutations/combinations?
I have tried listing them systematically but takes more time.

-

## marked as duplicate by Artes, Sjoerd C. de Vries, Michael E2, R. M.♦Oct 4 '13 at 1:06

Are you sure this is related to Mathematica rather than mathematics ? If so, please, provide sample code. – Sektor Oct 3 '13 at 19:51

Depending on whether you care about permutations or not, here are some ways to go about it.

One is to solve a system of equations via Reduce and count the solutions.

vars = Array[a, 6];
eqn = Total[vars] == 18;
ineqs = Map[0 <= # <= 9 &, vars];

In[558]:= Timing[soln = Reduce[Flatten[{eqn, ineqs}], vars, Integers];]
Length[soln]

Out[558]= {1.000000, Null}

Out[559]= 25927


Another is to create a loop that iterates over all possibilities and increments a counter for each.

countsolns[n_, k_] := Module[
{j = 0, indices, a, subtotals},
indices = Array[a, k];
subtotals = FoldList[Plus, 0, Most[indices]];
indices = MapThread[{#1, 0, Min[9, #2]} &, {indices, n - subtotals}];
indices[[-1, 2]] = Max[0, n - Last[subtotals]];
Do[j++, Evaluate[Sequence @@ indices]];
j
]

In[575]:= Timing[countsolns[18, 6]]

Out[575]= {0.480000, 25927}


If you want only one representative from each permutation of solutions, can use IntegerPartitions (as was already noted). We now use values in range 1 to 9 because values of zero would be accounted for in partitions that use fewer elements.

Length[IntegerPartitions[18, 6, Range[1, 9]]]

Out[581]= 139


This too might be done procedurally.

countsolns2[n_, k_] := Module[
{j = 0, indices, a, starts, subtotals},
indices = Array[a, k];
starts = Prepend[Most[indices], 0];
subtotals = FoldList[Plus, 0, Most[indices]];
starts[[-1]] = Max[starts[[-1]], n - Last[subtotals]];
indices =
MapThread[{#1, #2, Min[9, #3]} &, {indices, starts, n - subtotals}];
Do[j++, Evaluate[Sequence @@ indices]];
j
]

In[578]:= Timing[countsolns2[18, 6]]

Out[578]= {0.030000, 139}


One could also use generating function methods. I'll show for the easy case of counting all solutions.

SeriesCoefficient[(1 - x^10)^6/(1 - x)^6, {x, 0, 18}]

Out[594]= 25927

-
Haven't you forgotten about FrobeniusSolve[{1,1,1,1,1,1},18] another time? Nevertheless the last approach is really nice. – Artes Oct 3 '13 at 21:15
@Artes I'm partly responsible for FrobeniusSolve (described in part here). I just hope my code is better than my memory. – Daniel Lichtblau Oct 3 '13 at 21:25
Fair enough, your both answers deserve special attention – Artes Oct 3 '13 at 21:35

The combinations are shown below as 'result. The number of combinations is the number of elements inresult.

The permutations were calculated on each combination and summed.

It is possible to count the number of permutations with repetitions without actually producing each one. The trick is to use the formula:

n!/n1! n2!...nk!


where n stands for the number of objects (6), where there are n1 indistinguishable objects of type 1, n2 indistinguishable objects of type 2...and n, indistinguishable objects of type k. I was lazy. And producing the actual permutations is really little work for Mathematica.

result=IntegerPartitions[18, {6}, Range[0, 9]]

Print["combinations: ", Length[%]]

Print["permutations: ", Length[Permutations[#]] & /@ result // Total]


{{9, 9, 0, 0, 0, 0}, {9, 8, 1, 0, 0, 0}, {9, 7, 2, 0, 0, 0}, {9, 7, 1, 1, 0, 0}, {9, 6, 3, 0, 0, 0}, {9, 6, 2, 1, 0, 0}, {9, 6, 1, 1, 1, 0}, {9, 5, 4, 0, 0, 0}, {9, 5, 3, 1, 0, 0}, {9, 5, 2, 2, 0, 0}, {9, 5, 2, 1, 1, 0}, {9, 5, 1, 1, 1, 1}, {9, 4, 4, 1, 0, 0}, {9, 4, 3, 2, 0, 0}, {9, 4, 3, 1, 1, 0}, {9, 4, 2, 2, 1, 0}, {9, 4, 2, 1, 1, 1}, {9, 3, 3, 3, 0, 0}, {9, 3, 3, 2, 1, 0}, {9, 3, 3, 1, 1, 1}, {9, 3, 2, 2, 2, 0}, {9, 3, 2, 2, 1, 1}, {9, 2, 2, 2, 2, 1}, {8, 8, 2, 0, 0, 0}, {8, 8, 1, 1, 0, 0}, {8, 7, 3, 0, 0, 0}, {8, 7, 2, 1, 0, 0}, {8, 7, 1, 1, 1, 0}, {8, 6, 4, 0, 0, 0}, {8, 6, 3, 1, 0, 0}, {8, 6, 2, 2, 0, 0}, {8, 6, 2, 1, 1, 0}, {8, 6, 1, 1, 1, 1}, {8, 5, 5, 0, 0, 0}, {8, 5, 4, 1, 0, 0}, {8, 5, 3, 2, 0, 0}, {8, 5, 3, 1, 1, 0}, {8, 5, 2, 2, 1, 0}, {8, 5, 2, 1, 1, 1}, {8, 4, 4, 2, 0, 0}, {8, 4, 4, 1, 1, 0}, {8, 4, 3, 3, 0, 0}, {8, 4, 3, 2, 1, 0}, {8, 4, 3, 1, 1, 1}, {8, 4, 2, 2, 2, 0}, {8, 4, 2, 2, 1, 1}, {8, 3, 3, 3, 1, 0}, {8, 3, 3, 2, 2, 0}, {8, 3, 3, 2, 1, 1}, {8, 3, 2, 2, 2, 1}, {8, 2, 2, 2, 2, 2}, {7, 7, 4, 0, 0, 0}, {7, 7, 3, 1, 0, 0}, {7, 7, 2, 2, 0, 0}, {7, 7, 2, 1, 1, 0}, {7, 7, 1, 1, 1, 1}, {7, 6, 5, 0, 0, 0}, {7, 6, 4, 1, 0, 0}, {7, 6, 3, 2, 0, 0}, {7, 6, 3, 1, 1, 0}, {7, 6, 2, 2, 1, 0}, {7, 6, 2, 1, 1, 1}, {7, 5, 5, 1, 0, 0}, {7, 5, 4, 2, 0, 0}, {7, 5, 4, 1, 1, 0}, {7, 5, 3, 3, 0, 0}, {7, 5, 3, 2, 1, 0}, {7, 5, 3, 1, 1, 1}, {7, 5, 2, 2, 2, 0}, {7, 5, 2, 2, 1, 1}, {7, 4, 4, 3, 0, 0}, {7, 4, 4, 2, 1, 0}, {7, 4, 4, 1, 1, 1}, {7, 4, 3, 3, 1, 0}, {7, 4, 3, 2, 2, 0}, {7, 4, 3, 2, 1, 1}, {7, 4, 2, 2, 2, 1}, {7, 3, 3, 3, 2, 0}, {7, 3, 3, 3, 1, 1}, {7, 3, 3, 2, 2, 1}, {7, 3, 2, 2, 2, 2}, {6, 6, 6, 0, 0, 0}, {6, 6, 5, 1, 0, 0}, {6, 6, 4, 2, 0, 0}, {6, 6, 4, 1, 1, 0}, {6, 6, 3, 3, 0, 0}, {6, 6, 3, 2, 1, 0}, {6, 6, 3, 1, 1, 1}, {6, 6, 2, 2, 2, 0}, {6, 6, 2, 2, 1, 1}, {6, 5, 5, 2, 0, 0}, {6, 5, 5, 1, 1, 0}, {6, 5, 4, 3, 0, 0}, {6, 5, 4, 2, 1, 0}, {6, 5, 4, 1, 1, 1}, {6, 5, 3, 3, 1, 0}, {6, 5, 3, 2, 2, 0}, {6, 5, 3, 2, 1, 1}, {6, 5, 2, 2, 2, 1}, {6, 4, 4, 4, 0, 0}, {6, 4, 4, 3, 1, 0}, {6, 4, 4, 2, 2, 0}, {6, 4, 4, 2, 1, 1}, {6, 4, 3, 3, 2, 0}, {6, 4, 3, 3, 1, 1}, {6, 4, 3, 2, 2, 1}, {6, 4, 2, 2, 2, 2}, {6, 3, 3, 3, 3, 0}, {6, 3, 3, 3, 2, 1}, {6, 3, 3, 2, 2, 2}, {5, 5, 5, 3, 0, 0}, {5, 5, 5, 2, 1, 0}, {5, 5, 5, 1, 1, 1}, {5, 5, 4, 4, 0, 0}, {5, 5, 4, 3, 1, 0}, {5, 5, 4, 2, 2, 0}, {5, 5, 4, 2, 1, 1}, {5, 5, 3, 3, 2, 0}, {5, 5, 3, 3, 1, 1}, {5, 5, 3, 2, 2, 1}, {5, 5, 2, 2, 2, 2}, {5, 4, 4, 4, 1, 0}, {5, 4, 4, 3, 2, 0}, {5, 4, 4, 3, 1, 1}, {5, 4, 4, 2, 2, 1}, {5, 4, 3, 3, 3, 0}, {5, 4, 3, 3, 2, 1}, {5, 4, 3, 2, 2, 2}, {5, 3, 3, 3, 3, 1}, {5, 3, 3, 3, 2, 2}, {4, 4, 4, 4, 2, 0}, {4, 4, 4, 4, 1, 1}, {4, 4, 4, 3, 3, 0}, {4, 4, 4, 3, 2, 1}, {4, 4, 4, 2, 2, 2}, {4, 4, 3, 3, 3, 1}, {4, 4, 3, 3, 2, 2}, {4, 3, 3, 3, 3, 2}, {3, 3, 3, 3, 3, 3}}

combinations: 139
permutations: 25927

This lovely approach to the permutations was suggested by @Artes: Frobenius link

DeleteCases[FrobeniusSolve[{1, 1, 1, 1, 1, 1}, 18], {___, a_, ___} /; a > 9] // Length


25927

-
The problem is, the number of permutations is not 6! when there are repeated elements. – DavidC Oct 3 '13 at 20:39
To resolve your problem You sould use FrobeniusSolve rather than IntegerPartitions, the latter does not count permutations. See the answers to the linked question. – Artes Oct 3 '13 at 21:06
Nice. Why don't you propose it as your solution? – DavidC Oct 3 '13 at 21:11
@DavidCarraher Because it is a duplicate of Finding the number of solutions to a diophantine equation – Artes Oct 3 '13 at 21:19
The last approach is an added value, +1. – Artes Oct 3 '13 at 23:34
Reduce[a + b + c + d + e + f == 18 && 0 <= a <= 9 && 0 <= b <= 9 &&
0 <= c <= 9 && 0 <= d <= 9 && 0 <= e <= 9 && 0 <= f <= 9, {a, b,
c, d, e, f}, Integers] /. Or -> List /. And -> List


{{a == 0, b == 0, c == 0, d == 0, e == 9, f == 9}, {a == 0, b == 0, c == 0, d == 1, e == 8, f == 9}, {a == 0, b == 0, c == 0, d == 1, e == 9, f == 8}, {a == 0, b == 0, c == 0, d == 2, e == 7, f == 9}, {a == 0, b == 0, c == 0, d == 2, e == 8, f == 8}, {a == 0, b == 0, c == 0, d == 2, e == 9, f == 7}, {a == 0, b == 0, c == 0, d == 3, e == 6, f == 9}, {a == 0, b == 0, c == 0, d == 3, e == 7, f == 8}, {a == 0, b == 0, c == 0, d == 3, e == 8, f == 7}, {a == 0, b == 0, c == 0, d == 3, e == 9, f == 6}, {a == 0, b == 0, c == 0, d == 4, e == 5, f == 9}, {a == 0, b == 0, c == 0, d == 4, e == 6, f == 8}, etc etc

Length@%


25927

-

Variation on Lou's answer:

Total[Length[Permutations[#]] & /@
(Reduce[a + b + c + d + e + f == 18 &&
0 <= a <= b <= c <= d <= e <= f <= 9,
{a, b, c, d, e, f}, Integers] /.
{Or | And -> List, _ == v_Integer :> v})] // AbsoluteTiming


{0.022396, 25927}

It is not that pretty, but avoids explicitly finding all permutations on a result list of Reduce`. Instead, amount of permutations every ordered value could produce is counted and summed afterwards. This is relatively faster with six variables, and increasingly so with higher amount of variables.

Edit: Obviously my answer has also components from David Carraher. Or rather, I figured out an identical construct without reading that answer first...

-