cp's OEIS Frontend

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.

%I A238888 #31 Mar 05 2024 17:20:59
%S A238888 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,
%T A238888 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,
%U A238888 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
%N 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.
%C A238888 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
%H A238888 Joerg Arndt and Alois P. Heinz, <a href="/A238888/b238888.txt">Antidiagonals n = 0..48, flattened</a>
%F A238888 T(n,k) = Sum_{i=0..k} A238889(n,i).
%e A238888 A(4,0) = 1: 1234.
%e A238888 A(4,1) = 5: 1234, 1243, 1324, 2134, 2143.
%e A238888 A(4,2) = 8: 1234, 1243, 1324, 1432, 2134, 2143, 3214, 3412.
%e A238888 A(4,3) = 10: 1234, 1243, 1324, 1432, 2134, 2143, 3214, 3412, 4231, 4321.
%e A238888 Square array A(n,k) begins:
%e A238888   1,  1,   1,   1,   1,   1,   1,   1,   1, ...
%e A238888   1,  1,   1,   1,   1,   1,   1,   1,   1, ...
%e A238888   1,  2,   2,   2,   2,   2,   2,   2,   2, ...
%e A238888   1,  3,   4,   4,   4,   4,   4,   4,   4, ...
%e A238888   1,  5,   8,  10,  10,  10,  10,  10,  10, ...
%e A238888   1,  8,  15,  22,  26,  26,  26,  26,  26, ...
%e A238888   1, 13,  29,  48,  66,  76,  76,  76,  76, ...
%e A238888   1, 21,  56, 103, 158, 206, 232, 232, 232, ...
%e A238888   1, 34, 108, 225, 376, 546, 688, 764, 764, ...
%p A238888 b:= proc(n, k, s) option remember; `if`(n=0, 1, `if`(n in s,
%p A238888       b(n-1, k, s minus {n}), b(n-1, k, s) +add(`if`(i in s, 0,
%p A238888       b(n-1, k, s union {i})), i=max(1, n-k)..n-1)))
%p A238888     end:
%p A238888 A:= (n, k)-> `if`(k>n, A(n, n), b(n, k, {})):
%p A238888 seq(seq(A(n, d-n), n=0..d), d=0..12);
%t A238888 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 *)
%Y A238888 Columns k=0-10 give: A000012, A000045(n+1), A000078(n+3), A239075, A239076, A239077, A239078, A239079, A239080, A239081, A239082.
%Y A238888 Main diagonal gives A000085.
%K A238888 nonn,tabl
%O A238888 0,9
%A A238888 _Joerg Arndt_ and _Alois P. Heinz_, Mar 06 2014