1
$\begingroup$

I am following a problem from here. Now the original question states:

I want to find the different roll combinations that equal 6: 6 51 15 42 24 33 123 312 213 114 411 141 1113 3111 1311 1131 11112 21111 12111 11211 11121 and so on...

The given solution proposes a formula:

an=an−1+an−2+an−3+an−4+an−5+an−6

However this solution does not cater for duplicates like: 12111 11211. What strategy or formula can be implemented to omit the duplicates. I am not a maths major, so please bear with my novice self.

There is a solution proposed here However I would need a little more help, I intend to port it into a code based Algorithm. Say for example my board length is 6 and I have one single dice, how many combinations of the dice throw would give me sum 6 - without duplicates.

$\endgroup$
  • 1
    $\begingroup$ I think you want to enumerate the partitions of $6$. See en.wikipedia.org/wiki/Partition_(number_theory) $\endgroup$ – Ethan Bolker Nov 30 '17 at 15:36
  • 1
    $\begingroup$ To clarify, are you specifically wishing to count the number of ways to roll a six sided die and achieve a desired total result where any number of dice rolls is allowed and the order of the results on the dice does not matter? For example, for the total $3$ this could be accomplished in only three ways: $3,2+1,1+1+1$? $\endgroup$ – JMoravitz Nov 30 '17 at 15:36
  • $\begingroup$ @JMoravitz yes that is correct! $\endgroup$ – User3 Nov 30 '17 at 15:38
  • $\begingroup$ Assuming that is correct, you are asking for the restricted partitions of $n$ into partsize at most $6$, $p_1(n)+p_2(n)+\dots+p_6(n)$ where $p_k(n)$ represents the number of ways to partition the number $n$ into parts with largest part size equal to exactly $k$. The wiki-link includes generating functions and recurrence relations. To convince yourself of the similarity of your problems, consider paying attention to the section about Ferrers diagrams too. $\endgroup$ – JMoravitz Nov 30 '17 at 15:40
  • $\begingroup$ Thanks, Ill read up on that! $\endgroup$ – User3 Nov 30 '17 at 15:45
2
$\begingroup$

The objects you are interested in are restricted partitions. The sequence you are interested in is A001402: Number of partitions of $n$ into at most $6$ parts.

The equivalence between the problem of partitioning $n$ into at most $6$ parts and the problem of partitioning $n$ into parts of size at most $6$ can be seen by conjugation. Visually, one can picture it by reflecting the Young diagrams for each.

Let $a_n$ count the number of ways to do partition $n$ into at most $6$ parts. There are a number of ways we could express a formula for this, though they don't give very much intuition as to where the formula comes from. One way it could be expressed it is found on the OEIS page as:

$$a_n = a_{n-1}+a_{n-2}-a_{n-5}-2a_{n-7}+a_{n-9}+a_{n-1}+a_{n-11}+a_{n-12}-2a_{n-14}-a_{n-16}+a_{n-19}+a_{n-20}-a_{n-21}$$

where $a_0=1$ and $a_n=0$ for all $n<0$.

One could come up with something else similar from first principles by noting that the number $a_n$ we seek is going to equal

$$a_n=p_6(n)+p_5(n)+p_4(n)+p_3(n)+p_2(n)+p_1(n)+p_0(n)$$

where $p_k(n)$ counts the number of partitions of $n$ into at most $k$ parts. One could calculate $p_k(n)$ recursively by noting $p_k(n)=p_{k}(n-k)+p_{k-1}(n-1)$ with initial conditions $p_0(0)=1$ and $p_k(n)=0$ whenever $n\leq 0$ or $k\leq 0$ but not both.

(The brief reasoning behind this recurrence is that any partition of $n$ into $k$ parts either has all of its parts of size at least 2, or it has at least one part of size one. In the first case, by removing one from each of its parts, we are left with a partition of $n-k$ into $k$ parts. In the second case, by removing one of the parts of size one, we are left with a partition of $n-1$ into $k-1$ parts.)

One more comment on the topic, if all you are interested in is the results and not the math behind it, one could use asymptotics to get the expression that is found on the OEIS page a(n)=floor((6*n^5+315*n^4+6160*n^3+55125*n^2+(216705+9600*(n%3<1))*n+527500)/518400+(n+1)*(n+20)*(-1)^n/768) which is easily programmed, though difficult to explain.

$\endgroup$
  • $\begingroup$ Thanks a ton. I am really filled with gratitude! My Code is ready now! Thanks again! $\endgroup$ – User3 Nov 30 '17 at 16:30
  • $\begingroup$ Restricted partitions--very helpful! $\endgroup$ – DukeZhou Dec 14 '17 at 18:28

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.