A317139 Number of permutations of [n] with exactly floor(n/2) increasing runs of length two.

1, 1, 1, 4, 5, 43, 61, 906, 1385, 31493, 50521, 1629248, 2702765, 117248463, 199360981, 11190963430, 19391512145, 1367267690953, 2404879675441, 208031951035452, 370371188237525, 38563334673062963, 69348874393137901, 8554779137299629314, 15514534163557086905

Offset: 0

Author

Alois P. Heinz, Jul 22 2018

Keywords

• nonn

Examples

			a(3) = 4: 132, 213, 231, 312.
a(4) = 5: 1324, 1423, 2314, 2413, 3412.
		

Links

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

Crossrefs

Bisections give: A000364 (even part), A317140 (odd part).

Cf. A004767, A097592.

Programs

Maple

b:= proc(u, o, t, c) option remember; `if`(u+o=0, 1,`if`(t=1,
       add(b(u+j-1, o-j, t+1, c), j=1..o), 0)+`if`(t<>1 or t=1 and c=1,
       add(b(u-j, o+j-1, 1, `if`(t=1 and c=1, 0, c)), j=1..u), 0))
    end:
a:= n-> b(n, 0$2, irem(n, 2)):
seq(a(n), n=0..30);

Mathematica

b[u_, o_, t_, c_] := b[u, o, t, c] = If[u + o == 0, 1, If[t == 1,
    Sum[b[u+j-1, o-j, t+1, c], {j, o}], 0] + If[t != 1 || t == 1 && c == 1,
    Sum[b[u-j, o+j-1, 1, If[t == 1 && c == 1, 0, c]], {j, u}], 0]];
a[n_] := b[n, 0, 0, Mod[n, 2]];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Aug 31 2021, after Alois P. Heinz *)

Formula

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

a(n) is even <=> n == 3 (mod 4).