login
Triangle read by rows: T(n,k) (n >= 1, 0 <= k <= n-1) is the number of permutations of [0..(n-1)] of spread k.
1

%I #35 Oct 17 2022 01:45:40

%S 1,1,1,0,3,3,4,8,4,8,20,25,25,25,25,144,108,108,144,108,108,630,735,

%T 735,735,735,735,735,5696,4608,5248,4608,5696,4608,5248,4608,39366,

%U 40824,40824,39285,40824,40824,39285,40824,40824,366400,362000,362000,362000,362000,366400,362000,362000,362000,362000

%N Triangle read by rows: T(n,k) (n >= 1, 0 <= k <= n-1) is the number of permutations of [0..(n-1)] of spread k.

%C The reference gives more terms, formulas, connection with A003112, etc.

%C s(pi):= Sum_{j=0..n-1} j*pi(j) (mod j) is defined to be the spread of a permutation pi of [0..(n-1)].

%H R. L. Graham and D. H. Lehmer, <a href="https://doi.org/10.1017/S1446788700019339">On the Permanent of Schur's Matrix</a>, J. Australian Math. Soc., 21A (1976), 487-497.

%e Triangle begins:

%e 1

%e 1 1

%e 0 3 3

%e 4 8 4 8

%e 20 25 25 25 25

%e 144 108 108 144 108 108

%e ...

%p b:= proc(n) option remember;

%p local l, p, r;

%p l:= array([i$i=0..n-1]);

%p r:= array([0$i=1..n]);

%p p:= proc(t,s)

%p local d, h, j;

%p if t=n then d:= ((s+(n-1)*l[n]) mod n) +1;

%p r[d]:= r[d]+1

%p else for j from t to n do

%p l[t],l[j]:= l[j],l[t];

%p p(t+1, (s+(t-1)*l[t]) )

%p od;

%p h:= l[t];

%p for j from t to n-1 do l[j]:= l[j+1] od;

%p l[n]:= h

%p fi

%p end;

%p p(1,0);

%p eval(r)

%p end:

%p T:= (n,k)-> b(n)[k+1]:

%p seq (seq (T(n,k), k=0..n-1), n=1..10);

%t b[n_] := b[n] = Module[{l, p, r}, l = Range[0, n-1]; r = Array[0&, n]; p [t_, s_] := Module[{d, h, j}, If[t == n, d = Mod[s+(n-1)*l[[n]], n]+1; r[[d]] = r[[d]]+1, For[j = t, j <= n, j++, {l[[t]], l[[j]]} = {l[[j]], l[[t]]}; p[t+1, s+(t-1)*l[[t]]]]; h = l[[t]]; For[j = t, j <= n-1, j++, l[[j]] = l[[j+1]]]; l[[n]] = h]]; p[1, 0]; r]; t[n_, k_] := b[n][[k+1]]; Table [Print[t[n, k]]; t[n, k], {n, 1, 10}, {k, 0, n-1}] // Flatten (* _Jean-François Alcover_, Apr 17 2014, after _Alois P. Heinz_ *)

%o (Sage)

%o @CachedFunction

%o def A147679_row(n):

%o row = [0]*n

%o for p in Permutations(range(n)):

%o spread = sum(i*px for i,px in enumerate(p)) % n

%o row[spread] += 1

%o return row

%o A147679 = lambda n,k: A147679_row(n)[k] # _D. S. McNeil_, Dec 23 2010

%Y Cf. A003112. Row sums give: A000142. Columns k=0-3 give: A004204, A004205, A004206, A004246. Diagonal gives: A004205.

%K nonn,tabl

%O 1,5

%A _N. J. A. Sloane_, May 01 2009

%E Edited by _Alois P. Heinz_, Dec 22 2010