JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Basics of combinatorics (Article) Nice article
 Nice article | Reply The article is very nice, i hope another, a more advanced one comes through soon. Good effort.
 Re: Nice article (response to post by vinay.emani) | Reply I think it's very nice too.My 2 cents...Once I met problem “Derangements” on a math contest. The problem was to prove that f(n) always divisible by (n-1). Here f(n) - number of derangements, n>1. I solved it in slightly different manner.Proof:Statement is obvious when n = 2, so let n > 2Consider two different possibilities:1. Derangements like`1 2 ... i ... n....... n ... i`not hard to see that there are exactly (n-1) * f(n-2) of them2. All other derangements, so`1 2 ... i ... n....... j ... i j != n`Let's forget about last elements in both rows.If we look carefully, then we'll see that we canpainlessly rename "i" in upper row to "n" since j!= n.And when we do that it becomes obviously that there areexactly (n-1) * f(n-1) such derangements.So, f(n) = (n-1) * ( f(n-1) + f(n-2) )and is obviously divisible by (n-1).
 Re: Nice article (response to post by it4.kp) | Reply About derangements, the author remarks "This problem may not look very practical for use in TopCoder problems, but the thinking behind it is rather important, and these ideas can be widely applied."Presumably such a derivation would have been practical for this TopCoder problem...
 Re: Nice article (response to post by antimatter) | Reply You right :)And TC is not alone. You can see disguised version of this problem here:http://acm.timus.ru/problem.aspx?space=1&num=1366
 Re: Nice article (response to post by vinay.emani) | Reply The article is very nice, i hope another, a more advanced one comes through soon.I'll think of it :)