Using basic arithmetic, how do I count constrained partitions of a set?











up vote
5
down vote

favorite
1












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?










share|cite|improve this question
























  • My take on the first question is that the number of ways to display 3 stamps out of a collection of 18 is $18 times 17 times 16$; 18 ways to choose the first stamp, then 17 ways to choose the second, etc.
    – awkward
    Nov 18 at 15:17















up vote
5
down vote

favorite
1












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?










share|cite|improve this question
























  • My take on the first question is that the number of ways to display 3 stamps out of a collection of 18 is $18 times 17 times 16$; 18 ways to choose the first stamp, then 17 ways to choose the second, etc.
    – awkward
    Nov 18 at 15:17













up vote
5
down vote

favorite
1









up vote
5
down vote

favorite
1






1





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?










share|cite|improve this question















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?







combinatorics set-partition






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 18 at 13:59

























asked Nov 17 at 23:34









Greg Bacon

1285




1285












  • My take on the first question is that the number of ways to display 3 stamps out of a collection of 18 is $18 times 17 times 16$; 18 ways to choose the first stamp, then 17 ways to choose the second, etc.
    – awkward
    Nov 18 at 15:17


















  • My take on the first question is that the number of ways to display 3 stamps out of a collection of 18 is $18 times 17 times 16$; 18 ways to choose the first stamp, then 17 ways to choose the second, etc.
    – awkward
    Nov 18 at 15:17
















My take on the first question is that the number of ways to display 3 stamps out of a collection of 18 is $18 times 17 times 16$; 18 ways to choose the first stamp, then 17 ways to choose the second, etc.
– awkward
Nov 18 at 15:17




My take on the first question is that the number of ways to display 3 stamps out of a collection of 18 is $18 times 17 times 16$; 18 ways to choose the first stamp, then 17 ways to choose the second, etc.
– awkward
Nov 18 at 15:17










2 Answers
2






active

oldest

votes

















up vote
0
down vote














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.




Suggestions:




  1. Proceeding from left to right, subtract the highest available number.

  2. Don't think in terms of columns. In each row, underline the first number which you were compelled to choose. In the next row, replace the number before it with the next-highest number available.


$$begin{array}{lllllll}9&+&9.\9&+&6&+&underline{3}\9&+&underline{3}&+&3&+&3\6&+&6&+&6.\6&+&6&+&underline{3}&+&3\&vdots&&vdots&&vdotsend{array}$$



In the first row, the last number chosen was 9, so in the next you replace it by 6.



In the second row, the last number chosen was 6, so in the next you replace it by 3.



In the third row, the last number chosen was 9, so in the next you replace it by 6... etc.



I can't say whether she will feel this procedure to be "airtight", but the fact that all the partitions are presented with their parts in order means that, if another partition exists, it clearly must fit somewhere in between two of the rows on the list.






share|cite|improve this answer






























    up vote
    0
    down vote













    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.






    share|cite|improve this answer





















      Your Answer





      StackExchange.ifUsing("editor", function () {
      return StackExchange.using("mathjaxEditing", function () {
      StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
      StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
      });
      });
      }, "mathjax-editing");

      StackExchange.ready(function() {
      var channelOptions = {
      tags: "".split(" "),
      id: "69"
      };
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function() {
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled) {
      StackExchange.using("snippets", function() {
      createEditor();
      });
      }
      else {
      createEditor();
      }
      });

      function createEditor() {
      StackExchange.prepareEditor({
      heartbeatType: 'answer',
      convertImagesToLinks: true,
      noModals: true,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: 10,
      bindNavPrevention: true,
      postfix: "",
      imageUploader: {
      brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
      contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
      allowUrls: true
      },
      noCode: true, onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      });


      }
      });














      draft saved

      draft discarded


















      StackExchange.ready(
      function () {
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3002951%2fusing-basic-arithmetic-how-do-i-count-constrained-partitions-of-a-set%23new-answer', 'question_page');
      }
      );

      Post as a guest















      Required, but never shown

























      2 Answers
      2






      active

      oldest

      votes








      2 Answers
      2






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes








      up vote
      0
      down vote














      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.




      Suggestions:




      1. Proceeding from left to right, subtract the highest available number.

      2. Don't think in terms of columns. In each row, underline the first number which you were compelled to choose. In the next row, replace the number before it with the next-highest number available.


      $$begin{array}{lllllll}9&+&9.\9&+&6&+&underline{3}\9&+&underline{3}&+&3&+&3\6&+&6&+&6.\6&+&6&+&underline{3}&+&3\&vdots&&vdots&&vdotsend{array}$$



      In the first row, the last number chosen was 9, so in the next you replace it by 6.



      In the second row, the last number chosen was 6, so in the next you replace it by 3.



      In the third row, the last number chosen was 9, so in the next you replace it by 6... etc.



      I can't say whether she will feel this procedure to be "airtight", but the fact that all the partitions are presented with their parts in order means that, if another partition exists, it clearly must fit somewhere in between two of the rows on the list.






      share|cite|improve this answer



























        up vote
        0
        down vote














        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.




        Suggestions:




        1. Proceeding from left to right, subtract the highest available number.

        2. Don't think in terms of columns. In each row, underline the first number which you were compelled to choose. In the next row, replace the number before it with the next-highest number available.


        $$begin{array}{lllllll}9&+&9.\9&+&6&+&underline{3}\9&+&underline{3}&+&3&+&3\6&+&6&+&6.\6&+&6&+&underline{3}&+&3\&vdots&&vdots&&vdotsend{array}$$



        In the first row, the last number chosen was 9, so in the next you replace it by 6.



        In the second row, the last number chosen was 6, so in the next you replace it by 3.



        In the third row, the last number chosen was 9, so in the next you replace it by 6... etc.



        I can't say whether she will feel this procedure to be "airtight", but the fact that all the partitions are presented with their parts in order means that, if another partition exists, it clearly must fit somewhere in between two of the rows on the list.






        share|cite|improve this answer

























          up vote
          0
          down vote










          up vote
          0
          down vote










          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.




          Suggestions:




          1. Proceeding from left to right, subtract the highest available number.

          2. Don't think in terms of columns. In each row, underline the first number which you were compelled to choose. In the next row, replace the number before it with the next-highest number available.


          $$begin{array}{lllllll}9&+&9.\9&+&6&+&underline{3}\9&+&underline{3}&+&3&+&3\6&+&6&+&6.\6&+&6&+&underline{3}&+&3\&vdots&&vdots&&vdotsend{array}$$



          In the first row, the last number chosen was 9, so in the next you replace it by 6.



          In the second row, the last number chosen was 6, so in the next you replace it by 3.



          In the third row, the last number chosen was 9, so in the next you replace it by 6... etc.



          I can't say whether she will feel this procedure to be "airtight", but the fact that all the partitions are presented with their parts in order means that, if another partition exists, it clearly must fit somewhere in between two of the rows on the list.






          share|cite|improve this answer















          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.




          Suggestions:




          1. Proceeding from left to right, subtract the highest available number.

          2. Don't think in terms of columns. In each row, underline the first number which you were compelled to choose. In the next row, replace the number before it with the next-highest number available.


          $$begin{array}{lllllll}9&+&9.\9&+&6&+&underline{3}\9&+&underline{3}&+&3&+&3\6&+&6&+&6.\6&+&6&+&underline{3}&+&3\&vdots&&vdots&&vdotsend{array}$$



          In the first row, the last number chosen was 9, so in the next you replace it by 6.



          In the second row, the last number chosen was 6, so in the next you replace it by 3.



          In the third row, the last number chosen was 9, so in the next you replace it by 6... etc.



          I can't say whether she will feel this procedure to be "airtight", but the fact that all the partitions are presented with their parts in order means that, if another partition exists, it clearly must fit somewhere in between two of the rows on the list.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Nov 19 at 3:55

























          answered Nov 19 at 3:49









          Andrew Woods

          3,194513




          3,194513






















              up vote
              0
              down vote













              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.






              share|cite|improve this answer

























                up vote
                0
                down vote













                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.






                share|cite|improve this answer























                  up vote
                  0
                  down vote










                  up vote
                  0
                  down vote









                  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.






                  share|cite|improve this 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.







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered Nov 20 at 0:27









                  antkam

                  1,373112




                  1,373112






























                      draft saved

                      draft discarded




















































                      Thanks for contributing an answer to Mathematics Stack Exchange!


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      Use MathJax to format equations. MathJax reference.


                      To learn more, see our tips on writing great answers.





                      Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                      Please pay close attention to the following guidance:


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      To learn more, see our tips on writing great answers.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function () {
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3002951%2fusing-basic-arithmetic-how-do-i-count-constrained-partitions-of-a-set%23new-answer', 'question_page');
                      }
                      );

                      Post as a guest















                      Required, but never shown





















































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown

































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown







                      Popular posts from this blog

                      AnyDesk - Fatal Program Failure

                      How to calibrate 16:9 built-in touch-screen to a 4:3 resolution?

                      QoS: MAC-Priority for clients behind a repeater