OFFSET
0,5
COMMENTS
A palindromic composition is a composition that is identical to its own reverse. There are 2^floor(n/2) palindromic compositions. A Carlitz composition has no two consecutive equal parts (A003242). This sequence enumerates compositions that are both palindromic and Carlitz.
Also the number of odd-length integer compositions of n into parts that are alternately unequal and equal (n > 0). The unordered version (partitions) is A053251. - Gus Wiseman, Feb 26 2022
REFERENCES
S. Heubach and T. Mansour, Compositions of n with parts in a set, Congr. Numer. 168 (2004), 127-143.
S. Heubach and T. Mansour, Combinatorics of Compositions and Words, Chapman and Hall, 2010, page 67.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..5000
Petros Hadjicostas, Cyclic, Dihedral and Symmetrical Carlitz Compositions of a Positive Integer, Journal of Integer Sequences, Vol. 20 (2017), Article 17.8.5.
FORMULA
G.f.: (1 + Sum_{j>=1} x^j*(1-x^j)/(1+x^(2*j))) / (1 - Sum_{j>=1} x^(2*j)/(1+x^(2*j))).
a(n) ~ c / r^n, where r = 0.7558768372943356987836792261127971643747976345582722756032673... is the root of the equation sum_{j>=1} x^(2*j)/(1+x^(2*j)) = 1, c = 0.5262391407444644722747255167331403939384758635340487280277... if n is even and c = 0.64032989654153238794063877354074732669441634551692765196197... if n is odd. - Vaclav Kotesovec, Aug 22 2014
EXAMPLE
a(9) = 7 because we have: 9, 1+7+1, 2+5+2, 4+1+4, 1+3+1+3+1, 2+1+3+1+2, 1+2+3+2+1. 2+3+4 is not counted because it is not palindromic. 3+3+3 is not counted because it has consecutive equal parts.
MAPLE
b:= proc(n, i) option remember; `if`(i=0, 0, `if`(n=0, 1,
add(`if`(i=j, 0, b(n-j, j)), j=1..n)))
end:
a:= n-> `if`(n=0, 1, add(b(i, n-2*i), i=0..n/2)):
seq(a(n), n=0..60); # Alois P. Heinz, Mar 16 2014
MATHEMATICA
nn=50; CoefficientList[Series[(1+Sum[x^j(1-x^j)/(1+x^(2j)), {j, 1, nn}])/(1-Sum[x^(2j)/(1+x^(2j)), {j, 1, nn}]), {x, 0, nn}], x]
(* or *)
Table[Length[Select[Level[Map[Permutations, Partitions[n]], {2}], Apply[And, Table[#[[i]]==#[[Length[#]-i+1]], {i, 1, Floor[Length[#]/2]}]]&&Apply[And, Table[#[[i]]!=#[[i+1]], {i, 1, Length[#]-1}]]&]], {n, 0, 20}]
PROG
(PARI) a(n) = polcoeff((1 + sum(j=1, n, x^j*(1-x^j)/(1+x^(2*j)) + O(x*x^n))) / (1 - sum(j=1, n, x^(2*j)/(1+x^(2*j)) + O(x*x^n))), n); \\ Andrew Howroyd, Oct 12 2017
CROSSREFS
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, Mar 16 2014
STATUS
approved