Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In a book I had read

The number of ways in which n different things can be arranged in r different groups is $n!\dbinom{n-1}{r-1}$

Question 1.
So I had interpreted it like this
First n things are arranged by $n!$ ways then then the gaps are chosen for separators(that separates different groups).Number of gaps is $n-1$ assuming no group is empty and we have to choose $r-1$ out of them, so $n!\dbinom{n-1}{r-1}$.
So have I interpreted it correctly?
If yes , then if groups can be empty so number of ways will be $n!\dbinom{n+1}{r-1}$ as in this case number of gaps will be $n+1$.

Question 2
Why cant I interpret it like this we have $n+r-1$ things in which $r-1$ are alike so the number of ways will be $\frac {(n+r-1)!}{(r-1)!}$(which is not correct according to the book).

share|improve this question
    
I don't understand Question 2. What are these $n+r-1$ things, and how and why are $r-1$ of them alike? –  joriki May 25 '12 at 13:22
    
@joriki: The original $n$ items, plus the $r-1$ separators. –  Arturo Magidin May 25 '12 at 13:24
    
Yes Arturo Magidin is correct there are n different things and r-1 alike separators. –  Saurabh May 25 '12 at 13:30
    
What does it mean to arrange $n$ people into $r$ different groups? Do you mean named groups? (So how many ways to divide say $2$ people, $3$ people? A count for small $n$, $r$ would help identify what is being counted.) –  André Nicolas May 25 '12 at 13:31
add comment

2 Answers

up vote 4 down vote accepted

Question 1. Yes, you can do it that way. Note, however, that in this interpretation, it matters in which group you are in. For example, if you have three people to put into three groups, it would count as different putting A in group 1, B in 2, and C in 3; from putting B in 1, C in 2, and A in 3; even though the final "groups" are identical in both cases. Moreover (as Joriki points out), it also matters in which order the people are listed within the groups.

For empty groups, however, your count is wrong, because it does not allow you to pick the same spot more than once. So you would be unable, for example, to divide 5 people into five groups by putting them all in the same group, because the separators have to go into different places; you allow a maximum of two empty groups by doing this, namely the empty group you can get by putting a "separator" before all the items, and/or one after all the times, but that's it. You would need to allow for repetitions to be able to count this properly.

Question 2. This would give you the correct count for possibly empty groups, whereas your previous attempt does not work; this method allows several empty groups, by putting your "separators" in the same gap.

share|improve this answer
1  
Not only which group people are in matters, but also their order within the group. –  joriki May 25 '12 at 13:38
    
Good point! Added. –  Arturo Magidin May 25 '12 at 13:39
add comment

We look at the problem of dividing $n$ people into $r$ named groups, some of them possibly empty. So we want to count the functions from an $n$-element set to an $r$-element set. There are $r^n$ of these.

The answer is quite different if the order of the people within groups matters. In that case, we order the people ($n!$ ways). For the rest, it is the usual stars and bars argument, where we count the number of ways to express $n$ as an ordered sum of non-negative integers, some possibly $0$. Solve the equivalent but easier to visualize problem of expressing $n+r$ as a sum of positive integers. By a "separators" argument, this is $\binom{n+r-1}{r-1}$. This gives $n!\binom{n+r-1}{r-1}$ ways to divide into ordered "groups."

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.