No of ways to express a number N as a sum of K partitions

dynamic-programming

#1

I found this recurrence f(n,k)=f(n-1,k-1)+f(n-k,k).But unable to understand how it works.


#2

Assumptions :-

  • The set of partitions here refers to the valid numbers into which n can split.
  • Zero does not belong to the set of partitions. The set of partitions consists only of natural numbers.
  • n>k. In the base case when n < k, f(n,k) = 0 and when n==k, f(n,k) = 1

The Question can also be clearly formulated as the number of ways of writing a number N as a sum of K(non-zero and non-negative) numbers less than N. Kindly note that introducing zero in the partition set changes the scene all-together and forms many new combinations.

Argument :-

We clearly Define f(n,k) as the number of ways of attaining k-partitions 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 k-1 partitions such that they sum up to n-1. This gives us f(n-1,k-1).

In B, since all nos. are > 1, we can subtract 1 from each to decrease the overall sum required from n to n-k (and yet no partition number becomes zero). This gives us f(n-k,k).

Thus the final result, f(n,k) = f(n-1,k-1) + f(n-k,k).

Hope this helps.


#3

Partitions can be graphically visualized with Young diagrams or Ferrers diagrams.

For more details refer to this link


#4

@ankg : Thank you it really helped me :slight_smile: