Get permutation count

Question

I searching for an algorithm which gives me the permutation count of the elements 1....n. If i define the cycle lengths.

For example n := 4

<Set of cycle lengths> -> permutation count

1,1,1,1 -> 1 read 4 cycles of length 1 leads to 1 permutation: 1,2,3,4

1,1,2 -> 5 read 2 cycles of length 1 and 1 cycle of length 2 leads to 5 permutations: 1,2,4,3, 1,4,3,2, 1,3,2,4, 2,1,3,4, 3,2,1,4,

2,2 -> 3 read 2 cycles of length 2 leads to 3 permutations: 2,1,4,3, 3,4,1,2,4,3,2,1

1,3 -> 9 read 1 cycle of length 1 and 1 cycle of length 3 leads to 9 permutations 1,3,2,4, 1,3,4,2, 1,4,2,3, 2,3,1,4, 2,4,3,1, 3,1,2,4, 3,2,4,1,4,1,3,2, 4,2,1,3,

4 -> 6 read 1 cycle of length 4 leads to 6 permutations: 2,3,4,1, 2,4,1,3, 3,1,4,2, 3,4,2,1, 4,1,2,3, 4,3,1,2

How can i compute the permutation count of a given set consisting cycle lengths? Iterating through all permutations is not an option.

Answer 1

For a given cycle type, we can produce a permutation with that cycle type by writing down a permutation of the list 1, ..., n and then bracketing it appropriately, according to the lengths in the cycle type, to get a permutation written in cycle notation.

For example, if we want cycle type (3, 2, 2), then the permutation 1, 2, 3, 4, 5, 6, 7 is bracketed as (1 2 3)(4 5)(6 7), while 5, 1, 6, 2, 4, 3, 7 gives (5 1 6)(2 4)(3 7).

It's clear that we get all permutations of cycle type (3, 2, 2) this way, but it's also clear that we can get each permutation in multiple different ways. There are two causes of overcounting: first, we can make a cyclic shift for any of the cycles: (5 1 6)(2 4)(3 7) is the same permutation as (1 6 5)(2 4)(3 7) or (6 5 1)(2 4)(3 7). Second, cycles of the same length can be permuted arbitrarily: (5 1 6)(2 4)(3 7) is the same permutation as (5 1 6)(3 7)(2 4). A bit of thought should convince you that these are the only possible causes of overcounting.

To account for both causes of overcounting, we divide the total number of permutations by (a) the product of the cycle lengths, and also (b) the factorial of the number of cycles for any given cycle length. In the (3, 2, 2) case: we divide by 3 × 2 × 2 for (a), and 2! for (b), because there are two cycles of length 2.

Since this is Stack Overflow, here's some Python code:

from collections import Counter
from math import factorial

def count_cycle_type(p):
    """Number of permutations with a given cycle type."""

    count = factorial(sum(p))
    for cycle_length, ncycles in Counter(p).items():
        count //= cycle_length ** ncycles * factorial(ncycles)
    return count

Example:

>>> count_cycle_type((2, 2))
3
>>> count_cycle_type((3, 2, 2))
210

To double check correctness, we can add the counts for all cycle types of a given length n, and check that we get n!. The cycle types are the partitions of n. We can compute those fairly simply by a recursive algorithm. Here's some code to do that. partitions is the function we want; bounded_partitions is a helper.

def bounded_partitions(n, k):
    """Generate partitions of n with largest element <= k."""
    if k == 0:
        if n == 0:
            yield ()
    else:
        if n >= k:
            for c in bounded_partitions(n - k, k):
                yield (k,) + c
        yield from bounded_partitions(n, k - 1)


def partitions(n):
    """Generate partitions of n."""
    return bounded_partitions(n, n)

Example:

>>> for partition in partitions(5): print(partition)
... 
(5,)
(4, 1)
(3, 2)
(3, 1, 1)
(2, 2, 1)
(2, 1, 1, 1)
(1, 1, 1, 1, 1)

And here's the double check: the sum of all the cycle type counts, for total lengths 5, 6, 7 and 20. We get the expected results of 5!, 6!, 7! and 20!.

>>> sum(count_cycle_type(p) for p in partitions(5))
120
>>> sum(count_cycle_type(p) for p in partitions(6))
720
>>> sum(count_cycle_type(p) for p in partitions(7))
5040
>>> sum(count_cycle_type(p) for p in partitions(20))
2432902008176640000
>>> factorial(20)
2432902008176640000

Answer 2

This can be broken down into:

1. The number of ways to partition elements in to buckets matching the required count of elements with each distinct cycle size;
2. Multiplied by, for each distinct cycle size, the number of unique ways to partition the elements evenly into the required number of cycles;
3. Multiplied by, for each cycle, the number of distinct cyclic orderings

1: For bucket sizes s₁...s_k, that works out to n!/(s₁! * ... * s_k!)

2: For a bucket containing m elements that must be partitioned into c cycles, there are m!/( (m/c)!^c * c! ) ways

3: For a cycle containing m elements, there are (m-1)! distinct cyclic orderings if m > 1, and just 1 ordering otherwise