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

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A345462 Triangle T(n,k) (n >= 1, 0 <= k <= n-1) read by rows: number of distinct permutations after k steps of the "first transposition" algorithm. 2
 1, 2, 1, 6, 3, 1, 24, 13, 4, 1, 120, 67, 23, 5, 1, 720, 411, 146, 36, 6, 1, 5040, 2921, 1067, 272, 52, 7, 1, 40320, 23633, 8800, 2311, 456, 71, 8, 1, 362880, 214551, 81055, 21723, 4419, 709, 93, 9, 1, 3628800, 2160343, 825382, 224650, 46654, 7720, 1042, 118, 10, 1 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS The first transposition algorithm is: if the permutation is sorted, then exit; otherwise, exchange the first unsorted letter with the letter currently at its index. Repeat. At each step at least 1 letter (possibly 2) is sorted. If one counts the steps necessary to reach the identity, this gives the Stirling numbers of the first kind (reversed). REFERENCES D. E. Knuth, The Art of Computer Programming, Vol. 3 / Sorting and Searching, Addison-Wesley, 1973. LINKS Alois P. Heinz, Rows n = 1..150, flattened FORMULA T(n,0) = n!; T(n,n-3) = (3*(n-1)^2 - n + 3)/2. From Alois P. Heinz, Aug 11 2021: (Start) T(n,k) = T(n,k-1) - A010027(n,n-k) for k >= 1. T(n,k) - T(n,k+1) = A123513(n,k). T(n,0) - T(n,1) = A000255(n-1) for n >= 2. T(n,1) - T(n,2) = A000166(n) for n >= 3. T(n,2) - T(n,3) = A000274(n) for n >= 4. T(n,3) - T(n,4) = A000313(n) for n >= 5. (End) EXAMPLE Triangle begins:       1;       2,     1;       6,     3,    1;      24,    13,    4,    1;     120,    67,   23,    5,   1;     720,   411,  146,   36,   6,  1;    5040,  2921, 1067,  272,  52,  7, 1;   40320, 23633, 8800, 2311, 456, 71, 8, 1;   ... MAPLE b:= proc(n, k) option remember; (k+1)!*       binomial(n, k)*add((-1)^i/i!, i=0..k+1)/n     end: T:= proc(n, k) option remember;      `if`(k=0, n!, T(n, k-1)-b(n, n-k+1))     end: seq(seq(T(n, k), k=0..n-1), n=1..10);  # Alois P. Heinz, Aug 11 2021 CROSSREFS Cf. A321352, A345461 (same idea for other sorting algorithms). Cf. A180191 (second column, k=1). Cf. A107111 a triangle with some common parts. Cf. A143689 (diagonal T(n,n-3)). Cf. A000142, A000166, A000255, A000274, A000313, A010027, A123513. Sequence in context: A173333 A221915 A249619 * A222159 A221623 A096334 Adjacent sequences:  A345459 A345460 A345461 * A345463 A345464 A345465 KEYWORD nonn,tabl 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.

Last modified December 1 16:44 EST 2021. Contains 349430 sequences. (Running on oeis4.)