An elementary counting argument

At first when I read about this problem from a certain Indonesian olympiad, I was puzzled as to how would one solve it. It was a pretty nice revelation of strength of proof methods after I solved it.

Find a closed form for \sum x_1x_2\dots x_k where x_1+x_2+\dots +x_k=n. The summmation runs over every possible non negative solution of the equation.

First, I observed that a particular product form in the summation like x_1x_2\dots x_n meant selecting one element out of every block created by the composition. This was a clear invitation to a bijection, I just had to find another way of doing it. We can separate n with 2k-1 slashes where the alternating slashes could mean selecting an element out of a block and closure of a block. Some more tinkering lead to a neat closed form.

Advertisements

ನಿಮ್ಮದೊಂದು ಉತ್ತರ

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s