A291941 - OEIS

%I #44 Jan 05 2025 19:51:41

%S 1,1,3,3,5,7,9,13,19,21,31,45,53,73,101,129,171,233,295,407,533,701,

%T 921,1251,1605,2175,2837,3797,4945,6681,8637,11679,15165,20403,26525,

%U 35777,46381,62589,81253,109503,142187,191755,248775,335579,435561,587233,762305

%N Number of Carlitz compositions of n that either have length 1, or have length greater than or equal to 2 and are palindromic if we exclude the first part.

%C Carlitz compositions are compositions where adjacent parts are distinct. They are enumerated in sequence A003242.

%C In Hadjicostas and Zhang (2017), compositions that either have length 1, or have length greater than or equal to 2 and are palindromic, if we exclude the first part, are called type II palindromic compositions, while the usual palindromic compositions are called type I palindromic compositions. (Type I palindromic compositions that are Carlitz are enumerated in sequence A239327.)

%C Since in a Carlitz composition adjacent parts are distinct, type II palindromic compositions of length > 1 that are Carlitz must have an even number of parts.

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

%H Alois P. Heinz, <a href="/A291941/b291941.txt">Table of n, a(n) for n = 1..1000</a>

%H P. Hadjicostas, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Hadjicostas/hadji5.html">Cyclic, dihedral and symmetric Carlitz compositions of a positive integer</a>, Journal of Integer Sequences, 20 (2017), Article 17.8.5.

%H P. Hadjicostas and L. Zhang, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Papers1/55-1/HadjicostasZhang10252016.pdf">Sommerville's symmetrical cyclic compositions of a positive integer with parts avoiding multiples of an integer</a>, Fibonacci Quarterly 55 (2017), 54-73.

%F G.f.: x/(1-x) + B(x)^2/(1-A(x))-A(x), where A(x) = Sum_{n>=1} x^(2*n)/(1+x^(2*n)) and B(x) = Sum_{n>=1} x^n/(1+x^(2*n)).

%e For n=6, the a(6)=7 compositions that are type II palindromic and Carlitz are 6, 1+5, 5+1, 2+4, 4+2, 1+2+1+2, and 2+1+2+1. For n=7, the a(7)=9 compositions of this kind are 7, 1+6, 6+1, 2+5, 5+2, 3+4, 4+3, 3+1+2+1, and 2+1+3+1. (For example, the composition 1+6 becomes palindromic, i.e. 6, if we remove the first part. Similarly, the composition 2+1+3+1 becomes palindromic, i.e., 1+3+1, if we remove the first part. A composition of length one, such as 7, is considered palindromic of both types, I and II.)

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

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

%p     end:

%p a:= n-> 1+add(b(n-j, j), j=1..n-1):

%p seq(a(n), n=1..50);  # _Alois P. Heinz_, Sep 08 2017

%t b[n_, i_] := b[n, i] = If[n != i, 1, 0] + Sum[If[i == j, 0, b[n - 2*j, If[j > n - 2*j, 0, j]]], {j, 1, (n - 1)/2}];

%t a[n_] :=  1 + Sum[b[n - j, j], {j, 1, n - 1}];

%t Table[a[n], {n, 1, 50}] (* _Jean-François Alcover_, Jun 06 2018, after _Alois P. Heinz_ *)

%o (PARI) a(n) = { my(A=sum(j=1, n, x^(2*j)/(1+x^(2*j)) + O(x*x^n)), B=sum(j=1, n, x^j/(1+x^(2*j)) + O(x*x^n))); polcoeff(x/(1-x) + B^2/(1-A)-A, n) } \\ _Andrew Howroyd_, Oct 12 2017

%Y Cf. A003242, A239327.

%K nonn

%O 1,3

%A _Petros Hadjicostas_, Sep 06 2017

%E a(26)-a(47) from _Alois P. Heinz_, Sep 07 2017