You are not logged in. Please login at www.codechef.com to post your questions!

×

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

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

pallesai's gravatar image

4★pallesai
176830
accept rate: 17%


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.

link

answered 16 Jan '16, 22:57

ankg's gravatar image

3★ankg
2113
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

link

answered 16 Jan '16, 23:12

yash_chauhan28's gravatar image

4★yash_chauhan28
621
accept rate: 50%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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