A259784 Number T(n,k) of permutations p of [n] with no fixed points where the maximal displacement of an element equals k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 1, 3, 5, 0, 0, 0, 6, 18, 20, 0, 0, 1, 12, 44, 111, 97, 0, 0, 0, 24, 116, 396, 744, 574, 0, 0, 1, 44, 331, 1285, 3628, 5571, 3973, 0, 0, 0, 84, 932, 4312, 15038, 34948, 46662, 31520, 0, 0, 1, 159, 2532, 15437, 59963, 181193, 359724, 434127, 281825, 0

Offset

0,9

Links

Alois P. Heinz, Rows n = 0..20, flattened

Formula

T(n,k) = A259776(n,k) - A259776(n,k-1) for k>0, T(n,0) = A000007(n).

Example

Triangle T(n,k) begins:
  1;
  0, 0;
  0, 1,  0;
  0, 0,  2,   0;
  0, 1,  3,   5,    0;
  0, 0,  6,  18,   20,    0;
  0, 1, 12,  44,  111,   97,    0;
  0, 0, 24, 116,  396,  744,  574,    0;
  0, 1, 44, 331, 1285, 3628, 5571, 3973, 0;

Maple

b:= proc(n, s, k) option remember; `if`(n=0, 1, `if`(n+k in s,
      b(n-1, (s minus {n+k}) union `if`(n-k>1, {n-k-1}, {}), k),
      add(`if`(j=n, 0, b(n-1, (s minus {j}) union
      `if`(n-k>1, {n-k-1}, {}), k)), j=s)))
    end:
A:= (n, k)-> `if`(k=0, `if`(n=0, 1, 0), b(n, {$max(1, n-k)..n}, k)):
T:= (n, k)-> A(n, k) -`if`(k=0, 0, A(n, k-1)):
seq(seq(T(n, k), k=0..n), n=0..12);

Mathematica

b[n_, s_, k_] := b[n, s, k] = If[n==0, 1, If[MemberQ[s, n+k], b[n-1, (s ~Complement~ {n+k}) ~Union~ If[n-k>1, {n-k-1}, {}], k], Sum[If[j==n, 0, b[n-1, (s ~Complement~ {j}) ~Union~ If[n-k>1, {n-k-1}, {}], k]], {j, s}]] ];
A[n_, k_] := If[k == 0, If[n == 0, 1, 0], b[n, Range[Max[1, n-k], n], k]];
T[n_, k_] :=  A[n, k] - If[k == 0, 0, A[n, k-1]];
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, May 05 2019, after Alois P. Heinz *)

Crossrefs

Rows sums give A000166.

Column k=0 and main diagonal give A000007.

Columns k=1-10 give: A059841 (for n>0), A321048, A321049, A321050, A321051, A321052, A321053, A321054, A321055, A321056.

First lower diagonal gives A259834.

T(2n,n) gives A259785.

Cf. A259776.

Sequence in context: A375467 A373183 A351776 * A145224 A138157 A342243

Adjacent sequences: A259781 A259782 A259783 * A259785 A259786 A259787

Keyword

nonn,tabl

Author

Alois P. Heinz, Jul 05 2015

Status

approved