login
Maximum number of copies of a 12345 permutation pattern in an alternating (or zig-zag) permutation of length n + 7.
1

%I #10 Nov 25 2022 10:11:34

%S 8,16,64,112,272,432,832,1232,2072,2912,4480,6048,8736,11424,15744,

%T 20064,26664,33264,42944,52624,66352,80080,99008,117936,143416,168896,

%U 202496,236096,279616,323136,378624,434112,503880,573648,660288,746928,853328,959728,1089088,1218448

%N Maximum number of copies of a 12345 permutation pattern in an alternating (or zig-zag) permutation of length n + 7.

%C The maximum number of copies of 123 in an alternating permutation is motivated in the Notices reference, and the argument here is analogous.

%H Georg Fischer, <a href="/A339355/b339355.txt">Table of n, a(n) for n = 1..200</a>

%H Lara Pudwell, <a href="https://www.ams.org/journals/notices/202007/rnoti-p994.pdf">From permutation patterns to the periodic table</a>, Notices of the American Mathematical Society. 67.7 (2020), 994-1001.

%F a(2*n) = 16*A005585(n) = 32*binomial(n+4, 5) - 16*binomial(n+3, 4).

%F a(2*n-1) = 8*A033455(n) = (4*n*(n^4 + 5*n^3 + 10*n^2 + 10*n + 4))/15.

%F D-finite with recurrence: (n-1)*((n-3)^2+9*n-6)*a(n) - (2*(n-3)^2+20*n-16)*a(n-1) - (n+5)*((n-3)^2+11*n-2)*a(n-2) = 0. - _Georg Fischer_, Nov 25 2022

%e a(1) = 8. The alternating permutation of length 1 + 7 = 8 with the maximum number of copies of 12345 is 13254768. The eight copies are 12468, 12478, 12568, 12578, 13468, 13478, 13568, and 13578.

%p a := proc(n2) local n; n:= floor(n2/2): if n2 = 2*n then 32*binomial(n+4,5) - 16*binomial(n+3,4) else n:=n+1; (4*n*(n^4+5*n^3+10*n^2+10*n+4))/15 fi end; seq(a(n), n=1..20); # _Georg Fischer_, Nov 25 2022

%Y Cf. A005585, A033455, A168380.

%K nonn

%O 1,1

%A _Lara Pudwell_, Dec 01 2020