-----------------------------------

chelseafc

Mon Dec 22, 2008 7:03 pm


[help] can anyone help me???

-----------------------------------

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 :) [syntax="java"]Code Here[/syntax]


-----------------------------------

jbking

Mon Dec 22, 2008 10:10 pm


RE:[help] can anyone help me???

-----------------------------------

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

Mon Dec 22, 2008 10:30 pm


RE:[help] can anyone help me???

-----------------------------------

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

Mon Dec 22, 2008 10:57 pm


Re: [help] can anyone help me???

-----------------------------------

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."

[url=http://www.math.uwaterloo.ca/CandO_Dept/index.shtml]Waterloo has a "Combinatorics and Optimization" department within the Math faculty that may be of interest if you like this type of problem.