5
$\begingroup$

There was a combinatorics question last night that I thought I could answer, turns out I couldn't (so I discarded my draft) but I thought I could, I now want to find out if I got close.

The question was about splitting 50 things into any number of groups of 1,2,3,4 or 5 items.

If I were asked how many integer solutions there were to $A+B+C+D+E=10$ say I'd be quite happy to conclude that you "encode" any such solution using... say X and -s, so "XXX-XXX--XXX-X" denotes 3As, 3Bs, 0Cs 3Ds and 1 E, any arrangement of 10Xs and 4 dashes is a solution. So it is simply $\frac{14!}{10!4!}$ using the axiom of choice and such, I am happy with this work.

You can also modify it to work out how many integer solutions there are when any number is greater than a certain value (by substituting something like $A=a+1$ then A>=0 means a>=1).

But I cannot use this to solve A+2B+3C+4D+5E=n, at least not directly, I had a play on paper but I could not find anywhere to go with this, was I on the right lines or is this a totally different problem?

$\endgroup$
2
  • 1
    $\begingroup$ The Axiom of Choice??? $\endgroup$
    – Marc van Leeuwen
    Feb 17, 2014 at 14:02
  • $\begingroup$ @MarcvanLeeuwen Sorry I should have stated, given a decision with m outcomes and another independent with n the number of ways to choose is nm. So in this case you have a string of 14 things, there are 14 options for the first, 13 for the second ... 14! in total, of those 10! will be duplicates with respect to X (as you can't actually tell the Xs apart) and 4! duplicates with the dashes. Think of it as each string of 14! contains a substring of 10 Xs and 4-s, there will be 10! forms of that very substring and such. $\endgroup$
    – Alec Teal
    Feb 17, 2014 at 14:05

2 Answers 2

Reset to default
2
$\begingroup$

You are asking for the number of partitions of the number $50$ into parts of size at most $5$. It is equal to the number of partitions of the number $50$ into at most $5$ parts, and is the coefficient of $X^{50}$ in the power series $\prod_{i=1}^5\frac1{1-X^i}$, but there is no easy formula for such coefficients.

There is a lot of literature about counting partitions though.

$\endgroup$
2
  • $\begingroup$ Could you give me a little more info about where to find out more, and what this type of function is called? I like how X's value plays no part, that's interesting. I'd like to know where I can find out more. $\endgroup$
    – Alec Teal
    Feb 17, 2014 at 15:37
  • $\begingroup$ There is already quite a bit at Partition in Wikipedia. $\endgroup$
    – Marc van Leeuwen
    Feb 17, 2014 at 17:05
1
$\begingroup$

$A+2B+3C+4D+5E=n$ is the same problem, and it says to divide n in groups of multiple of 1's, multiple of 2's ...upto multiple's of 5's

Which is given by coefficient of $x^n$ in the expansion of

$$(1+x+x^2+\cdots)\cdot(1+x^2+x^4+\cdots)\cdot(1+x^3+x^6+\cdots)\cdot(1+x^4+x^8+\cdots)\cdot(1+x^5+x^{10}+\cdots)$$ $$={(1-x)^{-1}}\cdot(1-x^2)^{-1}\cdot(1-x^3)^{-1}\cdot(1-x^4)^{-1}\cdot(1-x^5)^{-1}$$

$\endgroup$
2
  • $\begingroup$ This is twice you've given some allegedly correct answer with no explanation or source as to what magic you have done to get it!! $\endgroup$
    – Alec Teal
    Feb 17, 2014 at 15:38
  • $\begingroup$ @AlecTeal I think it's self-explanatory. Nice $\endgroup$
    – ab123
    Jun 15, 2018 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.