login
Number of permutations of [n] with at least two (possibly overlapping) occurrences of the consecutive step pattern {up}^2.
2

%I #18 Dec 22 2020 03:54:10

%S 0,0,0,0,1,9,97,983,10616,119932,1441405,18383351,249155667,

%T 3581896559,54540748818,877824410030,14904605652001,266431586957773,

%U 5004557444810885,98594548150006583,2033673324306909868,43845407809459639440,986496730691143433269

%N Number of permutations of [n] with at least two (possibly overlapping) occurrences of the consecutive step pattern {up}^2.

%H Alois P. Heinz, <a href="/A230620/b230620.txt">Table of n, a(n) for n = 0..200</a>

%F a(n) = Sum_{i=2..n-2} A162975(n,i).

%F a(n) ~ n!. - _Vaclav Kotesovec_, Sep 06 2014

%e a(4) = 1: 1234.

%e a(5) = 9: 12345, 12354, 12453, 13452, 21345, 23451, 31245, 41235, 51234.

%e a(6) = 97: 123456, 123465, 123546, ..., 631245, 641235, 651234.

%e a(7) = 983: 1234567, 1234576, 1234657, ..., 7631245, 7641235, 7651234.

%p b:= proc(u, o, t) option remember;

%p `if`(t=5, (u+o)!, `if`(u+o+t<4, 0,

%p add(b(u-j, o+j-1, [1, 1, 4, 4][t]), j=1..u)+

%p add(b(u+j-1, o-j, [2, 3, 5, 3][t]), j=1..o)))

%p end:

%p a:= n-> b(n, 0, 1):

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

%t b[u_, o_, t_] := b[u, o, t] =

%t If[t == 5, (u + o)!, If[u + o + t < 4, 0,

%t Sum[b[u - j, o + j - 1, {1, 1, 4, 4}[[t]]], {j, 1, u}] +

%t Sum[b[u + j - 1, o - j, {2, 3, 5, 3}[[t]]], {j, 1, o}]]];

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

%t a /@ Range[0, 25] (* _Jean-François Alcover_, Dec 22 2020, after _Alois P. Heinz_ *)

%Y Cf. A230621.

%K nonn

%O 0,6

%A _Alois P. Heinz_, Oct 25 2013