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
KEYWORD
nonn
AUTHOR
Lara Pudwell, Dec 01 2020
STATUS
approved