×

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

 0 I found this recurrence f(n,k)=f(n-1,k-1)+f(n-k,k).But unable to understand how it works. asked 16 Jan '16, 21:19 4★pallesai 176●8●30 accept rate: 17%

 5 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. answered 16 Jan '16, 22:57 3★ankg 211●3 accept rate: 33% @ankg : Thank you it really helped me :) (17 Jan '16, 09:40) pallesai4★
 -2 Partitions can be graphically visualized with Young diagrams or Ferrers diagrams. For more details refer to this link answered 16 Jan '16, 23:12 62●1 accept rate: 50%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,167

question asked: 16 Jan '16, 21:19

question was seen: 4,257 times

last updated: 17 Jan '16, 09:40