Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 PermutationCountByCycleLength

Source Notebook

Calculate the number of permutations of the specified cycle length counts

Contributed by: Wolfram Staff (original content by Sriram V. Pemmaraju and Steven S. Skiena)

ResourceFunction["PermutationCountByCycleLength"][{λ1,λ2,…}]

gives the number of permutations of the specified cycle length counts {λ1,λ2,…}.

Details and Options

The number of permutations with a given list of cycle length counts {λ1,λ2,…} is , where n is the length of the list.
As the list {λ1,λ2,…} is also known as the permutation type, ResourceFunction["PermutationCountByCycleLength"] returns the number of permutations by type.

Examples

Basic Examples (1) 

The number of 6-permutations that have two 1-cycles and three 2-cycles:

In[1]:=
ResourceFunction["PermutationCountByCycleLength"][{2, 3, 0, 0, 0, 0}]
Out[1]=

Properties and Relations (4) 

There are (n-1)! n-permutations with one cycle:

In[2]:=
p = {0, 0, 0, 0, 1};
In[3]:=
ResourceFunction["PermutationCountByCycleLength"][p]
Out[3]=
In[4]:=
% == (Length[p] - 1)!
Out[4]=

There are n(n-2)! n-permutations with one singleton cycle and one (n-1)-cycle:

In[5]:=
p = {1, 0, 0, 1, 0};
In[6]:=
ResourceFunction["PermutationCountByCycleLength"][p]
Out[6]=
In[7]:=
% == Length[p] (Length[p] - 2)!
Out[7]=

The CycleLengthCountList resource function is a list of all possible cycle length counts (permutation types) into which an n-permutation can be partitioned:

In[8]:=
n = 5;
In[9]:=
ResourceFunction["CycleLengthCountList"][n] // Normal
Out[10]=

Count permutations by type:

In[11]:=
Total[ResourceFunction["PermutationCountByCycleLength"] /@ %]
Out[11]=

As expected, there are n! permutations:

In[12]:=
% == n!
Out[12]=

Use PermutationCountByCycleLength to tally the number of permutations of all the possible types:

In[13]:=
{#, ResourceFunction["PermutationCountByCycleLength"][#]} & /@ Sort[ResourceFunction["CycleLengthCountList"][n] // Normal]
Out[13]=

Tallying CycleLengthCounts in the Permutations list gives the same result:

In[14]:=
Tally[Sort[ Normal[ResourceFunction["CycleLengthCounts"] /@ Permutations[Range[5]]]]]
Out[14]=
In[15]:=
% === %%
Out[15]=

Version History

  • 1.0.0 – 09 July 2020

Related Resources

License Information