A303160 Number of permutations p of [n] such that 0p has exactly ceiling(n/2) alternating runs.

1, 1, 1, 3, 7, 43, 148, 1344, 6171, 74211, 425976, 6384708, 43979902, 789649750, 6346283560, 132789007200, 1219725741715, 29145283614115, 301190499710320, 8092186932120060, 92921064554444490, 2772830282722806978, 35025128774218944648, 1149343084932146388144

Offset

0,4

Links

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

Formula

a(n) = A186370(n,ceiling(n/2)).

Example

a(2) = 1: 12.
a(3) = 3: 132, 231, 321.
a(4) = 7: 1243, 1342, 1432, 2341, 2431, 3421, 4321.

Maple

b:= proc(n, k) option remember; `if`(k=0,
      `if`(n=0, 1, 0), `if`(k<0 or k>n, 0,
       k*b(n-1, k)+b(n-1, k-1)+(n-k+1)*b(n-1, k-2)))
    end:
a:= n-> b(n, ceil(n/2)):
seq(a(n), n=0..25);

Mathematica

b[n_, k_] := b[n, k] = If[k == 0,
     If[n == 0, 1, 0], If[k < 0 || k > n, 0,
     k*b[n-1, k] + b[n-1, k-1] + (n-k+1)*b[n-1, k-2]]];
a[n_] := b[n, Ceiling[n/2]];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Aug 31 2021, after Alois P. Heinz *)

Crossrefs

Bisections give: A291677 (even part), A303159 (odd part).

Cf. A186370.

Sequence in context: A101208 A050633 A107636 * A258435 A074268 A019026

Adjacent sequences: A303157 A303158 A303159 * A303161 A303162 A303163

Keyword

nonn

Author

Alois P. Heinz, Apr 19 2018

Status

approved