Question here, explanation for the question below:
How can I improve the formula I got for the number of ways to partition $a$ into $n$ parts and smallest part $b$ to make it less recursive, or nonrecursive altogether? Any tips on how to formally prove it would also be nice.
Reason for Asking: I needed to calculate the number of possible dice combinations in a hypothetical dice game I made - the amount of ways $60$ can be written as the sum of six integers, with each integer being greater than or equal to $4$.
My Recursive Definition:
For any integer $a$, the number of ways to partition it into $n$ parts such that the smallest part is $b$ is given by the recurrence $$P_n(a,b) = \sum_{k=b}^{\lfloor{a \over n}\rfloor} P_{n-1}(a-k, k)$$
Reasoning: I started trying to find cases for partitions of length one, then two, and so on. What I noticed is that, for partitions of length 2, if there is no smallest part limit ($b=1$, $P_2(a,b) = \lfloor{a \over 2}\rfloor - b + 1$.
For partitions of length 3, I started at 1, then fixed the first integer in place and found the partitions of the number, going up from fixing 1 and not repeating overall partitions. An example would be to find the partitions of 6 with length 3.
$$ 6 = 1+1+4 = 1+2+3 = 2+2+2 $$
I noticed that the partitions of $6$ with $2$ fixed cannot contain numbers less than $2$, as they would have already been listed when fixing $1$. I have checked this, and it holds true that partitions starting with fixedpoint $X$ do not contain values less than $X$, as they already would have been counted. In the case for triples and $6$, fixing $1$ would leave with a possible partition of $5$ with length $2$ and smallest part $1$ (no smallest part) and fixing $2$ would leave a possible partition of $4$ with length $2$ and smallest part $2$. If I wanted to find the partitions with smallest part $2$ and all other conditions were the same, then I would just start fixing points at $2$, not $1$.
$3$ cannot be fixed, as there are no partitions with $3$ that have not already been stated. Also, as I noticed, $3 \geq \lfloor{6 \over 3}\rfloor$, which lines up well with my formula. This holds true for all cases I have checked.
For higher lengths, the problem boils down to fixing a number starting at $b$, then finding the possible partitions of the next length down for all lengths down to 1. As a result,
$$P_n(a,b) = \sum_{k=b}^{\lfloor{a \over n}\rfloor} P_{n-1}(a-k, k)$$
$a-k$ represents the remainder given when subtracting off the fixed number, while $k$ is the fixed point itself.
To use the formula for my example given before,
$$P_3(6,1) = P_2(5, 1) + P_2(4,2) = 2 + 1 = 3$$ Restatement of Question, with Explanation in View:
How can I improve this formula, formally prove this formula, or make this formula non-recursive?
As it stands, it gets extremely tedious to compute at larger lengths, as even something like $P_4(20, 3)$ becomes $P_3(17, 3) + P_3(16, 4) +P_3(15, 5)$ which grow into $5$ $P_2$ terms each.
Thank you.
There's an easy bijection between the partitions of $n$ into $k$ parts of at least $b$ and the partitions of $n - k(b-1)$ into $k$ parts of at least $1$, i.e. partitions of $n - k(b-1)$ into $k$ parts. Similarly, there's an easy bijection with the partitions of $n - kb$ into at most $k$ parts.
For small fixed $k$ there are closed forms, but in general you'll need to use a recursive approach. If you code it up, it's worth memoising so you don't repeat calculations.
If you want to read more deeply about partitions into $k$ parts, the Online Encyclopedia of Integer Sequences' A008284 is a good starting point.