A322057 -id:A322057 - cp's OEIS frontend

A093305 Number of binary necklaces of length n with no subsequence 000.

1, 2, 3, 4, 5, 9, 11, 19, 29, 48, 75, 132, 213, 369, 627, 1083, 1857, 3244, 5619, 9844, 17205, 30229, 53115, 93701, 165313, 292464, 517831, 918578, 1630933, 2900109, 5161443, 9197251, 16402841, 29283026, 52319379, 93558968, 167427845, 299846737, 537358107, 963651447, 1729192433

Offset: 1

Philippe Deléham, Apr 24 2004

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 500.

Michael De Vlieger, Table of n, a(n) for n = 1..500
P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
Petros Hadjicostas, Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence, Journal of Integer Sequences, 19 (2016), #16.8.2.
Silvana Ramaj, New Results on Cyclic Compositions and Multicompositions, Master's Thesis, Georgia Southern Univ., 2021. See p. 57.
L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96.

Row 3 of A322057.

Cf. A000358, A001644, A280218, A280303.

Table[1/n * Sum[EulerPhi[n/d] (d Sum[Sum[Binomial[j, d - 3 k + 2 j] Binomial[k, j], {j, d - 3 k, k}]/k, {k, d}]), {d, Divisors@ n}], {n, 41}] (* Michael De Vlieger, Dec 28 2016, after Vladimir Joseph Stephan Orlovsky at A001644 *)

N=66;  x='x+O('x^N);
B(x)=x*(1+x+x^2);
A=sum(k=1, N, eulerphi(k)/k*log(1/(1-B(x^k))));
Vec(A)
/* Joerg Arndt, Aug 06 2012 */

a(n) = (1/n) * Sum_{d divides n} totient(n/d)*A001644(d).
G.f.: Sum_{k>=1} phi(k)/k * log( 1/(1-B(x^k)) ) where B(x) = x*(1+x+x^2). - Joerg Arndt, Aug 06 2012
a(n) ~ d^n / n, where d = (19 + 3*sqrt(33))^(1/3)/3 + 4/(3*(19 + 3*sqrt(33))^(1/3)) + 1/3 = A058265 = 1.8392867552141611325518... - Vaclav Kotesovec, Jul 13 2019

A280218 Number of binary necklaces of length n with no subsequence 0000.

Original entry on oeis.org

1, 2, 3, 5, 6, 11, 15, 27, 43, 75, 125, 228, 391, 707, 1262, 2285, 4119, 7525, 13691, 25111, 46033, 84740, 156123, 288529, 533670, 989305, 1835983, 3412885, 6351031, 11834623, 22074821, 41222028, 77048131, 144148859, 269913278, 505826391, 948652695, 1780473001, 3343960175, 6284560319, 11818395345

Offset: 1

Petros Hadjicostas, Dec 29 2016

nonn

a(n) is the number of cyclic sequences of length n consisting of zeros and ones that do not contain four consecutive zeros provided we consider as equivalent those sequences that are cyclic shifts of each other.

			a(5)=6 because we have six binary cyclic sequences of length 5 that avoid four consecutive zeros: 00011, 00101, 00111, 01101, 01111, 11111.

Alois P. Heinz, Table of n, a(n) for n = 1..3521
P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
Silvana Ramaj, New Results on Cyclic Compositions and Multicompositions, Master's Thesis, Georgia Southern Univ., 2021. See p. 57.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96.

Row 4 of A322057.

Cf. A000358, A073817, A093305, A280303.

Table[(1/n) Sum[EulerPhi[n/d] SeriesCoefficient[(4 - 3 x - 2 x^2 - x^3)/(1 - x - x^2 - x^3 - x^4), {x, 0, d}], {d, Divisors@ n}], {n, 41}] (* Michael De Vlieger, Dec 30 2016 *)

N=44; x='x+O('x^N);
B(x)=x*(1+x+x^2+x^3);
Vec(sum(k=1, N, eulerphi(k)/k * log(1/(1-B(x^k))))) \\ Joerg Arndt, Dec 29 2016

a(n) = (1/n) * Sum_{d divides n} totient(n/d) * A073817(d).

G.f.: Sum_{k>=1} (phi(k)/k) * log(1/(1-B(x^k))) where B(x) = x*(1+x+x^2+x^3).

A212634 Triangle read by rows: T(n,k) is the number of dominating subsets with cardinality k of the cycle C_n (n >= 1, 1 <= k <= n).

Original entry on oeis.org

1, 2, 1, 3, 3, 1, 0, 6, 4, 1, 0, 5, 10, 5, 1, 0, 3, 14, 15, 6, 1, 0, 0, 14, 28, 21, 7, 1, 0, 0, 8, 38, 48, 28, 8, 1, 0, 0, 3, 36, 81, 75, 36, 9, 1, 0, 0, 0, 25, 102, 150, 110, 45, 10, 1, 0, 0, 0, 11, 99, 231, 253, 154, 55, 11, 1

Offset: 1

Emeric Deutsch, Jun 14 2012

The entries in row n are the coefficients of the domination polynomial of the cycle C_n (see the Alikhani and Peng reference in Opuscula Math).
Sum of entries in row n = A001644(n) (number of dominating subsets; tribonacci numbers with initial values 1,3,7).
From Petros Hadjicostas, Jan 26 2019: (Start)
Let L(n, r, K) be the number of r-combinations of the n consecutive integers 1, 2, ..., n displaced on a circle, with no K integers consecutive (assuming that n and 1 are consecutive integers).
If on the circle where the n integers 1, 2, ..., n are displaced we put 1 for any integer that is included in the r-combination and 0 otherwise, we get a marked cyclic sequence of r ones and n-r zeros with no K consecutive ones.
Let L_{n,K}(x) = Sum_{r=0..floor(n-(n/K))} L(n, r, K)*x^(n-r) for n, K >= 1. Charalambides (1991) proved that L_{n,K}(x) = x*(n + Sum_{j=1..n-1} L_{n-j, K}(x)) for K >= 1 and 1 <= n <= K, and L_{n,K}(x) = x*Sum_{j=1..K} L_{n-j, K}(x) for K >= 1 and n >= K + 1. See Theorem 2.1 (p. 291) in his paper.
He also proved that L_{n,K}(x) = -1 + Sum_{j=0..floor(n/(K + 1))} (-1)^j*(n/(n-j*K))*binomial(n - j*K, j)*x^j*(1+x)^(n-j*(K+1)). See Theorem 2.3 (p. 293) in his paper.
He also produced other formulas for L(n, r, K) and L_{n,K}(x) including the explicit formulas of Moser and Abramson (1969) (regarding L(n, r, K)).
For the current sequence, we have T(n, k) = L(n, r = n-k, K = 3) for 1 <= n <= k. In other words, T(n, n-k) is the number of k-combinations of the n consecutive integers 1, 2, ..., n displaced on a circle, with no K = 3 consecutive integers (assuming n and 1 are consecutive).
(End)

			Row 4 is [0,6,4,1] because the cycle A-B-C-D-A has dominating subsets AB, AC, AD, BC, BD, CD, ABC, ABD, ACD, BCD, and ABCD.
Triangle starts:
1;
2, 1;
3, 3,  1;
0, 6,  4,  1;
0, 5, 10,  5, 1;
0, 3, 14, 15, 6, 1;
...
From _Petros Hadjicostas_, Jan 27 2019: (Start)
Let n=6 and 1 <= k <= 6. Then T(n, k) is the number of (n-k)-combinations of the integers 1, 2, 3, 4, 5, 6 displaced on a circle with no K=3 consecutive integers (assuming 6 and 1 are consecutive). Equivalently, T(n, k) is the number of marked cyclic sequences consisting of n-k ones and k zeros with no K=3 consecutive ones.
For each k below we give the corresponding (n-k)-combinations and the equivalent marked sequences of 0's and 1's.
k=1, n-k = 5: none; T(n=6, k=1) = 0.
k=2, n-k = 4: 1245 <-> 110110, 2356 <-> 011011, 1346 <-> 101101; T(n=6, k=2) = 3.
k=3, n-k = 3: 124 <-> 110100, 125 <-> 110010, 134 <-> 101100, 135 <-> 101010, 136 <-> 101001, 145 <-> 100110, 146 <-> 100101, 235 <-> 011010, 236 <-> 011001, 245 <-> 010110, 246 <-> 010101, 256 <-> 010011, 346 <-> 001101, 356 <-> 001011; T(n=6, k=3) = 14.
k=4, n-k=2: all 2-combinations of the integers 1,2,3,4,5,6 and all marked cyclic sequences with exactly 2 ones and 4 zeros; hence, T(n=6, k=4) = binomial(6, 2) = 15.
k=5, n-k=1: all 1-combinations of the integers 1,2,3,4,5,6 and all marked cyclic sequences with exactly 1 one and 5 zeros; hence, T(n=6, k=5) = binomial(6, 1) = 6.
k=6, n-k=0: empty combination <-> 000000; T(n=6, k=6) = 1.
(End)

S. Alikhani and Y. H. Peng, Introduction to domination polynomial of a graph, arXiv:0905.2251 [math.CO], 2009.
S. Alikhani and Y. H. Peng, Dominating sets and domination polynomials of paths, International J. Math. and Math. Sci., Vol. 2009, Article ID542040.
S. Alikhani and Y. H. Peng, Dominating sets and domination polynomials of certain graphs, II, Opuscula Math., 30, No. 1, 2010, 37-51.
J. L. Arocha, B. Llano, The number of dominating k-sets of paths, cycles and wheels, arXiv preprint arXiv:1601.01268 [math.CO], 2016.
C. A. Charalambides, Lucas numbers and polynomials of order k and the length of the longest circular success run, The Fibonacci Quarterly, 29 (1991), 290-297.
W. O. J. Moser and M. Abramson, Enumeration of combinations with restricted differences and cospan, J. Combin. Theory, 7 (1969), 162-170.
Eric Weisstein's World of Mathematics, Cycle Graph
Eric Weisstein's World of Mathematics, Domination Polynomial

Cf. A001644, A125127, A284966, A322057.

Cf. A212635 (corresponding sequence for wheel graphs). - Eric W. Weisstein, Apr 06 2017

p := proc (n) if n = 1 then x elif n = 2 then x^2+2*x elif n = 3 then x^3+3*x^2+3*x else sort(expand(x*(p(n-1)+p(n-2)+p(n-3)))) end if end proc: for n to 15 do seq(coeff(p(n), x, k), k = 1 .. n) end do; # yields sequence in triangular form

CoefficientList[LinearRecurrence[{x, x, x}, {1, 2 + x, 3 + 3 x + x^2}, 10], x] // Flatten (* Eric W. Weisstein, Apr 06 2017 *)

If p(n)=p(n,x) denotes the generating polynomial of row n (called the domination polynomial of the cycle C_n), then p(1)=x, p(2) = 2x + x^2 , p(3) = 3x + 3x^2 + x^3 and p(n) = x*[p(n-1) + p(n-2) + p(n-3)] for n >= 4 (see Theorem 4.5 in the Alikhani & Peng reference in Opuscula Math.).
From Petros Hadjicostas, Jan 26 2019: (Start)
T(n, k) = binomial(n, k) for 1 <= k <= n and n = 1, 2.
T(n, k) = Sum_{j=0..floor(n/3)-1} (-1)^j*binomial(k, j)*(n/(n - 3*j))*binomial(n - 3*j, k) for n - floor(2*n/3) <= k <= n and n >= 3. (This is a special case of a corrected version of formula (2.1) in Charalambides (1991) and equation (14) in Moser and Abramson (1969).)
T(n, k) = 0 for 1 <= k < n - floor(2*n/3) and n >= 4. (Thus, the number of initial zeros in row n is n - floor(2*n/3) - 1.)
G.f. for row n: p(n, x) = -1 + Sum_{j=0..floor(n/4)} (-1)^j*(n/(n-3*j))*binomial(n - 3*j, j)*x^j*(1+x)^(n-4*j). It satisfies the recurrence given above (found in Alikhani and Peng (2010) and Charalambides (1991)).
(End)

A280303 Number of binary necklaces of length n with no subsequence 00000.

Original entry on oeis.org

1, 2, 3, 5, 7, 12, 17, 31, 51, 91, 155, 287, 505, 930, 1695, 3129, 5759, 10724, 19913, 37239, 69643, 130745, 245715, 463099, 873705, 1651838, 3126707, 5927817, 11251031, 21382558, 40679233, 77475673, 147694719, 281822847, 538213671, 1028714071, 1967728553

Offset: 1

Petros Hadjicostas and Lingyun Zhang, Dec 31 2016

nonn

a(n) is the number of cyclic sequences of length n consisting of zeros and ones that do not contain five consecutive zeros provided we consider as equivalent those sequences that are cyclic shifts of each other.

			a(5)=7 because we have seven binary cyclic sequences (necklaces) of length 5 that avoid five consecutive zeros: 00001, 00011, 00101, 00111, 01101, 01111, 11111.

Andrew Howroyd, Table of n, a(n) for n = 1..1000
P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
Petros Hadjicostas, Proof of the formula for the generating function from the formula for a(n)
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96.

Row 5 of A322057.

Cf. A000358, A093305, A280218, A074048.

a(n) = (1/n) * Sum_{d divides n} totient(n/d) * A074048(d).

G.f.: Sum_{k>=1} (phi(k)/k) * log(1/(1-B(x^k))) where B(x) = x*(1+x+x^2+x^3+x^4).

a(34) onwards from Andrew Howroyd, Jan 25 2024

cp's OEIS Frontend

A093305 Number of binary necklaces of length n with no subsequence 000.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A280218 Number of binary necklaces of length n with no subsequence 0000.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A212634 Triangle read by rows: T(n,k) is the number of dominating subsets with cardinality k of the cycle C_n (n >= 1, 1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A280303 Number of binary necklaces of length n with no subsequence 00000.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions