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, 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

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