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.
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
FrobeniusSolve[{1,1,1,1,1,1},18] another time? Nevertheless the last approach is really nice.
$\endgroup$
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
FrobeniusSolve rather than IntegerPartitions, the latter does not count permutations. See the answers to the linked question.
$\endgroup$
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...
