A339358 Maximum number of copies of a 1234567 permutation pattern in an alternating (or zig-zag) permutation of length n + 11.

32, 64, 320, 576, 1696, 2816, 6400, 9984, 19392, 28800, 50304, 71808, 116160, 160512, 244992, 329472, 480480, 631488, 887744, 1144000, 1560416, 1976832, 2629120, 3281408, 4271488, 5261568, 6723840, 8186112, 10294656, 12403200, 15379968, 18356736, 22480800, 26604864

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

Andrew Howroyd, Table of n, a(n) for n = 1..1000

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,5,-12,-9,30,5,-40,5,30,-9,-12,5,2,-1).

Formula

a(2n) = 64*A050486(n-1) = 128*C(n+6,7) - 64*C(n+5,6).

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

D-finite with recurrence (-n+1)*a(n) +2*a(n-1) +16*a(n-2) +2*a(n-3) +(n+7)*a(n-4)=0. - R. J. Mathar, Jan 11 2024

G.f.: 32*x*(1 + x^2)/((1 - x)^8*(1 + x)^6). - Andrew Howroyd, Nov 18 2025

Example

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

Maple

A339358 := proc(n)
    nhalf := ceil(n/2) ;
    if type(n, 'even') then
        128*binomial(nhalf+6, 7)-64*binomial(nhalf+5, 6) ;
    else
        128*binomial(nhalf+4, 7)+128*binomial(nhalf+4, 6)+32*binomial(nhalf+4, 5) ;
    end if;
end proc:
seq(A339358(n), n=1..40) ; # R. J. Mathar, Jan 11 2024

Prog

(PARI) a(n) = my(k=n\2); if(n%2, 128*binomial(k+5, 7) + 128*binomial(k+5, 6) + 32*binomial(k+5, 5), 128*binomial(k+6, 7) - 64*binomial(k+5, 6)); \\ Andrew Howroyd, Nov 18 2025

Crossrefs

Cf. A168380.

Sequence in context: A256819 A358250 A235057 * A249116 A110562 A275187

Adjacent sequences: A339355 A339356 A339357 * A339359 A339360 A339361

Keyword

nonn,easy

Author

Lara Pudwell, Dec 01 2020

Status

approved