Using basic arithmetic, how to count constrained partitions of a set

combinatoricsset-partition

On my 9-year-old daughter’s recent test over multiplication and grouping that included questions about the total number items in m groups of n and converting between multiplication sentences and models, one particular question asked how many ways one can display 18 stamps in groups of either 3, 6, or 9.

Her answer was three: 3 × 6, 6 × 3, and 9 × 2. I made three false starts of my own trying to explain to her how to approach the problem.

Counting Method

The first approach that came to mind was what Mark Jason Dominus on pages 131-132 of his book Higher Order Perl called the counting method, which he generalizes to manage a generator for permutations.

What is the pattern here? It turns out that getting from one pattern to the next is rather simple:

  1. Scan the numbers in the pattern from right to left.
  2. If you can legally increment the current number, do so, and halt.
  3. Otherwise, change the current number to 0 and continue.
  4. If you fall off the left end, then the sequence was the last one.

This algorithm should sound familiar, because you learned it a long time ago. It’s exactly the same as the algorithm you use to count.

I suggested that we try a simple rule of using the lowest available number (of 3, 6, or 9) that we hadn’t yet used in each column but soon realized it was going to be problematic.

3 3 3 3 3 3
3 3 3 3 6
3 3 3 6 3

The second and third partitions are the same, but getting into combinations versus permutations seemed like it’d be a bit much. I figured we could come back afterward to throw out duplicates. But also, we reused 3 in the fifth column, so we had to modify the mechanical rule to using the lowest available number not yet used at that point (in the sense of a decision tree). She seemed to grasp the concept and turned the crank for a total of 13 rows.

I took advantage of a good teaching moment to suggest that when it seems like an approach isn’t gaining much ground, that’s a sign that it’s time to take a step back and consider a different approach.

Dynamic Programming

“Let’s try starting from a simple case and building up. What if there were only three stamps? How many possible displays would there be?”

She correctly answered one.

“Now what if there were six stamps?”

Looking back at the first two rows of the previous attempt and from our discussion then, she saw that the answer was two.

“Okay, how about for nine stamps?”

With her table, she enumerated the three possibilities. From there, I wasn’t sure whether she’d more easily follow the jump to 12 or 18 next. Hmm. But in her table, she made a tree with no explicit edges to show that 3 and 3 combine to make 6, so …

Tree Traversal

Earlier, she preferred starting with smaller numbers and working her way up. I suggested splitting numbers starting from 18 instead to give

       18
     /    \
    9      9
   / \    / \
  6   3  6   3
 / \    / \
3   3  3   3

I began a discussion of leaf and internal nodes, and she asked if she could go play with her friend across the street.

Brute Force

Maybe the answer derived from brute force would reveal an obvious pattern. Simulating nondeterminism with

import Control.Monad
import Data.List
import qualified Data.Set as S

groups = do
  a <- [9,6,3,0]
  b <- [9,6,3,0]
  c <- [9,6,3,0]
  d <- [9,6,3,0]
  e <- [9,6,3,0]
  f <- [9,6,3,0]
  guard $ a+b+c+d+e+f == 18
  return [a,b,c,d,e,f]

main =
  mapM_ print $
  S.toList $
  S.fromList $
  map (reverse . sort) groups

yielded

[3,3,3,3,3,3]
[6,3,3,3,3,0]
[6,6,3,3,0,0]
[6,6,6,0,0,0]
[9,3,3,3,0,0]
[9,6,3,0,0,0]
[9,9,0,0,0,0]

Talking through how the groups of 3 combined to make groups of 6 and then regrouping from three groups of 6 to (9, 3, 3, 3) seems a little handwavy, and how would I convince her that we hadn’t skipped any possible displays? Likewise, from the dynamic programming approach, she identified three ways of displaying nine stamps, so we double that and also add (6, 6, 6), but that would seem like producing it from thin air and might also make her wonder what other combinations we hadn’t considered.

Using the mathematical tools available to a bright but young student, how does dear old Dad make the airtight case for her?

Best Answer

In general you have a coin combination problem: how can \$18 total be made from coins of denominations \$3, \$6, \$9?

In my experience (I have 2 teenagers...but they were 9yo once :) ), a good way to teach a 9yo would be simply to do a triple loop. The loops can be arranged in any order but somehow it seems easier / more intuitive if the outermost loop counts down the number of the largest coin, etc. 

For a = no. of  $9 coins, counting down from 18/9 to 0:
    For b = no. of $6 coins, counting down from (18-9*a)/6 to 0:
        c = no. of $3 coins = (18 - 9*a - 6*b) / 3
        print (a, b, c)

This will produce the same result as @AndrewWoods answer.

More advanced methods to solve the coin-combination problem are available, e.g. https://stackoverflow.com/questions/1106929/how-to-find-all-combinations-of-coins-when-given-some-dollar-value and see also https://en.wikipedia.org/wiki/Change-making_problem

For your specific question there is actually a very neat alternative solution, but perhaps much too advanced for a 9yo. First, convince her that you can rescale everything by dividing by 3. So you're trying to make up a total of 6 using any number of positive integers where each positive integer used is $\le k=3$.

Amazingly, this problem is equivalent to making up a total of 6 using exactly $k=3$ integers where each integer is non-negative! See https://en.wikipedia.org/wiki/Partition_(number_theory)#Restricted_part_size_or_number_of_parts for a beautiful pictorial proof using Young/Ferrers diagram.

IME it would take a rather advanced 9yo to understand this equivalence. Maybe you have to wait till middle school. :D Anyway, once you're convinced, then the solution is easy by just considering lexicographical ordered triplets with total of 6, i.e. 600, 510, 420, 411, 330, 321, 222. (Computationally this is also a triple loop, but compared to the triple-loop pseudo-code above, this one is easier to generate using just mental arithmetic.) If you represent each triplet as $d_1 d_2 d_3$ then each $d_i$ counts the number of integers (in the original partition) whose value $\ge i$. Alternatively, if you map back to my early notation of $(a,b,c)$ then $d_3 = a, d_2 = a+b, d_1 = a+b+c$. Thus 600 represents the combination of 6 1's, and 222 represent the combination of 2 3's.

Related Question