[seqfan] Re: Number of permutations in S_n with complexity k

[Olivier Gerard]

Dear Neil,

This triangle is already in the OEIS because this is just the unsigned
Stirling numbers of the first kind in reverse horizontal order.

A094638

This is easy to see as you subtract the number of cycles to the size of the
permutation.

This measure of "complexity" is equivalent to the number of cycles.

Olivier



On Fri, Feb 8, 2019 at 2:52 AM Neil Sloane <njasloane at gmail.com> wrote:

> 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
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>