[help] can anyone help me???

[chelseafc]

Java:

private static int partition(int n, int k) {     if (k > n)         return 0;     else if (k == n)         return 1;     else if (k == 0)         return 0;     else         return partition(n - 1, k - 1) + partition(n - k, k); }

Can anyone explain to me how this recursive method returns the number of ways n can be written as a sum of k positive integers???
I don't understand why the sum of the ways n-1 can be written as k-1 integers and n-k can be written as k integers are equal to the ways that n can be written as k integers.
Thanks!!!

Mod Edit: Remember to use syntax tags! Thanks

code:

[syntax="java"]Code Here[/syntax]

[jbking]

The partition(n-1,k-1) is a list that you could simply add a + 1 to to get some of the partition solutions for (n,k) where 1 is part of the solution.

Now, as for the other value, think about what the other combinations would be where there isn't a 1 in the list as those were counted above. Now, what do all these look like? Well, if you subtract 1 from each integer the total will now be (n-k) as there were k values and you still want to use k integers to produce that sum.

[chelseafc]

OH!
I finally understand now thanks to your explanation!!
Actually this is a dwite question on 2007 January.
I now completely understand it!!

Thank you very much,jbking!!

[jbking]

Just as a side note, this type of problem is commonly found in a branch of Mathematics called "Combinatorics" where generating functions tend to be used to find various solutions. Combinatorics, to me at least, is generally a fancy way of counting things usually called "Enumeration." It does have its interesting elements, like how many different Lotto 6/49 combinations are there or how many ways can one schedule a tournament using what are called "Combinatorial Designs."

Waterloo has a "Combinatorics and Optimization" department within the Math faculty that may be of interest if you like this type of problem.