Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 CycleLengthCountList

Source Notebook

List the possible cycle length counts of permutations of a given length

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

ResourceFunction["CycleLengthCountList"][n]

returns a list of all possible cycle length counts that represent a partitioning of permutations of size n into disjoint cycles.

Details and Options

ResourceFunction["CycleLengthCountList"] returns a list of SparseArray objects representing {{λ11,…,λ1n},…,{λ{XMLElement[span, {class -> stylebox}, {XMLElement[i, {class -> ti}, {k}], 1}]},…,λkn}}, where {λ{XMLElement[span, {class -> stylebox}, {XMLElement[i, {class -> ti}, {i}], 1}]},…,λin} is a list of possible cycle length counts for an n-permutation.
The list {λ{XMLElement[span, {class -> stylebox}, {XMLElement[i, {class -> ti}, {i}], 1}]},…,λin} is known as a cycle type.

Examples

Basic Examples (2) 

Possible cycle length counts for 5-permutations:

In[1]:=
ResourceFunction["CycleLengthCountList"][5]
Out[1]=

See the values:

In[2]:=
Normal[%] // Column
Out[2]=

Properties and Relations (3) 

There are exactly as many cycle types of n-permutations as there are integer partitions of n:

In[3]:=
n = 10;
In[4]:=
{Length[IntegerPartitions[n]], Length[ResourceFunction["CycleLengthCountList"][n]]}
Out[4]=

Use the resource function PermutationCountByCycleLength to count the number of permutations of each possible type:

In[5]:=
n = 5;
In[6]:=
ResourceFunction["CycleLengthCountList"][n] // Normal
Out[6]=
In[7]:=
ResourceFunction["PermutationCountByCycleLength"] /@ %
Out[7]=

As expected, there are n! permutations in total:

In[8]:=
Total[%]
Out[8]=
In[9]:=
% == n!
Out[9]=

Counting possible permutations of each type is the same as tallying cycle length counts in the Permutations list:

In[10]:=
{#, ResourceFunction["PermutationCountByCycleLength"][#]} & /@ Sort[ResourceFunction["CycleLengthCountList"][n] // Normal]
Out[10]=
In[11]:=
Tally[Sort[ Normal[ResourceFunction["CycleLengthCounts"] /@ Permutations[Range[5]]]]]
Out[11]=
In[12]:=
% === %%
Out[12]=

Version History

  • 1.0.0 – 09 July 2020

Related Resources

Author Notes

Watson's book and the DLMF associate two functions with Lommel, denoted sμ,ν(z) and Sμ,ν(z). LommelS implements the latter one, since the former is undefined when μ±ν is an odd negative integer.

License Information