You have pearl of 3 types.
Type 1 pearl can be of color from 1 to X.
Type 2 pearl can be of color from X+1 to X+Y
Type 3 pearl can be of color from X+Y+1 to X+Y+Z.
You have unlimited supply of pearls of each type and each color. You want to build some pearl chain. But you have 2 more additional constraints.
The total number of Type 1 and Type 3 pearls will be exactly A.
The total number of Type 2 and Type 3 pearls will be exactly B.
Given A, B, X, Y and Z (All <= N) calculate how many different pearl chains are possible. 2 chains are different if they have different length or there is a position in which they have different colored pearl.
The Answer should be closed form, or computable in O(Log(N)) time.
Solution Idea:
Sum t3 from 0 to min(A,B) of X^(A - t3) * Y^(B - t3) * Z^t3 * (A + B - t3)! / [ t3! (A - t3)! (B - t3)! ]
At which point we were stuck. What kind of combinatoric quantity is this? It's some type of Stirling or Euler numbers? Thanks!