The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Identical/Non-identical Groups; Derangements

Date: 03/10/2000 at 04:54:27
From: Shweta Kala
Subject: Permutations and Combinations


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   

- Doctor Anthony, The Math Forum   
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.