I got so much valuable help on the ice-cream cone problem a while back that I thought I would try you all again.
The homework last night was to take ten objects and see how many ways you could put them into three groups (8, 1, 1; 7, 2, 1; 6, 2, 2; and so on.)
My question is: Is there a mathematical name for this, and if so, is there a formula for determining how many sets there are?
This is the introductory part of probability, and this type of problem is determining combinations. (Permutations is how many ways you can order the same set of objects.) Specifically, this has to do with selection without replacement (you can only use each object once). There are formulas for it, but to take this much further would be violating the board policy against providing solutions to homework problems. Although it doesn’t look like you are actually in the second grade. . . .
No, I quit school after 24th grade.
She (the actual second grader) doesn’t need to do the formula–the teacher just wanted them to play around with blocks or pennies or something. The question about the terminology and formula is just to satisfy my own curiosity.
The formula for taking k objects at a time from a set of n objects with no duplicates allowed and without regard to order is given by n!/(k!*(n - k)!). Just in case you’re not familiar with it, n! is defined by 0! = 1, and (n + 1)! = (n + 1)*n!.
Additionally, while there is a board policy against asking homework questions, there is no policy against answering them.
Actually, the exact term a mathematician would use depends on whether “a pile of 6, a pile of 3, and a pile of 1” is distinct from “a pile of 3, a pile of 6, and a pile of 1.” If those are considered the same, then you’re talking about partitions instead. If you know the number of “piles” you’re dividing things into, then you can use Stirling numbers to calculate the number of ways; but if the number of piles is arbitrary, then I believe I was once told that a “closed” formula is not known.
(I’m assuming that the objects you’re divvying up are all considered to be the same. If not, then disregard the above post.)
OK, I’m not clear on what exactly is being asked here. I gave the answer to the question “In how many ways can you choose 3 objects from a set of 10 if no repetitions are allowed and (A, B, C) is the same as (C, B, A)?”. MikeS is offering the answer to a different question, and the examples in the OP don’t look like either one. Can we get a little more clarification here?
Sure. They’ve been working on addition, among other things. The idea here was see how many ways you can get three integers (not counting zero) to add up to 10, with out repeating, i.e., 6+3+1 is the same as 3+6+1. I was mainly wondering if there is a formula to get the number of possible sets.
Actually, Stirling numbers assume that the objects aren’t considered all the same. For example, it says on your link that S(4,3)=6 (judging by that triangle of numbers between equations 7 and 8), and 6 is the number of ways to partition four distinguishable objects into 3 piles, but there’s only 1 way to partition four indistinguishable objects into 3 piles. (Namely, a pile of two and two piles of one.)
“Partitions” is definitely the right word for this type of problem, though.
I don’t know an exact formula for the kind of thing you’re looking for off the top of my head, and I have to teach a class now, but if no one else answers your question in the next hour I’ll think about it some more after my class.
WOW! A 2nd grader newbie on SDMB’s. Isn’t this a new one for the record? 
"Combinations and Permutations " is my name, thank you.
com·bi·na·tion ( P ) Pronunciation Key (kmb-nshn)
n. 5. Mathematics. One or more elements selected from a set without regard to the order of selection.
Selecting the 5 out of 10 object in unique ways to form sets
per·mu·ta·tion ( P ) Pronunciation Key (pûrmy-tshn)
n. 3. Mathematics. A rearrangement of the elements of a set.
The rearrangement of the 5 objects in each set in unique ways.
In that case, you don’t really want 10 choose 3, which would give you how many ways there are to add up three different numbers from a set of 10. One such way would be 1+2+3, because each number is different, and they were chosen from [0,9]. However, 1+2+3 does not equal 10, so it doesn’t fit your definition.
What you want is multichoose (with a twist), which is related to choose by: n multichoose k = (n + k - 1) choose k. What you want in this case is 3 multichoose 10 divided by 6 (because you can arrange the order any way you want). That is, you pick 10 things from a pool of three. However many times you pick the first thing is the first number in your sum. The number of times you pick the second thing is the second number, etc. Then you divide by 6 because you can arrange those three numbers in 6 ways, and you overcounted by that many times.
One way to think about multichoose is “How many size k sets can I make from n objects (if I allow repetition)?” 3 multichoose 2 = 6 because you can make {1,1}, {1,2}, {1,3}, {2,2}, {2,3}, {3,3} size two sets from the set {1,2,3}.
Another way to think about it is this: “If you have n objects and (k-1) dividers, how many ways are there to arrange the objects and dividors (like on a supermarket conveyer)?”
Let the objects be * and the dividers be |. Read left to right. One way would be:
||, which corresponds to the multiset <1,1,1,2,2,3,3,3,3,3> and to the sum 3 + 2 + 5 = 10
Another would be
||****, which would correspond to the multiset <1,3,3,3,3,3,3,3,3,3>, which would correspond to 1 + 0 + 9 = 10.
If you don’t want to allow 0 as a valid number, you can calculate the number of such sums that include 0, and subtract that number.
I think what we’re looking for (after some googling) is some form of “composition.” See “Length of Compositions” on this page:
http://www.users.globalnet.co.uk/~perry/maths/digitsum/digitsum.htm
I don’t see one where order is taken into account, though.
Oh, and this is definitely not 2nd grade level math. I learned this in my Sophmore year of college in Discrete Math. Here’s our homework for those interested.
The multichoose formula is right, but you can’t just divide by six at the end, because some ways of dividing the objects into 3 piles will be symmetric.
For example, while the partition “2,3,5” will appear in six different ways depending on the order of “2”, “3”, and “5”, the partition “2,4,4” will only appear 3 different ways. So 3 multichoose 10 divided by 6 will be too low.
Another way of seeing this: imagine there are 3 objects instead of 10. Then 3 multichoose 3 = 5 choose 3 = 10, which doesn’t even divide by 6, so dividing by 6 can’t be the way to go.
Another way to deal with the zero problem: start with 10-3=7 objects instead of ten. Calculate the number of ways to partition 7 objects into 3 piles in a way that allows 0 object in a pile. Then toss one extra object into each pile. So 10 objects into 3 piles with no empty piles allowed is the same number of partitions as 7 objects into 3 piles with empty piles allowed.
So to sum up, the number of ways to partition 10 objects into 3 piles with no empty piles allowed is 3 multichoose 7, which equals 9 choose 7, which equals 36. But that counts “2,3,5” and “2,5,3” as two separate answers. If the order doesn’t count then the number of ways is less than 36 (but it will be greater than 36/6). I still can’t think of an exact formula for this last case off the top of my head.
And a much better way too. I’ll have to think about the problem of overcounting.
Ugh. I’ve just finished wrestling with Maple and some hideous generating functions. I don’t think there is a nice formula for an arbitrary number of piles, but for a specific number of piles you can get some results.
Let P(n,k) be the number of ways to divide n objects into k piles, where the ordering doesn’t matter and where empty piles are allowed. Then obviously P(n,1)=1.
P(n,2)= floor(n/2+1), where floor(x) is the greatest integer less than or equal to x. This seems easy to prove.
P(n,3) seems to equal floor(n^2/12+n/2+1). For example, P(4,3)=floor(16/12+2+1)=4, and there are four ways to arrange four items in three piles if empty piles are allowed: (4,0,0), (3,1,0), (2,2,0), and (2,1,1). I think I could prove this, but it would be very messy.
I don’t know a general way of getting the formula for P(n,k) except in terms of generating functions.
Breaking a number into a sum of smaller numbers (or more generally a set into a collection of subsets) is “partitioning”. The number of smaller numbers is the “length of the partition”. That is, the question is “how many partitions of 10 are there of length 3?” In general this is denoted by P(10,3).
P(n,k) satisfies the recurrence relation P(n,k) = P(n-1,k-1) + P(n-k,k). Since P(n,k) = 0 for k>n, P(n,n) = 1, and P(n,0) = 0, this allows the calculation of P(n,k) for any n and k. For instance, P(n,1) = P(n-1,0) + P(n-1,1) = P(n-1,1), so P(n,1) = P(1,1) = 1 for all n>0.
P(10,3) = P(9,2) + P(7,3)
P(9,2) = P(8,1) + P(7,2) = 1 + P(7,2)
P(7,2) = P(6,1) + P(5,2) = 1 + P(5,2)
P(5,2) = P(4,1) + P(3,2) = 1 + P(3,2)
P(3,2) = P(2,1) + P(1,2) = 1 + 0 = 1
P(5,2) = 2
P(7,2) = 3
P(9,2) = 4
P(7,3) = P(6,2) + P(4,3)
P(6,2) = P(5,1) + P(4,2) = 1 + P(4,2)
P(4,2) = P(3,1) + P(2,2) = 1 + 1 = 2
P(6,2) = 3
P(4,3) = P(3,2) + P(1,3) = 1 + 0 = 1
P(7,3) = 4
P(10,3) = 8
To justify the recurrence relation, think of it this way: either one number in the sum is 1 or they’re all at least 1. In the first case, the number of ways it can happen is the number of ways n-1 can be broken into k-1 pieces (plus a kth piece of size 1). In the second, subtract 1 from every piece (and those k from n) and break n-k into k pieces.
There are explicit closed forms for many small k, but I don’t know of one in general. Neither do I know of a closed form for P(n), which is defined as the sum of P(n,k) for all k: the number of partitions of n of any length. However, I do know one very beautiful result.
Take the product of (1-q[sup]m[/sup]) for m running over all integers greater than or equal to 1 and call it f(q). Then take the multiplicative inverse of this power series and. You get (in the first few powers of q):
1/f(q) = 1 + q + 2q[sup]2[/sup] + 3q[sup]3[/sup] + 5q[sup]4[/sup] + …
and in general the coefficient of q[sup]n[/sup] is exactly P(n). Such a representation for a sequence of numbers is referred to as a “generating function” for the sequence.
A little more than just a second grade question, I’d say.
I only took up through Trig… I have noooooo idea wut you guys are talking about :eek:
I guess I’d fail 2nd grade math if I had to retake it 
Nah, Jester, the 2nd grader was not supposed to do all those calculations.
The 2nd grader is supposed to give the actually “sets of 3 numbers that add 10”.
So,
1+2+7
1+3+6
1+4+5
etc.
Some of the fancy calculations were 9th grade for me, some 12th grade.
What I meant was that thought the original assignment (finding collections of three numbers which add to 10) was 2nd grade math, the concept it touches on is actually surprisingly deep. Anyhow, the generating function is a little tweaky, but the rest should be accessible to anyone. Actually, I figured that since the OP “left school in the 24th grade” she may have teaching experience and patience enough to explain this to her daughter, should the daughter be interested. I’ll try to break it into smaller pieces.
P(n,k) is the number of ways of breaking n into k pieces. Such a way is a “partition” of “length” k.
If you have a partition, either one number is 1 or they’re all greater than 1.
In the first case, the other k-1 numbers add up to n-1, so there are P(n-1,k-1) of these.
In the second case, we can remove 1 from each piece. There are the same number of pieces now, but they add up to n-k (since we removed k 1s). Thus there are P(n-k,k) ways of doing this.
Since the two cases don’t overlap, the total P(n,k) is the sum of the two cases: P(n-1,k-1) + P(n-k,k)
To use this formula, you plug in numbers n and k and get new values of n and k you have to calculate P(n,k) for to add together. There are certain values we can know right away, and this will be enough since the new ns and ks are closer and closer to one of these cases.
k>n: can’t be done since each piece has size 1, making the smallest possible sum of k pieces larger than the number we’re trying to add up to.
k=n: exactly one way, with each piece being 1.
k=1: exactly one way, with the single piece being n.
Each step gives a new pair of n and k. One of them subtracts 1 from each of n and k, so eventually k will be 1. The other subtracts k from n and leaves k alone, so eventually n will be less than or equal to k.