Joshua P. Bowman - cp's OEIS frontend

A366045 Number of circular binary sequences of length n with an odd number of 0's and no three consecutive 1's.

1, 2, 4, 4, 11, 20, 36, 64, 121, 222, 408, 748, 1379, 2536, 4664, 8576, 15777, 29018, 53372, 98164, 180555, 332092, 610812, 1123456, 2066361, 3800630, 6990448, 12857436, 23648515, 43496400, 80002352, 147147264, 270646017, 497795634, 915588916, 1684030564

Offset: 1

Joshua P. Bowman, Sep 27 2023

A circular binary sequence is a finite sequence of 0's and 1's for which the first and last digits are considered to be adjacent. Rotations are distinguished from each other. Also called a marked cyclic binary sequence.

a(n) is also equal to the number of circular compositions of n into an odd number of 1's, 2's, and 3's.

			a(1)=1 because 0 is the only allowed sequence of length one, and a(2)=2 because 01 and 10 are the only allowed sequences of length two.
The allowed sequences of length three are 000, 011, 101, and 110. The allowed sequences of length four are 0001, 0010, 0100, and 1000. Thus a(3)=a(4)=4.

Joshua P. Bowman, Compositions with an Odd Number of Parts, and Other Congruences, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 19.
Petros Hadjicostas and Lingyun Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 1662-1674.
W. O. J. Moser, Cyclic binary strings without long runs of like (alternating) bits, Fibonacci Quart. 31 (1993), no. 1, 2-6.
Index entries for linear recurrences with constant coefficients, signature (0,1,2,3,2,1).

Cf. A001644, A283834, A366043, A366044.

LinearRecurrence[{0, 1, 2, 3, 2, 1}, {1, 2, 4, 4, 11, 20}, 50]

G.f.: x*(1+2*x+3*x^2)/((1-x-x^2-x^3)*(1+x+x^2+x^3)).
a(n) = (1/2)*A001644(n) + 1/2 - 2*[n==0 (mod 4)].
a(n) = a(n-2) + 2*a(n-3) + 3*a(n-4) + 2*a(n-5) + a(n-6), a(1)=1, a(2)=2, a(3)=4, a(4)=4, a(5)=11, a(6)=20.
a(n) = A001644(n) - A366044(n).

A366044 Number of circular binary sequences of length n with an even number of 0's and no three consecutive 1's.

Original entry on oeis.org

0, 1, 3, 7, 10, 19, 35, 67, 120, 221, 407, 751, 1378, 2535, 4663, 8579, 15776, 29017, 53371, 98167, 180554, 332091, 610811, 1123459, 2066360, 3800629, 6990447, 12857439, 23648514, 43496399, 80002351, 147147267, 270646016, 497795633, 915588915, 1684030567, 3097415114, 5697034595, 10478480275

Offset: 1

Joshua P. Bowman, Sep 27 2023

A circular binary sequence is a finite sequence of 0's and 1's for which the first and last digits are considered to be adjacent. Rotations are distinguished from each other. Also called a marked cyclic binary sequence.

a(n) is also equal to the number of circular compositions of n into an even number of 1s, 2s, and 3s.

			The sequence ‘1’ is not allowed because the 1 is considered to be adjacent to itself. Similarly ’11’ is not allowed. Thus a(1)=0 because the sequence ‘0’ does not have an even number of 0's, and a(2)=1 because ’00’ is the only allowed sequence of length two.
For n=4, the a(4)=7 allowed sequences are 0000, 0011, 0101, 0110, 1001, 1010, 1100.

Joshua P. Bowman, Compositions with an Odd Number of Parts, and Other Congruences, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 19.
Petros Hadjicostas and Lingyun Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 1662-1674.
W. O. J. Moser, Cyclic binary strings without long runs of like (alternating) bits, Fibonacci Quart. 31 (1993), no. 1, 2-6.
Index entries for linear recurrences with constant coefficients, signature (0,1,2,3,2,1).

Cf. A001644, A366045.

LinearRecurrence[{0, 1, 2, 3, 2, 1}, {0, 1, 3, 7, 10, 19}, 50]

G.f.: x^2*(1+2*x+3*x^2)*(1+x+x^2)/((1-x-x^2-x^3)*(1+x+x^2+x^3)).
a(n) = (1/2)*A001644(n) - 1/2 + 2*[n==0 (mod 4)].
a(n) = a(n-2)+2*a(n-3)+3*a(n-4)+2*a(n-5)+a(n-6), a(1)=0, a(2)=1, a(3)=3, a(4)=7, a(5)=10, a(6)=19.
a(n) = A001644(n) - A366045(n).

A366043 Number of circular binary sequences of length n with an odd number of 0's and no consecutive 1's.

Original entry on oeis.org

1, 2, 1, 4, 6, 8, 15, 24, 37, 62, 100, 160, 261, 422, 681, 1104, 1786, 2888, 4675, 7564, 12237, 19802, 32040, 51840, 83881, 135722, 219601, 355324, 574926, 930248, 1505175, 2435424, 3940597, 6376022, 10316620, 16692640, 27009261, 43701902, 70711161, 114413064, 185124226, 299537288, 484661515, 784198804, 1268860317

Offset: 1

Joshua P. Bowman, Sep 27 2023

A circular binary sequence is a finite sequence of 0's and 1's for which the first and last digits are considered to be adjacent. Rotations are distinguished from each other. Also called a marked cyclic binary sequence.
a(n) is also equal to the number of matchings in the cycle graph C_n for which the number of edges plus the number of unmatched vertices is odd.
a(n) is also equal to the number of circular compositions of n into an odd number of 1's and 2's.

			For n = 5, the a(5) = 6 allowed sequences are 00000, 00101, 01001, 01010, 10010, 10100.

Joshua P. Bowman, Compositions with an Odd Number of Parts, and Other Congruences, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 19.
Petros Hadjicostas and Lingyun Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 1662-1674.
W. O. J. Moser, Cyclic binary strings without long runs of like (alternating) bits, Fibonacci Quart. 31 (1993), no. 1, 2-6.
Index entries for linear recurrences with constant coefficients, signature (0,1,2,1).

Cf. A000204, A061347, A100886.

LinearRecurrence[{0, 1, 2, 1}, {0, 1, 2, 1}, 50]

G.f.: x*(1+2*x)/((1-x-x^2)*(1+x+x^2)).
a(n) = a(n-2) + 2*a(n-3) + a(n-4), a(0) = 0, a(1) = 1, a(2) = 2, a(3) = 1.
a(n) = (A000204(n) + A061347(n))/2.
a(n) = (1/2)*A000204(n) - cos(2*Pi*n/3).
a(n) = A000204(n) - A100886(n-1).

A365858 Number of cyclic compositions of 2*n-1 into odd parts.

Original entry on oeis.org

1, 2, 3, 5, 10, 19, 41, 94, 211, 493, 1170, 2787, 6713, 16274, 39651, 97109, 238838, 589527, 1459961, 3626242, 9030451, 22542397, 56393862, 141358275, 354975433, 892893262, 2249412291, 5674891017, 14335757586, 36259245523, 91815545801, 232745229290, 590586152235, 1500020153485, 3813274653414

Offset: 1

Joshua P. Bowman, Sep 20 2023

nonn

Odd bisection of A032189.

Also the number of cyclic compositions into an odd number of odd parts; because such a sum must be odd, alternating terms are zero and have been removed.

Joshua P. Bowman, Compositions with an Odd Number of Parts, and Other Congruences, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 25.
Brian Hopkins, Jesús Sistos Barrón, and Hua Wang, Conjugating cyclic n-color compositions, Utilitas Mathematica (2025) Vol. 122, 53-64. See p. 62.
Jesus Omar Sistos Barron, Counting Conjugates of Colored Compositions, Honors College Thesis, Georgia Southern Univ. (2024), No. 985. See p. 30.

Cf. A000010, A000204 (Lucas), A032189, A365857, A365859.

Table[1/(2*n - 1) * Sum[EulerPhi[k]*LucasL[(2*n - 1)/k], {k, Divisors[2*n - 1]}], {n, 1, 40}] (* Vaclav Kotesovec, Sep 22 2023 *)

N=99;  x='x+O('x^N); B(x)=x/(1-x^2);
A=Vec(sum(k=1, N, eulerphi(k)/k*log(1/(1-B(x^k)))));
vector(#A\2,n,A[2*n-1]) \\ Joerg Arndt, Sep 22 2023

from sympy import totient, lucas, divisors
def A365858(n): return sum(totient(((n<<1)-1)//k)*(lucas(k)-((k&1^1)<<1)) for k in divisors((n<<1)-1,generator=True))//((n<<1)-1) # Chai Wah Wu, Sep 23 2023

G.f.: (1/2) * Sum_{k odd} (phi(k)/k)*log((1+x^k-x^(2k))/(1-x^k-x^(2*k))), where phi(n) = A000010(n).
a(n) = (1/(2*n-1)) * Sum_{k divides 2n-1} phi(k)*A000204((2*n-1)/k).
a(n) ~ ((1+sqrt(5))/2)^(2*n-1) / (2*n). - Vaclav Kotesovec, Sep 22 2023

A365859 Number of self-dual cyclic n-color compositions.

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 5, 1, 10, 3, 19, 2, 41, 5, 94, 1, 211, 10, 493, 3, 1170, 19, 2787, 2, 6713, 41, 16274, 5, 39651, 94, 97109, 1, 238838, 211, 589527, 10, 1459961, 493, 3626242, 3, 9030451, 1170, 22542397, 19, 56393862, 2787, 141358275, 2, 354975433, 6713, 892893262, 41, 2249412291, 16274, 5674891017

Offset: 1

Joshua P. Bowman, Sep 20 2023

nonn

A cyclic composition is a sum in which the order of the parts is considered up to cyclic permutation. In other words, it is the collection of components remaining in the cycle graph C_n on n vertices when one or more edges are removed, and rotations are considered equivalent. In an n-color composition, each part of size k is assigned one of k "colors" which may be represented graphically by marking one vertex in the part. The dual of a cyclic n-color composition is obtained by switching the roles of edges and vertices in C_n, then removing each edge that came from a previously marked vertex while marking each vertex that came from a previously removed edge. A cyclic n-color composition is self-dual if it is invariant under this process.
a(n) is also the number of cyclic compositions of A000265(n) into odd parts.
This sequence is self-similar; removing all odd-indexed terms results in the same sequence.

			Every power of 2 has only one self-dual cyclic n-color composition, which has all parts of size 1.
The self-dual cyclic n-color compositions of 5 are 1_1+1_1+1_1+1_1+1_1, 1_1+2_2+2_1, and 5_3, where the subscript indicates the color of the part, or which vertex is marked within the part.

A. K. Agarwal, n-colour compositions, Indian J. Pure Appl. Math. 31 (11) (2000), 1421-1427.
Joshua P. Bowman, Compositions with an Odd Number of Parts, and Other Congruences, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 33.
Meghann Moriah Gibson, Daniel Gray, and Hua Wang, Combinatorics of n-color cyclic compositions, Discrete Mathematics 341 (2018), 3209-3226.
Brian Hopkins, Jesús Sistos Barrón, and Hua Wang, Conjugating cyclic n-color compositions, Utilitas Mathematica (2025) Vol. 122, 53-64. See p. 61.
Jesus Omar Sistos Barron, Counting Conjugates of Colored Compositions, Honors College Thesis, Georgia Southern Univ. (2024), No. 985. See p. 25.

Cf. A000204 (Lucas), A000265, A032189, A032198, A365857, A365858.

my(N=66,x='x+O('x^N)); Vec( sum(k=1,N, eulerphi(2*k)/(2*k) * log((1+x^k-x^(2*k))/(1-x^k-x^(2*k))) ) )  \\ Joerg Arndt, Sep 21 2023

from sympy import totient, lucas, divisors
def A365859(n):
    m = n>>(~n&n-1).bit_length()
    return sum(totient(k)*lucas(m//k) for k in divisors(m,generator=True))//m # Chai Wah Wu, Sep 23 2023

G.f.: Sum_{k>=1} phi(2*k)/(2*k) * log((1+x^k-x^(2*k))/(1-x^k-x^(2*k))).
a(n) = (1/(b(n)))*[Sum_{k divides A000265(n)} phi(k)*lucas(b(n)/k)], where b(n) = A000265(n) and lucas(n) = A000204(n).
a(n) = 2*A365857(n) - A032198(n).

A365857 Number of cyclic compositions of 2*n into odd parts.

Original entry on oeis.org

1, 2, 4, 7, 14, 30, 63, 142, 328, 765, 1810, 4340, 10461, 25414, 62074, 152287, 375166, 927554, 2300347, 5721044, 14264308, 35646311, 89264834, 223959710, 562878429, 1416953362, 3572233420, 9018211989, 22795835726, 57690911720, 146164582455, 370705552702, 941109975022, 2391391374017, 6081865318124

Offset: 1

Joshua P. Bowman, Sep 20 2023

nonn

Even bisection of A032189.
Also the number of cyclic compositions into an even number of odd parts; because such a sum must be even, alternating terms are zero and have been removed.
Also the number of dual classes of cyclic n-color compositions of n. A cyclic composition is a sum of positive integers in which the order of the parts is considered up to cyclic permutation. In other words, it is the collection of components remaining in the cycle graph C_n on n vertices when one or more edges are removed, and rotations are considered equivalent. In an n-color composition, each part of size k is assigned one of k "colors" which may be represented graphically by marking one vertex in the part. (See A032198 for the number of cyclic n-color compositions.) The dual of a cyclic n-color composition is obtained by switching the roles of edges and vertices in C_n, then removing each edge that came from a previously marked vertex while marking each vertex that came from a previously removed edge. Each cyclic n-color composition of n either belongs to a dual pair or is self-dual. (See A365859 for the number of self-dual cyclic n-color compositions.)

A. K. Agarwal, n-colour compositions, Indian J. Pure Appl. Math. 31 (11) (2000), 1421-1427.
Joshua P. Bowman, Compositions with an Odd Number of Parts, and Other Congruences, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 25.
Meghann Moriah Gibson, Daniel Gray, and Hua Wang, Combinatorics of n-color cyclic compositions, Discrete Mathematics 341 (2018), 3209-3226.

Cf. A001350, A032189, A032198, A365858, A365859.

N=99;  x='x+O('x^N); B(x)=x/(1-x^2);
A=Vec(sum(k=1, N, eulerphi(k)/k*log(1/(1-B(x^k)))));
vector(#A\2,n,A[2*n]) \\ Joerg Arndt, Sep 22 2023

from sympy import totient, lucas, divisors
def A365857(n): return sum(totient((n<<1)//k)*(lucas(k)-((k&1^1)<<1)) for k in divisors(n<<1,generator=True))//n>>1 # Chai Wah Wu, Sep 23 2023

G.f.: (1/2)*(Sum_{k>=1} phi(k)/k * log((1-2*x^k+x^(2*k))/(1-3*x^k+x^(2*k))) + Sum_{m>=1} phi(2*m)/(2*m) * log((1+x^m-x^(2*m))/(1-x^m-x^(2*m)))).
a(n) = (1/(2*n)) * Sum_{k divides 2*n} phi(k)*A001350((2*n)/k).
a(n) = (A032198(n) + A365859(n))/2.

cp's OEIS Frontend

User: Joshua P. Bowman

A366045 Number of circular binary sequences of length n with an odd number of 0's and no three consecutive 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A366044 Number of circular binary sequences of length n with an even number of 0's and no three consecutive 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A366043 Number of circular binary sequences of length n with an odd number of 0's and no consecutive 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A365858 Number of cyclic compositions of 2*n-1 into odd parts.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A365859 Number of self-dual cyclic n-color compositions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

A365857 Number of cyclic compositions of 2*n into odd parts.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Python

Formula