A354294 Number of palindromic compositions of 2n into parts <= n.

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).

Links

Table of n, a(n) for n=0..34.

Index entries for linear recurrences with constant coefficients, signature (2,2,-4).

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

Cf. A000079, A008464, A016116.

Sequence in context: A224840 A356804 A345334 * A132891 A200544 A308448

Adjacent sequences: A354291 A354292 A354293 * A354295 A354296 A354297

Keyword

nonn,easy

Author

Gerhard Kirchner, May 23 2022

Status

approved