A239327 Number of palindromic Carlitz compositions of n.

1, 1, 1, 1, 2, 3, 2, 5, 5, 7, 10, 14, 14, 25, 26, 42, 48, 75, 79, 132, 142, 226, 252, 399, 432, 704, 760, 1223, 1336, 2143, 2328, 3759, 4079, 6564, 7150, 11495, 12496, 20135, 21874, 35215, 38310, 61639, 67018, 107912, 117298, 188839, 205346, 330515, 359350, 578525, 628951

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

Carlitz compositions are counted by A003242.

Palindromic compositions are counted by A016116.

The unimodal case is A096441.

Cf. A053251, A122129, A122130, A351003, A351006, A351007.

Sequence in context: A133775 A099043 A318677 * A021047 A249492 A113649

Adjacent sequences: A239324 A239325 A239326 * A239328 A239329 A239330

Keyword

nonn

Author

Geoffrey Critzer, Mar 16 2014

Status

approved