A291941 -id:A291941 - cp's OEIS frontend

A292200 Number of Sommerville symmetrical cyclic compositions (on symmetric necklaces) of n that are Carlitz (adjacent parts on the circle are distinct).

1, 1, 2, 2, 3, 4, 5, 7, 10, 11, 16, 23, 27, 37, 51, 65, 86, 117, 148, 204, 267, 351, 461, 626, 803, 1088, 1419, 1899, 2473, 3341, 4319, 5840, 7583, 10202, 13263, 17889, 23191, 31295, 40627, 54752, 71094, 95878, 124388, 167790, 217781, 293617, 381153, 513989, 667029, 899589

Offset: 1

Petros Hadjicostas, Sep 11 2017

nonn

We consider cyclic compositions (necklaces) as equivalence classes of compositions that can be obtained from each other by a cyclic shift. A cyclic composition is called Sommerville symmetrical (on a symmetric necklace) if its equivalence class contains at least one palindromic composition (type I) or a composition that becomes a palindromic composition if we remove the first part (type II). A composition with only one part is a palindromic composition of both types.

The equivalence class of each Sommerville symmetrical cyclic composition that is Carlitz contains exactly two type II palindromic Carlitz compositions (except in the case of a composition with only one part). For example, when n = 8, the equivalence class {(1,2,3,2), (2,3,2,1), (3,2,1,2), (2,1,2,3)} represents a Sommerville symmetrical cyclic composition of n = 8 that is Carlitz, but only two of the compositions in the set, i.e., (1,2,3,2) and (3,2,1,2), are type II palindromic.

			For n = 7, there are exactly a(7) = 5 Sommerville symmetrical cyclic compositions (symmetric necklaces) of 7 that are Carlitz: 7, 1+6, 2+5, 3+4, 2+1+3+1. (Note that 1+6 is the same as 6+1, 3+1+2+1 is the same as 2+1+3+1, and so on, because in each case one composition can be obtained from the other by a cyclic shift.)

Petros Hadjicostas, Cyclic, dihedral and symmetrical Carlitz compositions of a positive integer, Journal of Integer Sequences, 20 (2017), Article 17.8.5.
Petros Hadjicostas, Generalized colored circular palindromic compositions, Moscow Journal of Combinatorics and Number Theory, 9(2) (2020), 173-186.
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.
D. M. Y. Sommerville, On certain periodic properties of cyclic compositions of numbers, Proc. London Math. Soc. S2-7(1) (1909), 263-313.

Cf. A119963, A291941.

a(n) = (A291941(n) + 1)/2.

G.f.: x/(1 - x) - A(x)/2 + B(x)^2/(2*(1 - 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)).

More terms from Altug Alkan, Sep 18 2017

A292906 Number of dihedral Carlitz compositions of n.

Original entry on oeis.org

1, 1, 2, 2, 3, 5, 6, 9, 14, 20, 29, 48, 69, 110, 175, 278, 441, 725, 1168, 1928, 3170, 5253, 8710, 14563, 24308, 40798, 68520, 115433, 194611, 328938, 556336, 942659, 1598539, 2714379, 4612681, 7847082, 13358850, 22762311, 38810771, 66223599, 113067441, 193172332

Offset: 1

Petros Hadjicostas, Oct 10 2017

nonn

A cyclic Carlitz composition is a composition of length greater than one where adjacent parts, including the first and the last ones, are distinct. A composition of length one is also considered cyclic and Carlitz. Assume two cyclic Carlitz compositions are considered equivalent iff one can be obtained from the other by a rotation or reversal of order. Each equivalence class obtained is called a dihedral Carlitz composition of n.

			a(6) = 5 because n = 6 has the following dihedral Carlitz compositions: 6, 1+5, 2+4, 1+2+3, 1+2+1+2. (For example, the equivalence class for the dihedral Carlitz composition 1+2+3 is {(1,2,3),(2,3,1), (3,1,2), (3,2,1),(2,1,3),(1,3,2)}.)

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

Cf. A106369, A291941, A292200.

a(n) = (A106369(n) + A292200(n))/2.
a(n) = (2*A106369(n) + A291941(n) + 1)/4.
G.f.: (g.f. of A106369 + g.f. of A292200)/2.

A296167 Triangle read by rows: T(n,k) is the number of circular compositions of n with length k such that no two adjacent parts are equal (1 <= k <= n).

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 2, 0, 0, 0, 1, 2, 2, 1, 0, 0, 1, 3, 2, 1, 0, 0, 0, 1, 3, 4, 3, 0, 0, 0, 0, 1, 4, 6, 4, 2, 1, 0, 0, 0, 1, 4, 8, 11, 4, 1, 0, 0, 0, 0, 1, 5, 10, 13, 10, 3, 0, 0, 0, 0, 0, 1, 5, 14, 22, 18, 10, 2, 1, 0, 0, 0, 0, 1, 6, 16, 29, 32, 20, 6, 1, 0, 0, 0, 0, 0, 1, 6, 20, 44, 50, 40, 18, 4, 0, 0, 0, 0, 0, 0

Offset: 1

Petros Hadjicostas, Dec 07 2017

By "circular compositions" here we mean equivalence classes of compositions with parts on a circle such that two compositions are equivalent if one is a cyclic shift of the other. We may call them "circular Carlitz compositions".
The formula below for T(n,k) involves indicator functions of conditions because unfortunately circular compositions of length 1 are considered Carlitz by most authors (even though, strictly speaking, they are not since the single number in such a composition is "next to itself" if we go around the circle).
To prove that the two g.f.'s below are equal to each other, use the geometric series formula, change the order of summations where it is necessary, and use the result Sum_{n >= 1} (phi(n)/n)*log(1 + x^n) = Sum_{n >= 1} (phi(n)/n)*log(1 - x^(2*n)) - Sum_{n >= 1} (phi(n)/n)*log(1 - x^n) = -x^2/(1 - x^2) + x/(1 - x) = x/(1 - x^2).

			Triangle T(n,k) (with rows n >= 1 and columns k = 1..n) begins:
  1;
  1,  0;
  1,  1,  0;
  1,  1,  0,  0;
  1,  2,  0,  0,  0;
  1,  2,  2,  1,  0,  0;
  1,  3,  2,  1,  0,  0,  0;
  1,  3,  4,  3,  0,  0,  0,  0;
  1,  4,  6,  4,  2,  1,  0,  0,  0;
  1,  4,  8, 11,  4,  1,  0,  0,  0,  0;
  ...
Case n=6:
The included circular compositions are:
k=1: 6;                                => T(6,1) = 1
k=2: 15, 24;                           => T(6,2) = 2
k=3: 123, 321;                         => T(6,3) = 2
k=4: 1212;                             => T(6,4) = 1
k=5: none;                             => T(6,5) = 0
k=6: none;                             => T(6,6) = 0

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

Row sums are in A106369.

Cf. A003242, A239327, A291941, A293595.

nmax = 14; gf (* of A293595 *) = Sum[x^(2j) y^2/(1 + x^j y), {j, 1, nmax}] + Sum[x^j y/(1 + x^j y)^2, {j, 1, nmax}]/(1 - Sum[x^j y/(1 + x^j y), {j, 1, nmax}]) + O[x]^(nmax + 1) + O[y]^(nmax + 1) // Normal // Expand;
A293595[n_, k_] := SeriesCoefficient[gf, {x, 0, n}, {y, 0, k}];
T[n_, k_] := Boole[k == 1] + (1/k) Sum[EulerPhi[d] A293595[n/d, k/d]* Boole[k/d != 1], {d, Divisors[GCD[n, k]]}];
Table[T[n, k], {n, 1, nmax}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jul 26 2020 *)

T(n,k) = [k = 1] + (1/k)*Sum_{d | gcd(n,k)} phi(d)*A293595(n/d, k/d) * [k/d <> 1], where [ ] is the Iverson Bracket.
G.f.: Sum_{n,k >= 1} T(n,k)*x^n*y^k = x*y/(1-x) - Sum_{s>=1} (phi(s)/s)*f(x^s,y^s), where f(x,y) = log(1 - Sum_{n >= 1} x^n*y/(1 + x^n*y)) + Sum_{n >= 1} log(1 + x^n*y).
G.f.: -Sum_{s >= 1} (x*y)^(2*s + 1)/(1-x^(2*s + 1)) - Sum_{s >= 1} (phi(s)/s)*g(x^s,y^s), where g(x,y) = log(1 + Sum_{n >= 1} (-x*y)^n/(1 - x^n)).

A373420 Number of Carlitz compositions of n (see A003242) such that the first and last parts are equal.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 2, 7, 11, 17, 26, 54, 86, 155, 272, 464, 816, 1447, 2507, 4400, 7706, 13456, 23570, 41293, 72212, 126394, 221282, 387219, 677714, 1186311, 2076170, 3633761, 6360219, 11131698, 19483066, 34100455, 59683664, 104460655, 182832044, 319999739

Offset: 0

John Tyler Rascoe, Aug 16 2024

			a(7) = 7 counts: (1,2,1,2,1), (1,2,3,1), (1,3,2,1), (1,5,1), (2,3,2), (3,1,3), and (7).

Cf. A001045, A003242, A285981, A291941, A374517.

C_x(N) = {my(g=1/(1-sum(k=1, N, x^k/(1+x^k))));g}
A_x(i,N) = {my( x='x+O('x^N), f=(x^i)*(C_x(N)*(x^i)+x^i+1)/(1+x^i)^2);f}
D_x(N) = {my( x='x+O('x^N), f=1+sum(i=1,N, A_x(i,N))); Vec(f)}
D_x(40)

G.f.: 1 + Sum_{i>0} (x^i)*(C(x)*(x^i) + x^i + 1)/(1+x^i)^2 where C(x) is the g.f. for A003242.

cp's OEIS Frontend

A292200 Number of Sommerville symmetrical cyclic compositions (on symmetric necklaces) of n that are Carlitz (adjacent parts on the circle are distinct).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A292906 Number of dihedral Carlitz compositions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A296167 Triangle read by rows: T(n,k) is the number of circular compositions of n with length k such that no two adjacent parts are equal (1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A373420 Number of Carlitz compositions of n (see A003242) such that the first and last parts are equal.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula