A239327 - OEIS

%I #47 Mar 13 2022 18:59:53

%S 1,1,1,1,2,3,2,5,5,7,10,14,14,25,26,42,48,75,79,132,142,226,252,399,

%T 432,704,760,1223,1336,2143,2328,3759,4079,6564,7150,11495,12496,

%U 20135,21874,35215,38310,61639,67018,107912,117298,188839,205346,330515,359350,578525,628951

%N Number of palindromic Carlitz compositions of n.

%C 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.

%C 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

%D S. Heubach and T. Mansour, Compositions of n with parts in a set, Congr. Numer. 168 (2004), 127-143.

%D S. Heubach and T. Mansour, Combinatorics of Compositions and Words, Chapman and Hall, 2010, page 67.

%H Alois P. Heinz, <a href="/A239327/b239327.txt">Table of n, a(n) for n = 0..5000</a>

%H Petros Hadjicostas, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Hadjicostas/hadji5.html">Cyclic, Dihedral and Symmetrical Carlitz Compositions of a Positive Integer</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.8.5.

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

%F 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

%e 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.

%p b:= proc(n, i) option remember; `if`(i=0, 0, `if`(n=0, 1,

%p       add(`if`(i=j, 0, b(n-j, j)), j=1..n)))

%p     end:

%p a:= n-> `if`(n=0, 1, add(b(i, n-2*i), i=0..n/2)):

%p seq(a(n), n=0..60);  # _Alois P. Heinz_, Mar 16 2014

%t 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]

%t (* or *)

%t 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}]

%o (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

%Y Carlitz compositions are counted by A003242.

%Y Palindromic compositions are counted by A016116.

%Y The unimodal case is A096441.

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

%K nonn

%O 0,5

%A _Geoffrey Critzer_, Mar 16 2014