Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question

marked as duplicate by Artes, Sjoerd C. de Vries, Michael E2, rm -rf Oct 4 '13 at 1:06

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

4 Answers 4

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
share|improve this answer
    
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
1  
@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
add comment

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

share|improve this answer
    
The problem is, the number of permutations is not 6! when there are repeated elements. –  David Carraher 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? –  David Carraher 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
add comment
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

share|improve this answer
add comment

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...

share|improve this answer
add comment

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