A339356 Maximum number of copies of a 123456 permutation pattern in an alternating (or zig-zag) permutation of length n + 9.

16, 32, 144, 256, 688, 1120, 2352, 3584, 6496, 9408, 15456, 21504, 32928, 44352, 64416, 84480, 117744, 151008, 203632, 256256, 336336, 416416, 534352, 652288, 821184, 990080, 1226176, 1462272, 1785408, 2108544, 2542656, 2976768, 3550416, 4124064, 4870992, 5617920, 6577648

Offset: 1

Author

Lara Pudwell, Dec 01 2020

Keywords

• nonn
• easy

Comments

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

Examples

			a(1) = 16. The alternating permutation of length 1+9=10 with the maximum number of copies of 123456 is 132547698(10). The sixteen copies are 12468(10), 12469(10), 12478(10), 12479(10), 12568(10), 12569(10), 12578(10), 12579(10), 13468(10), 13469(10), 13478(10), 13479(10), 13568(10), 13569(10), 13578(10), and 13579(10).
		

Links

• Lara Pudwell, From permutation patterns to the periodic table, Notices of the American Mathematical Society. 67.7 (2020), 994-1001.
• Index entries for linear recurrences with constant coefficients, signature (2,4,-10,-5,20,0,-20,5,10,-4,-2,1).

Crossrefs

Cf. A168380.

Formula

a(2n) = 32*A040977(n-1) = 64*C(n+5,6) - 32*C(n+4,5).

a(2n-1) = 16*A259181(n) = (2*n*(n + 1)*(n + 2)*(n + 3)*(2*n^2 + 6*n + 7))/45.

From Chai Wah Wu, Jul 06 2025: (Start)

a(n) = 2*a(n-1) + 4*a(n-2) - 10*a(n-3) - 5*a(n-4) + 20*a(n-5) - 20*a(n-7) + 5*a(n-8) + 10*a(n-9) - 4*a(n-10) - 2*a(n-11) + a(n-12) for n > 12.

G.f.: x*(-16*x^2 - 16)/((x - 1)^7*(x + 1)^5). (End)