# How to find the cycle type vector of a random permutation

Given a random permutation $$\pi$$ of {1,2,...,n}, I want to produce a list {a1,a2,...,an} of nonnegative integers so that ai is the number of cycles in $$\pi$$ of length i for each i=1,2,...,n. For example, in the permutation below I would like the list {2,1,0,0,0,1,0,0,0,0} indicating that there are 2 fixed points, 1 cycle of length 2 and 1 cycle of length 6.

In[16]:= RandomPermutation[10]

Out[16]= Cycles[{{1, 4, 10, 7, 3, 5}, {2, 6}}]


If I understand correctly, you want a list, where the first element is the number of cycles with length 1, the second element the numbers of cycles with length 2 e.t.c.

Here is one way of doing it:

We first need some data:

n = 20;
perm = RandomPermutation[n];


Then we need to determine the lengths of the cycles:

cy = Length /@ perm[[1]];


Tally will count the cycles with a given length, whereby we need to consider the cycles with length 1:

cy = Tally[cy];
cy = AppendTo[cy, {1, n - Total[Times @@@ cy]}];


For the result we set up an array with zeros and then fill in the numbers of cycles at the corresponding positions:

res = ConstantArray[0, Length[perm]];
(res[[#[[1]]]] = #[[2]]) & /@ cy;
res

(* {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0} *)


You could write a function along these lines:

CycleCounts[elementCount_, perm : Cycles[cycles_List]] :=
With[
{fixedPts = List /@ Complement[Range@elementCount, Flatten@cycles]},
ReplacePart[
ConstantArray[0, elementCount],
CountsBy[Join[cycles, fixedPts], Length]]]


Then,

CycleCounts[10, Cycles[{{1, 4, 10, 7, 3, 5}, {2, 6}}]]
(*gives {2, 1, 0, 0, 0, 1, 0, 0, 0, 0}*)

sA = Normal @* SparseArray @* Map[{First @ #} -> Last @ # &] @*Tally @* Map[Length];

cycleLengths = PermutationCycles[#, sA] &;


Examples:

SeedRandom[1]

perm = RandomPermutation[10]

Cycles[{{1, 2, 5, 8, 9, 3}, {4, 10}}]

cycleLengths @ perm

{2, 1, 0, 0, 0, 1}

Grid[Prepend[{"π", "cycleLengths @ π"}] @
({#, cycleLengths @ #} & /@ RandomPermutation[10, 7]),
Dividers -> All]