wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> A Possibility-related formula
        
(Message started by: Sjoerd Job Postmus on Mar 14^th, 2006, 11:24am)

Title: A Possibility-related formula
Post by Sjoerd Job Postmus on Mar 14^th, 2006, 11:24am

Heya guys,

During a math-lesson a week ago, we had a couple of questions, in the general form of:

You have <n> people, and want to divide it into <s> groups with <r> people in each. How many ways are there to do that, if you don't care about the order of the groups, or the order of the people in the groups?

Example: 22 persons, 2 soccer teams ( 11players each )
Example: 10 persons, groups of two. (5 groups)

The first solution was something like
22 Choose 11
------------------
2

The second solution was
10!
-----
5! * 2^5

(Ten persons, all possible permutations. Divide by 5! to ignore the same groups in different orders, divide by 2 for each group to ignore orders in each group...

Now, I was wondering, can I generalize this, and I managed.

r people in s groups:
n = r * s

possibilities = n! / ( s! * (r!)^s)

Is my formula correct? Can you prove it? My intuition tells me the formula works, and also some experimenting.

If you care about the order of the groups, cancel the s!, if you care about the order inside the groups, cancel out the (r!)^s

Again, is this formula correct? Is it a known formula, or have I been in the unlikely situation to think of something new?

-Regards,
Sjoerd Job Postmus

Title: Re: A Possibility-related formula
Post by towr on Mar 14^th, 2006, 11:50am

Quote:

Is my formula correct?

Yes. You can further generalize it for dividing a group into unequal (nonempty) groups.
If you have s groups r_i (summing to n)
then it's n!/( s! * [prod]r_i! )

n!/[prod]r_i! (where [sum](r_i) = n) is known as the multinomial, a generalization of the binomial.

Quote:

Can you prove it?

No, but I could perhaps show it.