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
Examples
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, ...
Links
- Joerg Arndt and Alois P. Heinz, Antidiagonals n = 0..48, flattened
Crossrefs
Programs
-
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 *)
Formula
T(n,k) = Sum_{i=0..k} A238889(n,i).
Comments