login
This site is supported by donations to The OEIS Foundation.

 

Logo


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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 22 14:45 EDT 2019. Contains 325223 sequences. (Running on oeis4.)