A322294 Number of permutations of [n] with exactly floor(n/2) rising or falling successions.

1, 1, 2, 4, 10, 48, 120, 888, 2198, 22120, 54304, 685368, 1674468, 25344480, 61736880, 1087931184, 2644978110, 53138966904, 129019925424, 2909014993080, 7056278570108, 176372774697856, 427516982398576, 11729862804913680, 28417031969575260, 848948339328178128

Offset

0,3

Links

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

Formula

a(n) = A001100(n,floor(n/2)).

Maple

S:= proc(n) option remember; `if`(n<4, [1, 1, 2*t, 4*t+2*t^2]
       [n+1], expand((n+1-t)*S(n-1) -(1-t)*(n-2+3*t)*S(n-2)
       -(1-t)^2*(n-5+t)*S(n-3) +(1-t)^3*(n-3)*S(n-4)))
    end:
a:= n-> coeff(S(n), t, floor(n/2)):
seq(a(n), n=0..30);

Mathematica

s[n_] := s[n] = If[n < 4, {1, 1, 2*t, 4*t + 2*t^2}[[n + 1]], Expand[(n + 1 - t)*s[n - 1] - (1 - t)*(n - 2 + 3*t)*s[n - 2] - (1 - t)^2*(n - 5 + t)*s[n - 3] + (1 - t)^3*(n - 3)*s[n - 4]]];
t[n_, k_] := Ceiling[Coefficient[s[n], t, k]];
a[n_] := t[n, Floor[n/2]];
a /@ Range[0, 30] (* Jean-François Alcover, Sep 25 2019, after Alois P. Heinz *)

Crossrefs

Bisections give A322295 (even part), A322295 (odd part).

Cf. A001100.

Sequence in context: A113208 A173488 A000613 * A053500 A214724 A326325

Adjacent sequences: A322291 A322292 A322293 * A322295 A322296 A322297

Keyword

nonn

Author

Alois P. Heinz, Dec 02 2018

Status

approved