Number of ways m+n things can be divided into classes containing m,n things severally.

A

Aion

Junior Member
Joined
May 8, 2018
Messages
145
I have a question about a corollary from a proof from Higher Algebra by Hall and knight.

146. To find the number of ways in which [imath]m+n[/imath] things can be divided into groups of [imath]m[/imath] and [imath]n[/imath] things respectively.

Proof: This is equivalent to finding the number of combinations of [imath]m+n[/imath] things [imath]m[/imath] at a time, for every time we select one group of [imath]m[/imath] things we leave a group of [imath]n[/imath] things behind. Thus the required number is

[math]\binom{m+n}{m}=\frac{(m+n)!}{m!n!}[/math]
Corollary. If [imath]n=m[/imath], the groups are equal, and in this case, the number of different ways of subdivision is

[math]\frac{(2m)!}{m!m!2!};[/math]
for in any one way, it is possible to interchange the two groups without obtaining a new distribution.
...............................................................................................................................................................................................................................................................................................................................

To understand the corollary provided above, I've tried to delve into the reasoning step-by-step.


Let's consider when [imath]n=m[/imath]. The total number of things is [imath]2m[/imath]. We divide these [imath]2m[/imath] things into two groups, each containing [imath]m[/imath] things. Applying the same logic as above this is equivalent to choosing [imath]m[/imath] things out of [imath]m+m[/imath] things because the remaining [imath]m[/imath] things will automatically form the second group. We use the binomial coefficient to find the number of ways to choose [imath]m[/imath] things out of [imath]2m[/imath] things.

[math]\binom{2m}{m}=\frac{(2m)!}{m!m!};[/math]
Suppose we denote the equal objects as [imath]m_1[/imath] and [imath]m_2[/imath] such that [imath]m_1=m_2=m[/imath].

The division by 2 accounts for the fact that

[math]\frac{(2m_1)!}{m_1!m_1!}=\frac{(2m_2)!}{m_2!m_2!}[/math]
Since [imath]m_1[/imath] and [imath]m_2[/imath] are equal in size, swapping them does not result in a new unique division. This means each unique division of the [imath]2m[/imath] things into two equal groups is counted twice in the binomial coefficient calculation. Therefore, the number of unique ways to divide [imath]2m[/imath] things into two groups of [imath]m[/imath] things each is:

[math]\frac{(2m)!}{m!m!2!};[/math]
I apologize if this seems trivial, but I would really appreciate it if you could confirm whether my reasoning is correct.
 
Last edited:
Aion said:
I have a question about a corollary from a proof from Higher Algebra by Hall and knight.

146. To find the number of ways in which [imath]m+n[/imath] things can be divided into groups of [imath]m[/imath] and [imath]n[/imath] things respectively.

Proof: This is equivalent to finding the number of combinations of [imath]m+n[/imath] things [imath]m[/imath] at a time, for every time we select one group of [imath]m[/imath] things we leave a group of [imath]n[/imath] things behind. Thus the required number is

[math]\binom{m+n}{m}=\frac{(m+n)!}{m!n!}[/math]
Corollary. If [imath]n=m[/imath], the groups are equal, and in this case, the number of different ways of subdivision is

[math]\frac{(2m)!}{m!m!2!};[/math]
for in any one way, it is possible to interchange the two groups without obtaining a new distribution.
...............................................................................................................................................................................................................................................................................................................................

To understand the corollary provided above, I've tried to delve into the reasoning step-by-step.


Let's consider when [imath]n=m[/imath]. The total number of things is [imath]2m[/imath]. We divide these [imath]2m[/imath] things into two groups, each containing [imath]m[/imath] things. Applying the same logic as above this is equivalent to choosing [imath]m[/imath] things out of [imath]m+m[/imath] things because the remaining [imath]m[/imath] things will automatically form the second group. We use the binomial coefficient to find the number of ways to choose [imath]m[/imath] things out of [imath]2m[/imath] things.

[math]\binom{2m}{m}=\frac{(2m)!}{m!m!};[/math]
Suppose we denote the equal objects as [imath]m_1[/imath] and [imath]m_2[/imath] such that [imath]m_1=m_2=m[/imath].

The division by 2 accounts for the fact that

[math]\frac{(2m_1)!}{m_1!m_1!}=\frac{(2m_2)!}{m_2!m_2!}[/math]
Since [imath]m_1[/imath] and [imath]m_2[/imath] are equal in size, swapping them does not result in a new unique division. This means each unique division of the [imath]2m[/imath] things into two equal groups is counted twice in the binomial coefficient calculation. Therefore, the number of unique ways to divide [imath]2m[/imath] things into two groups of [imath]m[/imath] things each is:

[math]\frac{(2m)!}{m!m!2!};[/math]
I apologize if this seems trivial, but I would really appreciate it if you could confirm whether my reasoning is correct.
Click to expand...
I think you're right, basically expanding on the statement "it is possible to interchange the two groups without obtaining a new distribution".

If I were the author, I would have said some things differently, to emphasize that the problem itself is being understood differently when m=n than the general case. In dividing into groups of m and n respectively ([imath]m\ne n[/imath]), we have two inherently distinguishable groups, so the original formula applies. When m=n, we are no longer able to distinguish the groups inherently; if we asked the question in terms of making, say, a group of m on the left and a group of n on the right, then we would be distinguishing the groups explicitly, and would not need to divide by 2 when m=n.

It just feels a little misleading to treat this as one problem and only mention m=n after the fact. It would be clearer, to my mind, if the second part were stated separately, as "To find the number of ways in which 2n things can be divided into two groups of n things". But that's because I'm very sensitive to the fact that wording of combinatorics problems (and others) is often contrary to the way normal humans interpret sentences, and it can be easy to misconstrue which things are distinct, especially for students.
 
This problem has been bothering me and now I know why.
The corollary is fine. However, the original theorem is not valid. The original theorem never stated that m and n had to be distinct! That formula that they gave you is not valid when m=n.
 
Steven G said:
This problem has been bothering me and now I know why.
The corollary is fine. However, the original theorem is not valid. The original theorem never stated that m and n had to be distinct! That formula that they gave you is not valid when m=n.
Click to expand...
... or, if one prefers, it is valid when m=n only if interpreted as I suggested, with two piles designated by position, and not only by size.
 
Dr.Peterson said:
... or, if one prefers, it is valid when m=n only if interpreted as I suggested, with two piles designated by position, and not only by size.
Click to expand...
Yes Dr Peterson. I read what you wrote after my post. Thanks!
 
You must log in or register to reply here.
Top