login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A345461 Triangle T(n,k) (n >= 1, 0 <= k <= n-1) read by rows: number of distinct permutations after k steps of the "optimist" algorithm. 2
1, 2, 1, 6, 1, 1, 24, 6, 1, 1, 120, 38, 7, 1, 1, 720, 232, 53, 7, 1, 1, 5040, 1607, 404, 74, 7, 1, 1, 40320, 12984, 3383, 732, 108, 7, 1, 1, 362880, 117513, 31572, 7043, 1292, 167, 9, 1, 1, 3628800, 1182540, 324112, 75350, 14522, 2384, 260, 11, 1, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Start with the n! permutations of order n. Apply an iteration of the "optimist" sorting algorithm. Count the distinct permutations, until all are sorted.

The length of each row is n.

The optimist algorithm is: rotate right all currently unsorted letters by the distance between the first unsorted one and its sorted position. An example is given in A345453.

LINKS

Table of n, a(n) for n=1..55.

FORMULA

T(n,0) = n!; T(n,n-1) = 1; T(n,n-2) = 1 for n > 2.

EXAMPLE

Triangle begins:

.

     1;

     2,     1;

     6,     1,    1;

    24,     6,    1,   1;

   120,    38,    7,   1,  1;

   720,   232,   53,   7,  1,  1;

  5040,  1607,  404,  74,  7,  1,  1;

.

CROSSREFS

Cf. A345453 (permutations according to number of steps for sorting).

Cf. A321352 and A008305 (the equivalent for Eulerian numbers).

Cf. A345462 (the equivalent for Stirling numbers of 1st kind).

Cf. A345464 (first column).

Sequence in context: A139547 A323855 A126342 * A229818 A324500 A082388

Adjacent sequences:  A345458 A345459 A345460 * A345462 A345463 A345464

KEYWORD

tabl,nonn

AUTHOR

Olivier Gérard, Jun 20 2021

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 29 04:38 EST 2021. Contains 349416 sequences. (Running on oeis4.)