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

8, 16, 64, 112, 272, 432, 832, 1232, 2072, 2912, 4480, 6048, 8736, 11424, 15744, 20064, 26664, 33264, 42944, 52624, 66352, 80080, 99008, 117936, 143416, 168896, 202496, 236096, 279616, 323136, 378624, 434112, 503880, 573648, 660288, 746928, 853328, 959728, 1089088, 1218448

Offset

1,1

Comments

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

Links

Georg Fischer, Table of n, a(n) for n = 1..200

Lara Pudwell, From permutation patterns to the periodic table, Notices of the American Mathematical Society. 67.7 (2020), 994-1001.

Formula

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

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

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

Example

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.

Maple

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

Crossrefs

Cf. A005585, A033455, A168380.

Sequence in context: A307876 A166638 A356961 * A132794 A082982 A218899

Adjacent sequences: A339352 A339353 A339354 * A339356 A339357 A339358

Keyword

nonn

Author

Lara Pudwell, Dec 01 2020

Status

approved