|
%I #23 Nov 29 2018 04:11:43
%S 1,2,3,8,6,9,26,36,27,30,146,126,177,120,150,746,966,777,960,750,840,
%T 5786,5166,6657,5160,6630,5040,5880,41066,50526,41937,50520,41910,
%U 50400,41160,45360,403946,368046,450177,368040,450150,367920,449400,362880,408240,3669866,4359726,3716097,4359720,3716070,4359600,3715320,4354560,3674160,3991680
%N 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.
%D 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.
%H Hugo Pfoertner, <a href="/A321668/b321668.txt">Table of n, a(n) for n = 1..91</a>, rows 1..13, flattened.
%e The triangle starts:
%e 1
%e 2 3
%e 8 6 9
%e 26 36 27 30
%e 146 126 177 120 150
%e 746 966 777 960 750 840
%e 5786 5166 6657 5160 6630 5040 5880
%e 41066 50526 41937 50520 41910 50400 41160 45360
%e 403946 368046 450177 368040 450150 367920 449400 362880 408240
%e 3669866 4359726 3716097 4359720 3716070 4359600 3715320 4354560 3674160 3991680
%e .
%e 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
%e 123
%e t(1) = 2: 12\3 -> 132
%e t(2) = 1: 1\32 -> 312
%e t(3) = 2: 31\2 -> 321
%e t(4) = 1: 3\21 -> 231
%e t(5) = 2: 23\1 -> 213
%e .
%e 1 occurs 2 times in t, 2 occurs 3 times. Therefore T(2,1) = 2, T(2,2) = 3.
%e .
%e 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.
%p # Algorithm T due to Don Knuth.
%p Knuth_T := proc(n)
%p local N,d,t,m,k,j,often;
%p # T1 [Initialize]
%p often := [seq(0,j=1..n-1)];
%p N := n!; d := N/2; t[d] := 1; m := 2;
%p # T2 [Loop on m]
%p while m <> n do
%p m := m+1; d := d/m; k := 0;
%p # T3 [Hunt down]
%p while true do
%p k := k+d; j := m-1;
%p while j > 0 do
%p t[k] := j; j := j-1; k := k+d; od;
%p # T4 [Offset]
%p t[k] := t[k]+1; k := k+d;
%p # T5 [Hunt up]
%p while j < m-1 do
%p j := j+1; t[k] := j; k := k+d;
%p od;
%p if k >= N then break; fi; od;
%p if j = 0 then break; fi; od;
%p for j to n-1 do
%p often[j] := 0; od;
%p for k to N-1 do
%p often[t[k]] := often[t[k]]+1; od;
%p return often;
%p end:
%p for n from 2 to 9 do Knuth_T(n); od; # _Rainer Rosenthal_, Nov 26 2018
%Y Cf. A033312.
%K nonn,tabl
%O 1,2
%A _Hugo Pfoertner_, Nov 16 2018
|
