[seqfan] Number of permutations in S_n with complexity k

Neil Sloane njasloane at gmail.com
Fri Feb 8 00:52:02 CET 2019


I just came across a review in Math Sci Net from 1998 (MR1768839, the
authors are Miyata and Son) which defines the complexity of a permutation
pi as follows.
Represent pi as a product of cycles in the standard way.

E.g.  pi = (1,2,4,5)(3,7)(6)

The complexity of pi is 0 if pi = identity,
otherwise it is Sum(  (length of cycle) -1 )

So in the above example it would be 3+1+0 = 4

What is the triangle T(n,k) = number of permutations of n letters with
complexity k ?

It is probably in the OEIS already, but I did not
find it under that name



More information about the SeqFan mailing list