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,4

Links

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

Formula

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

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

Example

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

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 *)

Crossrefs

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

Cf. A004767, A097592.

Sequence in context: A189744 A241279 A245696 * A123304 A270129 A271293

Adjacent sequences: A317136 A317137 A317138 * A317140 A317141 A317142

Keyword

nonn

Author

Alois P. Heinz, Jul 22 2018

Status

approved