Binomial question

Forum for the GRE subject test in mathematics.
Kleene
Posts: 7
Joined: Wed Feb 26, 2014 12:35 pm

Binomial question

Postby Kleene » Fri Feb 06, 2015 8:40 pm

Hi there,

Apparently it should be rather easy, but I cannot figure it out. We have n piles and want to divide at most k over these piles. The number of possibilities is (n+k) choose n, but why?

Example to illustrate the problem:
n = 2
k = 2

The possibilities: (0,0), (0,1), (1,0), (2,0), (1,1), (0,2)

mathrocks
Posts: 6
Joined: Mon Jan 19, 2015 11:35 pm

Re: Binomial question

Postby mathrocks » Fri Feb 06, 2015 8:51 pm

It is appropriate to use a Stars and Bars argument in this case: http://en.wikipedia.org/wiki/Stars_and_bars_%28combinatorics%29 . You can add an extra pile to make the problem easier where the extra pile is the remaining number of objects that you don't use. Hence. you want to distribute k objects over n+1 piles, and the argument follows:)




Return to “Mathematics GRE Forum: The GRE Subject Test in Mathematics”



Who is online

Users browsing this forum: Bing [Bot] and 6 guests

cron