I found this recurrence f(n,k)=f(n-1,k-1)+f(n-k,k).But unable to understand how it works.
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.
5 Likes
Partitions can be graphically visualized with Young diagrams or Ferrers diagrams.
For more details refer to this link
