|
|
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
|
S. Heubach and T. Mansour, "Compositions of n with parts in a set," Congr. Numer. 168 (2004), 127-143.
|
|
LINKS
|
|
|
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):
|
|
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}];
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|