Given a number of "pips", and a number of rows with maximum values, what's an algorithm that can calculate the number of combinations?

Question

I'm trying to figure out what the equation is that can calculate the total number of combinations for placing "pips" into rows, where each row has a maximum. I'm not quite sure if that explains it, so here's an example:

6 pips with 3 rows each with a maximum of 5, has 25 combinations:

• "xxxxx" "x" ""
• "xxxxx" "" "x"
• "xxxx" "x" "x"
• "xxxx" "xx" ""
• "xxxx" "" "xx"
• "xxx" "xxx" ""
• "xxx" "" "xxx"
• "xxx" "xx" "x"
• "xxx" "x" "xx"
• "xx" "xxxx" ""
• "xx" "xxx" "x"
• "xx" "xx" "xx"
• "xx" "x" "xxx"
• "xx" "" "xxxx"
• "x" "xxxxx" ""
• "x" "" "xxxxx"
• "x" "xxxx" "x"
• "x" "x" "xxxx"
• "x" "xxx" "xx"
• "x" "xx" "xxx"
• "" "xxxxx" "x"
• "" "x" "xxxxx"
• "" "xxxx" "xx"
• "" "xx" "xxxx"
• "" "xxx" "xxx"

What's the equation that can calculate this, given a(m, r, p) = ? where m is the maximum number of pips per row, r is the number of rows, and p is the pips to select?

Answer 1

This answer has a recurrence that solves the problem. Your $a(m, r, p)$ is equivalent to $a_m(r-1, p)$ in that answer. Note that when coding an algorithm, you'll need a version of the binomial coefficient that yields $0$ for out-of-range values.

Answer 2

Let us assume that the number of "pips" is p, there are r "baskets" to place those "pips" and the maximum number of "pips" that can be placed in each basket is m. Then a(m,r,p)=(p+r-1)!/(r-1)!p!- Σr(n-i) for i in {0,1,..,p-m} For the first part of the equation assume that you put all the p "pips" in line and you have to place r-1 lines, so that there are r baskets. Assumed that you have to choose the r-1 lines of p+r-1 places. so you must calculate the combination of p+r-1 things r-1 at a time. For the second part, because you have set a maximum number m of pips that can be placed in baskets you have to substract Σr(n-i) from the previous combination, because this is the number of not allowed combinations