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

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

Links

Table of n, a(n) for n=1..55.

R. L. Graham and D. H. Lehmer, On the Permanent of Schur's Matrix, J. Australian Math. Soc., 21A (1976), 487-497.

Example

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

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

Prog

(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

Crossrefs

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

Sequence in context: A266616 A360846 A340429 * A339054 A137417 A137418

Adjacent sequences: A147676 A147677 A147678 * A147680 A147681 A147682

Keyword

nonn,tabl

Author

N. J. A. Sloane, May 01 2009

Extensions

Edited by Alois P. Heinz, Dec 22 2010

Status

approved