login
A354294
Number of palindromic compositions of 2n into parts <= n.
1
1, 1, 3, 6, 14, 28, 60, 120, 248, 496, 1008, 2016, 4064, 8128, 16320, 32640, 65408, 130816, 261888, 523776, 1048064, 2096128, 4193280, 8386560, 16775168, 33550336, 67104768, 134209536, 268427264, 536854528, 1073725440, 2147450880, 4294934528, 8589869056, 17179803648
OFFSET
0,3
COMMENTS
Proof of the formula: An even number 2k must be located in the middle of a palindromic composition of 2n such that a composition of n-k preceeds and its mirror image follows 2k. For k=0, the middle is empty. 0 <= 2k <= n => b(n) <= n-k <= n with b(n) = floor((n+1)/2.
a(n) = Sum_{j=b(n)..n} C(j) where C(j) = 2^(j-1) is the number of all compositions of j. This yields a(n) = 2^n - 2^(b(n)-1).
FORMULA
a(n) = ceiling(2^n - 2^floor((n-1)/2)).
G.f.: (2*x^3-x^2-x+1)/((2*x-1)*(2*x^2-1)). - Alois P. Heinz, May 23 2022
a(n) = 2^n - 2^((n-5)/2)*(2 + sqrt(2) + (-1)^n*(sqrt(2) - 2)) for n > 0. - Stefano Spezia, May 24 2022
EXAMPLE
a(1)=1: 2 = 1+1.
a(2)=3: 4 = 2+2 = 1+1+1+1 = 1+2+1.
a(3)=6: 6 = 3+3 = 2+1+1+2 = 1+2+2+1 = 1+1+1+1+1+1 = 2+2+2 = 1+1+2+1+1.
PROG
(Python)
def A354294(n): return (1<<n)-(1<<(n-1>>1)) if n else 1 # Chai Wah Wu, Aug 08 2022
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Gerhard Kirchner, May 23 2022
STATUS
approved