Say I have white, red, and blue poker chips. They’ve been given these point values: white=1, red=2, blue=4. I want to give each player an assortment of chips that will total 12 points. How many different combinations are possible? What is the formula for determining this? How do we determine each of the combinations? What would these formulas be called?
And for these purposes, 6 whites+1 red+1 blue is the same as 1 blue+1 red+6 whites, etc.
Thanks!
What you seek are called partitions of 12 into parts 1, 2, or 4. There are 16 such beasts.
If you’d like to enumerate them its probably easiest to do so in either ascending or descending order of the number of largest parts.
4+4+4
4+4+2+2
4+4+2+1+1
4+4+1+1+1+1
4+2+2+2+2
4+2+2+2+1+1
4+2+2+1+1+1+1
4+2+1+1+1+1+1+1
4+1+1+1+1+1+1+1+1
2+2+2+2+2+2
2+2+2+2+2+1+1
2+2+2+2+1+1+1+1
2+2+2+1+1+1+1+1+1
2+2+1+1+1+1+1+1+1+1
2+1+1+1+1+1+1+1+1+1+1
1+1+1+1+1+1+1+1+1+1+1+1
Thanks, Lance Turbo. This doesn’t quite answer the question I’m most curious about. It’s not the distribution of the number of chips, but of the value of chips. In this case, each player should have chips worth a total of 12: 12 whites, or 6 reds, or 3 blues, or any other combination adding up to 12. I see how your answer helps with that. I just have to substitute the values for the numbers, e.g., take the first variation of 4+4+4 and say, right, that’s 4 white (4x1), 2 red (2x2), and 1 blue (1x4) for a total value of 12. But is there a way to calculate all the distributions without doing that arithmetic all the way through?
I’ve already solved the “problem” by figuring out enough permutations for the task at hand, and the arithmetic is not beyond me, but just became curious as how someone who knew more math (which would be a C student in grade 7 or 8, I’m afraid) might go, oh, that’s easy, you just do this, this, and this, and the secret of the universe is revealed!
Thanks!
No, the first variation of 4+4+4 is three blues, each of value four. There’s no way to calculate such a scenario without doing a lot of manual “trying it out” and as Lance Turbo says the trick is to line them up in a way that ensures you don’t miss any.
Now if you were going to try other combinations of values, and other desired values, you could automate the process somewhat, but you’d still have a many parted, somewhat complicated method.
Well, that is interesting. I’m not mathphobic, that is, it doesn’t scare me. I just don’t understand it and stand in childlike wonder and awe before it. So I’m surprised that the brute force method I used is the way to solve this. Thanks, Lance and Naita!
This is a variation on a change-making problem. I’m not astute enough mathematically, but the general principles are discussed here.
You can get the answer in Wolfram alpha for your problem by typing in [“power series 1/( (1-x)(1-x^2)(1-x^4))”](https://www.wolframalpha.com/input/?i=power+series+1%2F(+(1-x)(1-x^2)(1-x^4)) and expanding the series until you get to the coefficient of x^12, which is 16. (Click on “more terms” on the right side of the first results box until you get to your answer.)
No, I don’t exactly understand it. We’ll need someone like Indistinguishable to explain it.
Ooooh! Ooooh! I can be like Indistinguishable!
The first key insight is that the power series for 1/(1-x) is particularly simple:
1/(1-x) = 1 + x + x^2 + x^3 + x^4 + …
Similarly, the power series for 1/(1-x^2) and 1/(1-x^4) can be constructed by substituting x->x^2 and x->x^4 into that series:
1/(1-x^2) = 1 + x^2 + x^4 + x^6 + …
1/(1-x^4) = 1 + x^4 + x^8 + x^12 + …
The “point” of these series, is that the coefficient in x^n in each one is the number of ways to construct a collection of chips of value n out of one of the chip. For example, the 1/(1-x) series represents the $1 chip. Using only $1 chips there is only one way to construct a collection with each value, so each coefficient is 1.
The 1/(1-x^4) series represents the $4 chip. Using $4 chips, there is exactly one way construct collections worth $0, $4, $8, $12, &c, so those coefficients are 1, but no way to construct collections worth $1, $2, $3, $5, $6, $7, &c, so those coefficients are 0.
The second key insight is that when you multiply power series together, the terms combine in the same way that, “finding the number of ways to make collections of things” works.
So if I want to figure out the power series for the product of these functions you get:
1/(1-x)1/(1-x^2)1/(1-x^4) = (1 + x + x^2 + x^3 + x^4 + …)(1 + x^2 + x^4 + x^6 + …)(1 + x^4 + x^8 + x^12 + …)
And if you want to find the coefficient of x^12 in whatever power series that multiplies out to, the result ends up being "the number of ways to construct a term of x^12 using exactly one term from each sub-series).
So the x^12 * 1 * 1 term is part of that result, as is the x^6x^21 and x^31x^4 term, as well as a bunch of others. So the “multiply these functions together and taking the x^12 term” method is really doing the same thing as “figuring out all of the combinations of terms that sum to 12” method.
These techniques are called “generating function methods” and they are the part of combinatorics that doesn’t suck. 
My 16 year-old nephew was like this and more–or I should say I was and still am like this–when I was reading him practice questions for the SAT.
I was torn between pride and guilt. I wonder if there’s a word for that.
I’d love that insight. 
Could you explain it?
Sure. To start with a simpler, but better known, example, consider the binomial expansion:
(1+x)^n = C(n, 0) + C(n, 1)*x + C(n, 2)*x^2 + C(n, 3)*x^3 + … + C(n, n-1)*x^{n-1} * C(n, n)*x^n
Where C(n, x) is the number of ways to choose x items out of a set of n. Which is seems like it ought to be a combinatorial property, instead of one that comes out of algebra.
The connection is to note that:
(1+x)^n = (1+x)(1+x)(1+x)(1+x)…*(1+x)
where there are n factors in the expansion. Since this is a finite product, I could expand it out entirely with 2^n total terms, all of which would be some power of x. Conversely for every particular one of those terms, I could think of it as "picking whether to multiply in the “1” or the “x” from each original (1+x) factor.
So if I was looking for the constant term, I would know that in order to generate it I would have had to “pick” the constant term from each of the original factors. There is only one way to make that selection, so there is only one such term.
If I was looking for the x^1 term, I would know that in order to generate it I would have had to pick “x” from exactly one of the factors, and “1” for all of the rest. If I don’t pick “x” ever, I get the constant term, which is not what I want, and if I pick it twice, I get an x^2 term, which is also not what I want. Since there are n terms, there are C(n, 1) = n ways to pick exactly one of those terms to contribute an x^1 term, so in the full expansion there are C(n,1) x^1 terms, which makes a term of C(n,1)*x^1 when simplified.
If I was looking for the x^2 term, I would know that to generate it I need to pick exactly 2 of the (1+x) terms to contribute an “x”, and the rest need to contribute a “1”. Since there are C(n,2) ways to pick two terms to contribute an x, the end result has a term of C(n,2)*x^2.
And so on for the remaining coefficients.
The power series case is just a little more complicated because the original factors are themselves infinite series, and the original coefficients aren’t necessarily all 1. But even as such, if you want to pick out a specific term in:
S = (sum(a[sub]i[/sub]x[sup]i[/sup]))(sum(b[sub]i[/sub]x[sup]i[/sup]))(sum(c[sub]i[/sub]x[sup]i[/sup]))
The coefficient of x^n in S is the sum of all of the possible products of the form (a[sub]i[/sub]x[sup]i[/sup]b[sub]j[/sub]x[sup]j[/sup]c[sub]k[/sub]x[sup]k[/sup]) where i+j+k = n. To solve the OP’s problem, we just pick power series such that the sum of all of those products is the result that we are after.
Ah, the binomial and nCr of course. But for the infinite series there’s no C, right? You have to do the multiplication of the series out to wherever you need to be and see what you get?
Right, nCr has a closed-form formula, but suppose you didn’t know the formula. Then if you wanted to calculate 7C2, say, you could start with (1+x)^7, differentiate it twice, evaluate that derivative at x=0, and divide by 2!, to get the coefficient of x^2 in that expansion which is the value we want.
In the OP’s case, we don’t have a closed form formula for the coefficients of the series, but because we can infer the sum of the series, we can apply the “differentiate and evaluate at 0” technique to extract the coefficients.
Um, right, I’ll get my 2nd year math major nephew right on that…:eek:
I missed this thread when it originally went down, but having struck upon it now via, yes, vanity searching, I’ll note that, for what it’s worth, there IS a closed-form solution for this problem! (I mean, I’m fond of saying that “closed-form” is a silly and subjective concept, but at any rate, this will be the sort of thing most everyone calls “closed-form”).
The formula is this: Let f(x) = (x + 1) * (x + 2)/2, and let g(x) = f(floor(x/4)). Then the number of ways to make a total of n using white (1 pt), red (2 pt), and blue (4 pt) chips is g(n) + g(n - 2).
For example, when n = 12, we have that g(n) + g(n - 2) = f(floor(12/4)) + f(floor(10/4)) = f(3) + f(2) = 4 * 5/2 + 3 * 4/2 = 10 + 6 = 16. [As a sanity check, this matches the enumeration already done in the thread.]. As another example, when n = 103, we have that g(n) + g(n - 2) = f(floor(25.75)) + f(floor(25.25)) = f(25) + f(25) = (25 + 1) * (25 + 2) = 702. [It would be much more tedious to get to that with the Wolfram Alpha power series expander!]
Where does this formula come from?
Well, first of all, suppose we were forced to use an even number of red chips. I.e., suppose that instead of single red chips, we only had access to red-pairs, each pair worth 4 pts. Then, n mod 4 (i.e., the remainder when n is divided by 4) would have to match the number of white chips used mod 4. After putting in that many white chips for sure (0, 1, 2, or 3), the remaining number of white chips used has to be a multiple of 4; i.e., the remaining white chips have to be deployed in quadruplets, each quadruplet worth 4 pts. At this point, the question reduces to how many ways we can pick precisely floor(n/4) out of white-quadruplets, red-pairs, and blue chips. The standard “stars-and-bars” argument tells us the number of ways to pick 3 quantities summing to x is f(x) [i.e., (x + 2) choose 2; i.e., the number of ways to intermix, in some sequence, x many stars with 2 bars, thus creating 3 groups of stars totaling to x], and thus we find we can do this in f(floor(n/4)) = g(n) many ways.
That’s if we’re forced to use an even number of red chips. But we could possibly use an odd number of red chips! That’s ok; to make n with an odd number of red chips is to same as to toss in one red chip and then make the remaining n - 2 with an even number of red chips. And so the number of ways to do so will be g(n - 2), and adding these together gives the total quantity we are interested in.
I wrote this out without explicit resort to the generating series from before, but if you like, we can think of this in terms of those as well: this closed form arises from re-expressing 1/((1 - x)(1 - x[sup]2[/sup])(1 - x[sup]4[/sup])) as (1 + x[sup]2[/sup])(1 + x + x[sup]2[/sup] + x[sup]3[/sup])/(1 - x[sup]4[/sup])[sup]3[/sup]. The (1 + x[sup]2[/sup]) corresponds to whether we use an even or odd number of red chips. Similarly, the (1 + x + x[sup]2[/sup] + x[sup]3[/sup]) corresponds to the number of white chips mod 4.
Finally, the coefficients of the power series for 1/(1 - x[sup]4[/sup])[sup]3[/sup] have a nice closed-form because the coefficients of 1/(1 - y)[sup]3[/sup] have a nice closed form, which can be derived either by observing 1/(1 - y) is the sum of all powers of y and applying “stars-and-bars” reasoning as above, or thinking in terms of Newton’s generalized binomial theorem for (1 - y)[sup]-3[/sup] to get the coefficient of y[sup]n[/sup] as (-1)[sup]n[/sup] * (-3) choose n = (-1)[sup]n[/sup] * (-3)/1 * (-4)/2 * (-5)/3 * … * (-(n + 2))/n = (n + 2) * (n + 1)/2 (i.e., what was called f(n) above). From this, it follows that (1 + x + x[sup]2[/sup] + x[sup]3[/sup])/(1 - x[sup]4[/sup])[sup]3[/sup] has degree n coefficient equal to f(floor(n/4)) (i.e., what was called g(n) above), and therefore that the quantity of interest, which is (1 + x[sup]2[/sup]) times this, has degree n coefficient equal to g(n) + g(n - 2), the formula noted above.
Things happened to work out particularly nicely in this case, but I’ll note that ANY rational function (i.e., one polynomial divided by another) has a power series whose coefficients have a closed-form formula in the same sense, and thus we would be able to get closed-form formulae using any number of colors of chips, each worth any particular number of points. One sledgehammer approach to deriving these closed-form formulae for coefficients of arbitrary rational functions is to use so-called “partial fraction” decomposition to reduce to linear combinations of reciprocals of (x - r)[sup]p[/sup] for various complex roots r of the denominator and powers p, these reciprocals in turn being handled by the generalized binomial theorem just as above. There are also more direct ways to get at these general closed-form formulae (in the sense of not thinking about complex roots), but anyway, I’ll leave it at that for now.
Ah, I should say, for these chips problems, we won’t even need to deal with arbitrary rational functions; just those of the form P(x)/(1 - x[sup]n[/sup])[sup]m[/sup] for some n and m (where n can be taken to be the least common multiple of the variously colored chips’ point values, and m the number of colors of chips). These are easy to get closed-form formulae for the coefficients of, as above; the mentioned partial fraction sledgehammer will never be necessary.