I found this recurrence f(n,k)=f(n1,k1)+f(nk,k).But unable to understand how it works. asked 16 Jan '16, 21:19

Assumptions :
The Question can also be clearly formulated as the number of ways of writing a number N as a sum of K(nonzero and nonnegative) numbers less than N. Kindly note that introducing zero in the partition set changes the scene alltogether and forms many new combinations. Argument : We clearly Define f(n,k) as the number of ways of attaining kpartitions of a number n. Let us divide the possible permutations into two groups : Group A : The permutations that have a "1" Group B : The permutations that do not have a "1" In A, since we have attained a 1, we now need k1 partitions such that they sum up to n1. This gives us f(n1,k1). In B, since all nos. are > 1, we can subtract 1 from each to decrease the overall sum required from n to nk (and yet no partition number becomes zero). This gives us f(nk,k). Thus the final result, f(n,k) = f(n1,k1) + f(nk,k). Hope this helps. answered 16 Jan '16, 22:57
@ankg : Thank you it really helped me :)
(17 Jan '16, 09:40)

Partitions can be graphically visualized with Young diagrams or Ferrers diagrams. For more details refer to this link answered 16 Jan '16, 23:12
