1

I would like some confirmation regarding my logic here, which I feel is 'suspiciously straightforward'.

Say I wish to express a number as the sum of $10$ non-zero numbers, where order does not matter.

I can see that this is an application of the stars and bars method, but the part I am not completely sure about is the fact that order does not matter. So for example $1+2+3$ would be considered the same as $3+2+1$.

Would I get the normal answer (where order does matter) and divide it by $10!$ to remove the degree of over counting?

Trogdor
  • 10,331
  • Unordered partitions are hard, compared to order. See Wikipedia. Stars and bars is not useful. There isn't any lovely formula. https://en.m.wikipedia.org/wiki/Partition_(number_theory)#Partition_function – Thomas Andrews Aug 31 '15 at 03:09
  • there are some recursions you can use though. – Asinomás Aug 31 '15 at 03:10
  • Thank you to you both. Could you perhaps explain why the logic I have shown above is not correct? I cannot spot any flaws in it. $(1,2,3)=(1,3,2)=(2,1,3)=(2,3,1)=(3,1,2)=(3,2,1)$, and there are $6=3!$ such sets. – Trogdor Aug 31 '15 at 03:13

2 Answers2

2

The degree of overcounting by Stars and Bars changes, not all partitions are overcounted by a factor of $10!$. Indeed it is only $10!$ when you for expressions of $n$ as a sum of $10$ distinct positive integers.

As an extreme example, Stars and Bars counts $20=2+2+\cdots +2$ ($10$ copies of $2$) once. That's exactly how often it should be counted in your partition problem.

André Nicolas
  • 507,029
1

No, because dividing by $10!$ assumes all the elements are different. If three are the same (and all the others are different) you should divide by $10!/3!$ A simple example that we can count by hand is expressing $6$ in three unordered parts. We can have $1+1+4, 1+2+3$ or $2+2+2$, so there are three ways. The stars and bars approach gives ${5 \choose 2} =10$ possibilities. There are three arrangements of $1,1,4$, six of $1,2,3$, and one of $2,2,2$.

Ross Millikan
  • 374,822