Here is a partial solution of the problem. For background on derangements:
[Derangements -- MathWorld, A Wolfram Web Resource]
http://mathworld.wolfram.com/Derangement.html
We can introduce an artificial distinction between the first and
second color (sock) assigned to each person, then switch the first and
second colors for certain persons so that the first socks form a
permutation of the n colors and the second socks a derangement of
those.
Counting such configurations leads to an overcount of the
distinguishable configurations of socks (where the two colors are an
unordered pair for each person) by at least a factor of two, for one
can switch the first and second sock for all persons simultaneously
and get a configuration that is different in the artificial sense
taken here but the same in the sense posed by gnuspeak-ga.
An exact count would be obtained in this fashion if we were to
partition the derangements according to the number of cycles therein.
We illustrate this for the cases of n = 3 and n = 4.
With n = 3 there are only two derangements and both are single cycles
of length 3. Therefore with the artificial distinction of a first row
socks which is one permutation and a second row which is a derangement
of the first row, we count:
3! * !3 = 6*2 = 12
But switching the two socks of the first person forces a switch in the
two socks of every person, to preserve the permutation-ness of the
first row, because the derangement in the second is the whole cycle.
Thus 12/2 = 6 is the count for n = 3 without regard to the socks'
order. A diagram of the artificial configurations is this, where the
top row contains "first" socks and the bottom row the "second" socks:
R G B R G B
G B R B R G
G B R G B R
R G B B R G
B R G B R G
R G B G B R
R B G R B G
G R B B G R
G R B G R B
R B G B G R
B G R B G R
R B G G R B
[Note that these configurations pair off by switching the top and bottom row.]
If we apply this to the case n = 4, we discover that there are n! = 24
possibilities for the top row and !n = 9 respective possibilities for
the bottom row, which suggests an answer of 24*9/2 = 108. But this is
an overestimate, because not every derangment with n = 4 is a whole
cycle of length 4.
In fact the nine derangements with n = 4 may be classified as six that
are cycles of length 4 and three that are a pair of transpositions
(cycles of length 2). The calculation must then be corrected to
divide by 2 for the derangements that contain a single cycle and by 4
for those which have two cycles:
4! * (6/2 + 3/4) = 24*(3 + 3/4) = 72 + 18 = 90
as gnuspeak-ga has claimed.
In an extended set of notes on counting techniques, here:
[Notes on counting, by Peter J. Cameron]
http://www.maths.qmw.ac.uk/~pjc/notes/counting.pdf
it is noted that the number of derangements of n items containing a
single cycle is simply (n-1)!, as may be seen (pg. 33) by writing the
first element followed by the remaining n-1 elements in any order as a
cycle.
For smallish values of n it is not difficult to classify the
derangements by the number of cycles contained. The cycle to which
the the first element belongs must, if not of length n, be of length
n-2 or less (since leaving a cycle of length 1 is tantamount to a
fixed point). Hence one can quickly build up a small table that
counts the number of derangements of n things containing m cycles by
recursion:
\ # containing m cycles
n \ 1 2 3 4
-----------------------------
2 | 1 0 0 0
3 | 2 0 0 0
4 | 6 3 0 0
5 | 24 20 0 0
6 | 120 130 15 0
7 | 720 924 210 0
We illustrate the extension to n = 7. There are !7 = round(7!/e) =
1854 derangements in all, and we begin by counting how many have
exactly two cycles. The first element must belong to a cycle of
length 2,3,4, or 5, leaving a cycle of complementary length 5,4,3, or
2. There are 6 possible subsets of size two that would contain the
first element, C(6,2) = 15 possible subsets of size three containing
the first element, C(6,3) = 20 of size four and C(6,4) = 15 of size
five. Applying the numbers of derangements for cycles of these
smaller sizes:
# derangements of 7 items containing 2 cycles = 6 * 1 * 24
+ 15 * 2 * 6
+ 20 * 6 * 2
+ 15 * 24 * 1
= 924
Likewise the cycle containing the first element could of length 2 or 3
and leave room for two more cycles:
# derangements of 7 items containing 3 cycles = 6 * 1 * 20
+ 15 * 2 * 3
= 210
Finally no choice of length for the cycle containing the first element
allow an additional three cycles, so it is not possible for a
derangement of 7 items to contain 4 or more cycles. [There are
however 7*15 = 105 derangements of 8 items containing 4 cycles
(transpositions).]
regards, mathtalk-ga |
