This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A321668 Number of occurrences of k in the list of transitions t(j), j <= n!-1, of interchanges a(t(j)) <-> a(t(j)+1) created by Knuth's "Algorithm T" (Plain change transitions) to generate all permutations of n distinct elements, written as a triangle T(m,k), m = n-1 >= 1, k <= m. 1
 1, 2, 3, 8, 6, 9, 26, 36, 27, 30, 146, 126, 177, 120, 150, 746, 966, 777, 960, 750, 840, 5786, 5166, 6657, 5160, 6630, 5040, 5880, 41066, 50526, 41937, 50520, 41910, 50400, 41160, 45360, 403946, 368046, 450177, 368040, 450150, 367920, 449400, 362880, 408240, 3669866, 4359726, 3716097, 4359720, 3716070, 4359600, 3715320, 4354560, 3674160, 3991680 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 REFERENCES Donald E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 2, Generating All Tuples and Permutations, chapter 7.2.1.2. pages 43-44, Addison-Wesley Professional, 2005. LINKS Hugo Pfoertner, Table of n, a(n) for n = 1..91, rows 1..13, flattened. EXAMPLE The triangle starts:         1         2       3         8       6       9        26      36      27      30       146     126     177     120     150       746     966     777     960     750     840      5786    5166    6657    5160    6630    5040    5880     41066   50526   41937   50520   41910   50400   41160   45360    403946  368046  450177  368040  450150  367920  449400  362880  408240   3669866 4359726 3716097 4359720 3716070 4359600 3715320 4354560 3674160 3991680 . For n=3 (m=2), Algorithm T produces the transitions list t = (t(1),...,t(5)) = (2, 1, 2, 1, 2). With a\b indicating interchange of xy -> yx, the 6 permutations of 1 2 3 are created in the order                     123   t(1) = 2: 12\3 -> 132   t(2) = 1: 1\32 -> 312   t(3) = 2: 31\2 -> 321   t(4) = 1: 3\21 -> 231   t(5) = 2: 23\1 -> 213 . 1 occurs 2 times in t, 2 occurs 3 times. Therefore T(2,1) = 2, T(2,2) = 3. . For n=4 (m=3), t = (t(1),...,t(23)) = (3, 2, 1, 3, 1, 2, 3, 1, 3, 2, 1, 3, 1, 2, 3, 1, 3, 2, 1, 3, 1, 2, 3). 1 occurs 8 times, 2 occurs 6 times and 3 occurs 9 times. Therefore T(3,1) = 8, T(3,2) = 6, T(3,3) = 9. MAPLE # Algorithm T due to Don Knuth. Knuth_T := proc(n)    local N, d, t, m, k, j, often;    # T1 [Initialize]    often := [seq(0, j=1..n-1)];    N := n!; d := N/2; t[d] := 1; m := 2;    # T2 [Loop on m]    while m <> n do       m := m+1; d := d/m; k := 0;       # T3 [Hunt down]       while true do          k := k+d; j := m-1;          while j > 0 do             t[k] := j; j := j-1; k := k+d; od;          # T4 [Offset]          t[k] := t[k]+1; k := k+d;          # T5 [Hunt up]          while j < m-1 do             j := j+1; t[k] := j; k := k+d;          od;          if k >= N then break; fi; od;       if j = 0 then break; fi; od;    for j to n-1 do       often[j] := 0; od;    for k to N-1 do       often[t[k]] := often[t[k]]+1; od;    return often; end: for n from 2 to 9 do Knuth_T(n); od; # Rainer Rosenthal, Nov 26 2018 CROSSREFS Cf. A033312. Sequence in context: A093098 A021423 A160582 * A112977 A120390 A109230 Adjacent sequences:  A321665 A321666 A321667 * A321669 A321670 A321671 KEYWORD nonn,tabl AUTHOR Hugo Pfoertner, Nov 16 2018 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 July 22 14:45 EDT 2019. Contains 325223 sequences. (Running on oeis4.)