Mixing
Using basic arithmetic, how do I count constrained partitions of a set?
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:
- Scan the numbers in the pattern from right to left.
- If you can legally increment the current number, do so, and halt.
- Otherwise, change the current number to 0 and continue.
- 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
asked Nov 17 '18 at 23:34
Greg Bacon
1285
add a comment |
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:
- Scan the numbers in the pattern from right to left.
- If you can legally increment the current number, do so, and halt.
- Otherwise, change the current number to 0 and continue.
- 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
asked Nov 17 '18 at 23:34
Greg Bacon
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 '18 at 15:17
add a comment |
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:
- Scan the numbers in the pattern from right to left.
- If you can legally increment the current number, do so, and halt.
- Otherwise, change the current number to 0 and continue.
- 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
asked Nov 17 '18 at 23:34
Greg Bacon
1285
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:
- Scan the numbers in the pattern from right to left.
- If you can legally increment the current number, do so, and halt.
- Otherwise, change the current number to 0 and continue.
- 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
combinatorics set-partition
asked Nov 17 '18 at 23:34
Greg Bacon
1285
asked Nov 17 '18 at 23:34
Greg Bacon
1285
edited Nov 18 '18 at 13:59
asked Nov 17 '18 at 23:34
Greg Bacon
1285
asked Nov 17 '18 at 23:34
Greg Bacon
1285
asked Nov 17 '18 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 '18 at 15:17
add a comment |
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 '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 '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 '18 at 15:17
add a comment |
2 Answers
2
active
oldest
votes
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:
- Proceeding from left to right, subtract the highest available number.
- 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.
answered Nov 19 '18 at 3:49
Andrew Woods
3,194513
add a comment |
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.
answered Nov 20 '18 at 0:27
antkam
1,528112
add a comment |
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',
autoActivateHeartbeat: false,
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
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:
- Proceeding from left to right, subtract the highest available number.
- 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.
answered Nov 19 '18 at 3:49
Andrew Woods
3,194513
add a comment |
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:
- Proceeding from left to right, subtract the highest available number.
- 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.
answered Nov 19 '18 at 3:49
Andrew Woods
3,194513
add a comment |
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:
- Proceeding from left to right, subtract the highest available number.
- 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.
answered Nov 19 '18 at 3:49
Andrew Woods
3,194513
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:
- Proceeding from left to right, subtract the highest available number.
- 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.
answered Nov 19 '18 at 3:49
Andrew Woods
3,194513
edited Nov 19 '18 at 3:55
answered Nov 19 '18 at 3:49
Andrew Woods
3,194513
answered Nov 19 '18 at 3:49
Andrew Woods
3,194513
answered Nov 19 '18 at 3:49
Andrew Woods
3,194513
3,194513
add a comment |
add a comment |
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.
answered Nov 20 '18 at 0:27
antkam
1,528112
add a comment |
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.
answered Nov 20 '18 at 0:27
antkam
1,528112
add a comment |
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.
answered Nov 20 '18 at 0:27
antkam
1,528112
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.
answered Nov 20 '18 at 0:27
antkam
1,528112
answered Nov 20 '18 at 0:27
antkam
1,528112
answered Nov 20 '18 at 0:27
antkam
1,528112
answered Nov 20 '18 at 0:27
antkam
1,528112
1,528112
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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 '18 at 15:17