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

[Neil Sloane]

Thanks Alois and Olivier  for those very helpful replies. I have added
comments about the complexity of permutations to both A008275 and A094638.

Just to clarify things, the number of perms of 1..n with complexity k =
number of perms with n-k cycles,
for k=0..n-1.

For n=5, the number of perms of 1..n with complexity k  for k=0..4 are
1,10,35,50,24.
The 10 of complexity 1 are the transpositions of form (12)(3)(4)(5) with 4
cycles.

Best regards
Neil

Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com



On Thu, Feb 7, 2019 at 8:47 PM Olivier Gerard <olivier.gerard at gmail.com>
wrote:

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