There are two variations I would like to discuss about this problem that I have encountered and haven't been able to solve previously.
1) Shuffling is introduced i.e when order/arrangement matters. Suppose We have infinte (or >=N) flags of each of r colors. We have to find an arrangement of N flags using these flags . How many ways can this be done. (So a1 + a2 + .... ar = N where ai is number of flags of color i but since this is an arrangement, shuffling within the N flags is possible).
2) No shuffling but similar sets should be counted only once. i.e (a1,a2,a3) = (1,1,2) is same as (a1,a2,a3) = (2,1,1)
Also, what is a good blog/site/resource for intermediate-hard counting/combinatorics problems (with editorials/theory).
In the second variation, I believe you can use the simple recurence relation: dp(i, j) = dp(0, j - i) + dp(1, j - i) + dp(2, j - i) + ... + dp(i, j - i), with the basic case dp(0, 0) = 1. It just counts the number of inscreasing sequences of length i that sum up to some j, and every element is bigger than 0.
Sorry, I didn't get the part where we look back upon values which sum upto (j — i) to obtain dp(i,j). If i is the length of current sequence and j is the sum, then what sum is being achieved by subtracting length of the sequence from the sum i.e j — i ?. Could you explain a bit more ?
It's actually the number of ways to write an increasing sequence of numbers that sum up to N (it's the same as partitions, but formultated in another way). Because our sequence is increasing and we add 1 to our ith element, we must also add 1 to all the elements that are before him to keep the sequence increasing. Here is how you could visualize this dp, we will calculate dp(5,9), and I will number the elements from the end to the beginning: 00000 - > 11111 - > 11222 - > 11223. There are actually many number of ways to transition.
in ques 1 , if (1,1,2) is a solution and arrangements matter , shouldn't there be 3 similar solution (1,1,2) , (1,2,1) and (2,1,1) , but how (1+1+2)! / 2! ?
I will update the statement for better understanding. Consider there are infinite flags of each color and total number of flags in an arrangement is N. So for the arrangement, a1 + a2 + .... ar = N. In the example, what I meant was if (a1,a2,a3) = (1,1,2), then arrangements of this particular type are are (1+1+2)!/2! because (say) you have 1 red flag, 1 blue flag and 2 green flags. So, RBGG, RGBG, RGGB, RGBG, etc are all different.
This is partition problem. all of these can be solved using Dp. some formula's which i know of are here: -if shuffling is allowed as in your case 1 and this is into 2 cases . 0 is allowed — n+k-1 C k-1 atleast 1 n-1 C k-1 .
No, it's not ! I know the choose (n+k-1,k-1) for the basic partition problem. Sorry, if the question was not presented in a clear way. If it still isn't clear, I will update it again :p
Auto comment: topic has been updated by thezodiac1994 (previous revision, new revision, compare).