A238888 Number A(n,k) of self-inverse permutations p on [n] with displacement of elements restricted by k: |p(i)-i| <= k, square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 1, 2, 4, 5, 1, 1, 1, 2, 4, 8, 8, 1, 1, 1, 2, 4, 10, 15, 13, 1, 1, 1, 2, 4, 10, 22, 29, 21, 1, 1, 1, 2, 4, 10, 26, 48, 56, 34, 1, 1, 1, 2, 4, 10, 26, 66, 103, 108, 55, 1, 1, 1, 2, 4, 10, 26, 76, 158, 225, 208, 89, 1, 1, 1, 2, 4, 10, 26, 76, 206, 376, 492, 401, 144, 1

Offset

0,9

Comments

A(n,k) is exactly the number of matchings of the k-th power of the path on n vertices. Here is A(4,1): o o o o (1234); o o o--o (1243); o o--o o (1324); o--o o o (2134); o--o o--o (2143). - Pietro Codara, Feb 17 2015

Links

Joerg Arndt and Alois P. Heinz, Antidiagonals n = 0..48, flattened

Formula

T(n,k) = Sum_{i=0..k} A238889(n,i).

Example

A(4,0) = 1: 1234.
A(4,1) = 5: 1234, 1243, 1324, 2134, 2143.
A(4,2) = 8: 1234, 1243, 1324, 1432, 2134, 2143, 3214, 3412.
A(4,3) = 10: 1234, 1243, 1324, 1432, 2134, 2143, 3214, 3412, 4231, 4321.
Square array A(n,k) begins:
  1,  1,   1,   1,   1,   1,   1,   1,   1, ...
  1,  1,   1,   1,   1,   1,   1,   1,   1, ...
  1,  2,   2,   2,   2,   2,   2,   2,   2, ...
  1,  3,   4,   4,   4,   4,   4,   4,   4, ...
  1,  5,   8,  10,  10,  10,  10,  10,  10, ...
  1,  8,  15,  22,  26,  26,  26,  26,  26, ...
  1, 13,  29,  48,  66,  76,  76,  76,  76, ...
  1, 21,  56, 103, 158, 206, 232, 232, 232, ...
  1, 34, 108, 225, 376, 546, 688, 764, 764, ...

Maple

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

Mathematica

b[n_, k_, s_] := b[n, k, s] = If[n == 0, 1, If[MemberQ[s, n], b[n-1, k, DeleteCases[s, n]], b[n-1, k, s] + Sum[If[MemberQ[s, i], 0, b[n-1, k, s ~Union~ {i}]], {i, Max[1, n-k], n-1}]]]; A[n_, k_] := If[k>n, A[n, n], b[n, k, {}]]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Mar 12 2014, translated from Maple *)

Crossrefs

Columns k=0-10 give: A000012, A000045(n+1), A000078(n+3), A239075, A239076, A239077, A239078, A239079, A239080, A239081, A239082.

Main diagonal gives A000085.

Sequence in context: A119338 A054124 A144406 * A179748 A096670 A130461

Adjacent sequences: A238885 A238886 A238887 * A238889 A238890 A238891

Keyword

nonn,tabl

Author

Joerg Arndt and Alois P. Heinz, Mar 06 2014

Status

approved