| Re .2:
That's not sufficient. It doesn't matter whether the order is
randomized when the selection process is restarted. The chance of a
selecting a derangement of seven people which is a single 7-cycle is
252709/475035. But there are 720 7-cycles on seven people (720 ways to
arrange seven people in a circle) and 1854 derangements of seven
people, so if the probability of each derangement were equal, that
would be a 40/103 chance of selecting a single 7-cycle.
Actually, the simplest case is four people. With four people, there is
a 10/31 chance of getting two 2-cycles and a 21/31 chance of getting
one 4-cycle. But there are 3 derangements that are two 2-cycles and 6
that are 4-cycles, so that should be 1/3 and 2/3.
Proof:
The derangements of four people are { (ab)(cd), (ac)(bd), (ad),(bc),
(abcd), (abdc), (acbd), (acdb), (adbc), (adcb) }. ("(xyz)" indicates
the operation of mapping x to y, y to z, and z to x.)
Start the selection process. Let the choosers be denoted a, b, c, and
d, in that order. There is a 1/3 chance that a chooses b. If that
happens, there is a 1/3 chance that b chooses a, forcing c and d to
choose each other, so that's a 1/9 chance of (ab)(cd).
a chooses a person:
1/3 b
1/3 c
1/3 d
b chooses a person:
1/3*1/3 ba
1/3*1/3 bc
1/3*1/3 bd
1/3*1/2 ca
1/3*1/2 cd
1/3*1/2 da
1/3*1/2 dc
c and d each choose a person, with d's choice always being forced and
c's choice sometimes being forced:
1/3*1/3*1 badc = 1/9 for (ab)(cd)
1/3*1/3*1/2 bcad = 1/18 for selection is restarted
1/3*1/3*1/2 bcda = 1/18 for (abcd)
1/3*1/3*1 bdac = 1/9 for (abdc)
1/3*1/2*1/2 cabd = 1/12 for selection is restarted
1/3*1/2*1/2 cadb = 1/12 for (acdb)
1/3*1/2*1/2 cdab = 1/12 for (ac)(bd)
1/3*1/2*1/2 cdba = 1/12 for (acbd)
1/3*1/2*1 dabc = 1/6 for (adcb)
1/3*1/2*1/2 dcab = 1/12 for (adbc)
1/3*1/2*1/2 dcba = 1/12 for (ad)(bc)
That totals 5/36 for restarting the selection, 21/36 for single
4-cycles and 10/36 for pairs of 2-cycles. When the selection is
restarted, single 4-cycles still have a probability of 21/36 on each
go-around, no matter how the people are rearranged, and pairs of
2-cycles still have probability 10/36.
With the process repeated until it terminates, the probability of a
single 4-cycle approaches 21/36 * 36/31 = 21/31, and pairs of 2-cycles
approach 10/31.
By the way, if, during the selection process, there are m people left
to choose and there are n unclosed chains of people already selected,
there is a (m-n)(m-1-n)/(m^2-m) probability of making a new chain, a
(2m^2n-2mn^2-mn+n^2)/(m^3-m^2) probability of increasing a chain by
one, a n(n-1)/m^2 probability of merging two chains, and a n/m^2
probability of closing a chain. When m is 2 and n is 1, closing a
chain leaves the last person with themself and forces selection to
start over.
How many times a chain is closed reveals the number of cycles in the
final derangement, but not the lengths of those chains, so the above
does not distinguish derangements of six people into a 4-cycle and a
2-cycle versus a pair of three-cycles. The easiest thing to calculate
is the probability of a single cycle.
If derangements have equal probability, the probability of a
derangement consisting of a set of cycles with lengths l_0, l_1, l_2, .
. . l_m is (the factorial of the number of people) divided by the
length of each cycle, and then divided by the permutations of the
equal-length cycles. (Divide by 2! for each pair of equal-length
cycles, by 3! for each triple, by 4! for each quadruple, and so on.)
E.g., for seven people, the derangements are:
7-cycle: 7!/7 = 720.
5-cycle, 2-cycle: 7!/5/2 = 504.
4-cycle, 3-cycle: 7!/4/3 = 420.
3-cycle, two 2-cycles: 7!/3/2/2/2! = 210.
-- edp
|
| Here's a program which computes the probability that a derangement
selected from a uniform distribution of derangements does not contain a
swap of two elements. The probability rapidly approaches .606531 as
the number of objects increases.
-- edp
/* A derangement of a set of objects is a permutation which maps no object
* into itself. Each permutation has a unique decomposition into disjoint
* cycles.
*
* For given numbers l_0, l_1, l_2, . . . l_e and m_0, m_1, m_2, . . . m_e,
* where no two l's are equal, it is possible to calculate the number of
* permutations whose decomposition consists of m_0 cycles of length l_0,
* m_1 cycles of length l_1, m_2 cycles of length l_2, . . . m_e cycles
* of length l_e.
*
* The number of such permutations is:
*
* n! / product {i = 0 to e } (l_i * m_i!),
*
* where n is the total of all the lengths.
*
* To derive this formula, first consider writing each of the cycles
* sequentially. A cycle can be denoted by (a b c . . z), where the cycle
* maps a to b, b to c, and so on, with z being mapped to a. A cycle of
* length l has l spaces in its denotation. And cycles with lengths
* totalling n have n spaces for objects. Each permutation of n objects
* can be used to fill in those spaces, creating a mapping between the n!
* permutations of n objects and the cycles with the described lengths. But
* this mapping is not one-to-one. (a b c) and (b c a) denote the same
* cycle. Each cycle of length l can be represented l different ways. So
* dividing n! by the length of each cycle eliminates those duplications.
* Also, (a b c)(d e f) and (d e f)(a b c) represent the same permutation
* composed of two cycles. Dividing n! by the number of ways to permute
* each set of cycles of equal length removes those duplications. The result
* is the above formula.
*
* For a given n, the program below generates all the partitions of n that
* do not have 1 as an element. Then it computes the number of permutations
* corresponding to that partition (except that n! is left out of the
* computation, as it is eliminated eventually anyway). Since cycles of
* length one are omitted, this gives us the numbers of derangements. The
* numbers of derangements are totalled, and the numbers of derangements
* containing no cycles of length two are also totalled. The latter number
* is divided by the former to give the probability that a derangement
* selected from a uniform distribution of derangements does not contain a
* swap.
*/
#include stdio
#define MEMORY 0
#define INPUT 1
#define min(a,b) ((a) < (b) ? (a) : (b))
void got_one(int *beginning, int *end);
void panic(int error);
int derangements(int *origin, int *current, int n, int high);
double total, no_pairs;
int main(void)
{
int *c, i, n;
if (1 != scanf("%d", &n) || n <= 1)
panic(INPUT);
if (! (c = calloc(n, sizeof *c)) )
panic(MEMORY);
total = no_pairs = 0.0;
/* Using memory at location c, generate derangements of n objects,
* with n being the maximum cycle length, initially.
*/
derangements(c, c, n, n);
printf(
"The probability of no pairs in a derangement of %d objects is %g.\n",
n, no_pairs/total);
}
/* "derangements" generates sets of numbers such that:
*
* Each number is at least two.
* The numbers add up to "n".
* The highest number is not greater than "high".
*
* When "high" is not less than "n", the above is equivalent to the
* partitions of n which do not contain 1.
*
* Memory beginning at "current" is used to hold each set in turn. If
* the set containing only n meets the above requirements, it is the first
* such set, and "got_one" is called to process the set. Then this routine
* sets the first location in memory to possible values and calls itself to
* fill out the rest of the set.
*/
int derangements(int *origin, int *current, int n, int high)
{
int num = 0;
if (n <= high)
{
*current = n;
num++;
got_one(origin, current);
}
for (*current = min(high, n-2); *current > 1; --*current)
num += derangements(origin, current+1, n-*current, *current);
return num;
}
/* Given a partition of some number, "got_one" computes the numbers of
* permutations composed of cycles with lengths equal to the numbers in
* the partition. "got_one" keeps a total of these numbers and a total
* of the numbers of permutations that do not contain swaps of two elements.
*
* The elements of the partition are in memory locations from "beginning" to
* "end".
*/
void got_one(int *beginning, int *end)
{
double p = 1.0;
int *c, j = 1;
/* Conceptually, p is initialized to n!. But since n! cancels
* out when our two totals are divided, we simply initalize it
* to the constant 1.0.
*
* c is used to point to the elements of the partition.
* j keeps track of the number of identical lengths seen in
* the current run.
*/
/* For each length but the last, divide by that length. Also
* divide by the number of identical lengths seen in the current
* run. When the current run is complete, we will have divided
* by the factorial of the length of the run of identical lengths
* -- and that factorial is the number of ways to permute the
* elements of the run.
*/
for (c = beginning; c < end; c++)
{
p /= *c * j;
if (*c == *(c+1))
j++;
else
j = 1;
}
/* Process the last element just as all the others -- but skip
* the adjustment of j so that we don't refer to the non-existent
* element *(c+1).
*/
p /= *c * j;
total += p;
if (*c > 2)
no_pairs += p;
}
void panic(int error)
{
switch (error)
{
case MEMORY:
fprintf(stderr, "Out of memory.\n");
break;
case INPUT:
fprintf(stderr, "Input error.\n");
break;
}
exit();
}
|