|
%I #18 Aug 08 2022 14:19:19
%S 1,1,3,6,14,28,60,120,248,496,1008,2016,4064,8128,16320,32640,65408,
%T 130816,261888,523776,1048064,2096128,4193280,8386560,16775168,
%U 33550336,67104768,134209536,268427264,536854528,1073725440,2147450880,4294934528,8589869056,17179803648
%N Number of palindromic compositions of 2n into parts <= n.
%C 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.
%C 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).
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,2,-4).
%F a(n) = ceiling(2^n - 2^floor((n-1)/2)).
%F G.f.: (2*x^3-x^2-x+1)/((2*x-1)*(2*x^2-1)). - _Alois P. Heinz_, May 23 2022
%F a(n) = 2^n - 2^((n-5)/2)*(2 + sqrt(2) + (-1)^n*(sqrt(2) - 2)) for n > 0. - _Stefano Spezia_, May 24 2022
%e a(1)=1: 2 = 1+1.
%e a(2)=3: 4 = 2+2 = 1+1+1+1 = 1+2+1.
%e 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.
%o (Python)
%o def A354294(n): return (1<<n)-(1<<(n-1>>1)) if n else 1 # _Chai Wah Wu_, Aug 08 2022
%Y Cf. A000079, A008464, A016116.
%K nonn,easy
%O 0,3
%A _Gerhard Kirchner_, May 23 2022
|
