Identical/Non-identical Groups; Derangements
Date: 03/10/2000 at 04:54:27 From: Shweta Kala Subject: Permutations and Combinations Sir, I was not able to understand the following: 1) The number of ways of dividing mp things into m identical groups of p things each = (mp)!/[(m!)(p!)^m] 2) The number of ways of dividing mp things into m different, non-identical groups of p things each = (mp)!/(p!)^m 3) Derangements: If n things are arranged in a row, the number of ways in which they can be deranged so that no one of them occupies its original place = n!(1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n.1/n!) Why is there a different formula for derangements? Why isn't it = P(n,n) - 1 After all, it is the number of arrangements of n things except the original arrangement. Kindly help me with this. Thank you, Shweta Kala
Date: 03/10/2000 at 07:23:04 From: Doctor Anthony Subject: Re: Permutations and Combinations 1) In this situation the 'containers' of the groups are indistinguishable, so you could swap the complete groups around in m! ways without giving rise to a different combination. An example would be putting p people into car(1), p people into identical car(2), p people into identical car(3) and so on. We are only concerned with the groups of people, and NOT worried about which car they are in. 2) Here the 'containers' of the groups are different, e.g. you may be putting p people into one house, another p people into a local hotel, another p people into tents, and so on. 3) Derangements: P(n,n) = n! and (n! - 1) would allow many of the n objects to be in their original positions. For a derangement we require EVERY single object to be in a different position from where it was in the first arrangement. A typical problem is that of the careless secretary who puts letters at random into envelopes. We require the probability that EVERY letter goes to a wrong address. For an explanation of this problem, see: Letters and Envelopes and the Inclusion-Exclusion Principle http://mathforum.org/dr.math/problems/jarrad03.27.99.html - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.