login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 10
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 (list; table; graph; refs; listen; history; text; internal format)
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.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 26 11:49 EST 2020. Contains 332279 sequences. (Running on oeis4.)