login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A291941 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. 4
1, 1, 3, 3, 5, 7, 9, 13, 19, 21, 31, 45, 53, 73, 101, 129, 171, 233, 295, 407, 533, 701, 921, 1251, 1605, 2175, 2837, 3797, 4945, 6681, 8637, 11679, 15165, 20403, 26525, 35777, 46381, 62589, 81253, 109503, 142187, 191755, 248775, 335579, 435561, 587233, 762305 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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

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

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.

REFERENCES

P. Hadjicostas and L. Zhang, "Sommerville's symmetrical cyclic compositions of a positive integer with parts avoiding multiples of an integer," Fibonacci Quarterly 55 (2017), 54-73.

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

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..1000

P. Hadjicostas, Cyclic, dihedral and symmetric Carlitz compositions of a positive integer, Journal of Integer Sequences, 20 (2017), Article 17.8.5.

FORMULA

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

EXAMPLE

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

MAPLE

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

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

    end:

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

seq(a(n), n=1..50);  # Alois P. Heinz, Sep 08 2017

MATHEMATICA

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}];

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

Table[a[n], {n, 1, 50}] (* Jean-Fran├žois Alcover, Jun 06 2018, after Alois P. Heinz *)

PROG

(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

CROSSREFS

Cf. A003242, A239327.

Sequence in context: A323431 A211516 A323430 * A086341 A176513 A128424

Adjacent sequences:  A291938 A291939 A291940 * A291942 A291943 A291944

KEYWORD

nonn

AUTHOR

Petros Hadjicostas, Sep 06 2017

EXTENSIONS

a(26)-a(47) from Alois P. Heinz, Sep 07 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 1 03:14 EDT 2020. Contains 334758 sequences. (Running on oeis4.)