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

%I #20 Aug 31 2021 08:02:29

%S 1,1,1,4,5,43,61,906,1385,31493,50521,1629248,2702765,117248463,

%T 199360981,11190963430,19391512145,1367267690953,2404879675441,

%U 208031951035452,370371188237525,38563334673062963,69348874393137901,8554779137299629314,15514534163557086905

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

%H Alois P. Heinz, <a href="/A317139/b317139.txt">Table of n, a(n) for n = 0..484</a>

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

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

%e a(3) = 4: 132, 213, 231, 312.

%e a(4) = 5: 1324, 1423, 2314, 2413, 3412.

%p b:= proc(u, o, t, c) option remember; `if`(u+o=0, 1,`if`(t=1,

%p add(b(u+j-1, o-j, t+1, c), j=1..o), 0)+`if`(t<>1 or t=1 and c=1,

%p add(b(u-j, o+j-1, 1, `if`(t=1 and c=1, 0, c)), j=1..u), 0))

%p end:

%p a:= n-> b(n, 0$2, irem(n, 2)):

%p seq(a(n), n=0..30);

%t b[u_, o_, t_, c_] := b[u, o, t, c] = If[u + o == 0, 1, If[t == 1,

%t Sum[b[u+j-1, o-j, t+1, c], {j, o}], 0] + If[t != 1 || t == 1 && c == 1,

%t Sum[b[u-j, o+j-1, 1, If[t == 1 && c == 1, 0, c]], {j, u}], 0]];

%t a[n_] := b[n, 0, 0, Mod[n, 2]];

%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Aug 31 2021, after _Alois P. Heinz_ *)

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

%Y Cf. A004767, A097592.

%K nonn

%O 0,4

%A _Alois P. Heinz_, Jul 22 2018