Author |
Topic: A Possibility-related formula (Read 2383 times) |
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
 |
A Possibility-related formula
« on: Mar 14th, 2006, 11:24am » |
 Quote  Modify
|
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
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: A Possibility-related formula
« Reply #1 on: Mar 14th, 2006, 11:50am » |
Quote Modify
|
Quote:Yes. You can further generalize it for dividing a group into unequal (nonempty) groups.
If you have s groups ri (summing to n)
then it's n!/( s! * [prod]ri! )
n!/[prod]ri! (where [sum](ri) = n) is known as the multinomial, a generalization of the binomial.
Quote:No, but I could perhaps show it.
|
| « Last Edit: Mar 14th, 2006, 11:55am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print