A356853 Number of permutations p of [2n+1] such that at most one element of {p(1),...,p(i-1)} is between p(i) and p(i+1) for all i <= 2n and p(2n+1) = n+1.

1, 2, 20, 216, 2720, 36228, 503216, 7171404, 104142520, 1533200656, 22811374568, 342216338652, 5168324302672, 78483423004680, 1197266739443160, 18335055482658748, 281714880491273736, 4340894020114398672, 67055152953864109240, 1038097819961270208088

Offset

0,2

Links

Alois P. Heinz, Table of n, a(n) for n = 0..832

Formula

a(n) = A356692(2n,n).

Example

a(0) = 1: 1.
a(1) = 2: 132, 312.
a(2) = 20: 12453, 12543, 14253, 14523, 15243, 15423, 21453, 21543, 25143, 25413, 41253, 41523, 45123, 45213, 51243, 51423, 52143, 52413, 54123, 54213.
a(3) = 216: 1235764, 1236754, 1237564, 1237654, ..., 7651234, 7651324, 7652134, 7653124.

Maple

b:= proc(u, o) option remember; `if`(u+o=0, 1,
      add(b(sort([o-j, u+j-1])[]), j=1..min(2, o))+
      add(b(sort([u-j, o+j-1])[]), j=1..min(2, u)))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..20);
# second Maple program:
b:= proc(n, k) option remember; `if`(k<0 or k>n, 0,
      `if`(n=0, 1, add(b(n-1, j), j=k-2..k+1)))
    end:
a:= n-> b(2*n, n):
seq(a(n), n=0..20);

Crossrefs

Cf. A356692.

Sequence in context: A226301 A000906 A308945 * A199761 A214769 A227337

Adjacent sequences: A356850 A356851 A356852 * A356854 A356855 A356856

Keyword

nonn

Author

Alois P. Heinz, Aug 31 2022

Status

approved