A147679 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, 1, 1, 0, 3, 3, 4, 8, 4, 8, 20, 25, 25, 25, 25, 144, 108, 108, 144, 108, 108, 630, 735, 735, 735, 735, 735, 735, 5696, 4608, 5248, 4608, 5696, 4608, 5248, 4608, 39366, 40824, 40824, 39285, 40824, 40824, 39285, 40824, 40824, 366400, 362000, 362000, 362000, 362000, 366400, 362000, 362000, 362000, 362000

Offset: 1

Author

N. J. A. Sloane, May 01 2009

Keywords

• nonn
• tabl

Comments

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

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)].

Examples

			Triangle begins:
    1
    1   1
    0   3   3
    4   8   4   8
   20  25  25  25  25
  144 108 108 144 108 108
  ...
		

Links

• Seiichi Manyama, Rows n = 1..13, flattened
• R. L. Graham and D. H. Lehmer, On the Permanent of Schur's Matrix, J. Australian Math. Soc., 21A (1976), 487-497.

Crossrefs

Cf. A003112.

Row sums give: A000142.

Columns k=0-3 give: A004204, A004205, A004206, A004246.

Diagonal gives: A004205.

Programs

Maple

b:= proc(n) option remember;
     local l, p, r;
     l:= array([i$i=0..n-1]);
     r:= array([0$i=1..n]);
     p:= proc(t,s)
      local d, h, j;
      if t=n then d:= ((s+(n-1)*l[n]) mod n) +1;
                  r[d]:= r[d]+1
      else for j from t to n do
            l[t],l[j]:= l[j],l[t];
            p(t+1, (s+(t-1)*l[t]) )
           od;
           h:= l[t];
           for j from t to n-1 do l[j]:= l[j+1] od;
           l[n]:= h
      fi
     end;
     p(1,0);
     eval(r)
    end:
T:= (n,k)-> b(n)[k+1]:
seq (seq (T(n,k), k=0..n-1), n=1..10);

Mathematica

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 *)

Sage

@CachedFunction
def A147679_row(n):
    row = [0]*n
    for p in Permutations(range(n)):
        spread = sum(i*px for i,px in enumerate(p)) % n
        row[spread] += 1
    return row
A147679 = lambda n,k: A147679_row(n)[k] # D. S. McNeil, Dec 23 2010

Extensions

Edited by Alois P. Heinz, Dec 22 2010