A045630 -id:A045630 - cp's OEIS frontend

A022553 Number of binary Lyndon words containing n letters of each type; periodic binary sequences of period 2n with n zeros and n ones in each period.

1, 1, 1, 3, 8, 25, 75, 245, 800, 2700, 9225, 32065, 112632, 400023, 1432613, 5170575, 18783360, 68635477, 252085716, 930138521, 3446158600, 12815663595, 47820414961, 178987624513, 671825020128, 2528212128750, 9536894664375, 36054433807398, 136583760011496

Offset: 0

David Broadhurst

Also number of asymmetric rooted plane trees with n+1 nodes. - Christian G. Bower
Conjecturally, number of irreducible alternating Euler sums of depth n and weight 3n.
a(n+1) is inverse Euler transform of A000108. Inverse Witt transform of A006177.
Dimension of the degree n part of the primitive Lie algebra of the Hopf algebra CQSym (Catalan Quasi-Symmetric functions). - Jean-Yves Thibon (jyt(AT)univ-mlv.fr), Oct 22 2006
For n>0, 2*a(n) is divisible by n (cf. A268619), 12*a(n) is divisible by n^2 (cf. A268592). - Max Alekseyev, Feb 09 2016

			a(3)=3 counts 6-periodic 000111, 001011 and 001101. a(4)=8 counts 00001111, 00010111, 00011011, 00011101, 00100111, 00101011, 00101101, and 00110101. - _R. J. Mathar_, Oct 20 2021

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 336 (4.4.64)

Alois P. Heinz, Table of n, a(n) for n = 0..1000
M. J. H. Al-Kaabi, Monomial Bases for Free Post-Lie Algebras, IOP Conf. Ser.: Mater. Sci. Eng. (2020) Vol. 871, 012048.
Nicolas Andrews, Lucas Gagnon, Félix Gélinas, Eric Schlums, and Mike Zabrocki, When are Hopf algebras determined by integer sequences?, arXiv:2505.06941 [math.CO], 2025. See pp. 3, 6.
David J. Broadhurst, On the enumeration of irreducible k-fold Euler sums and their roles in knot theory and field theory, arXiv:hep-th/9604128, 1996.
Gilbert Labelle and Pierre Leroux, Enumeration of (uni- or bicolored) plane trees according to their degree distribution, Disc. Math. 157 (1996) 227-240, Eq. (1.20).
Hans Munthe-Kaas and Alexander Lundervold, On post-Lie algebras, Lie-Butcher series and moving frames, arXiv preprint arXiv:1203.4738 [math.NA], 2012. - From _N. J. A. Sloane_, Sep 20 2012
Jean-Christophe Novelli and Jean-Yves Thibon, Hopf algebras and dendriform structures arising from parking functions, arXiv:math/0511200 [math.CO], 2005.
Tilman Piesk, List of 2n-bead balanced binary Lyndon words for n=1...8
Yash Puri and Thomas Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
Index entries for sequences related to rooted trees
Index entries for sequences related to Lyndon words

Cf. A003239, A005354, A000740, A007727, A086655, A289978 (multiset trans.), A001037 (binary Lyndon wds.), A074655 (3 letters), A074656 (4 letters).

A diagonal of the square array described in A051168.

with(numtheory):
a:= n-> `if`(n=0, 1,
        add(mobius(n/d)*binomial(2*d, d), d=divisors(n))/(2*n)):
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 21 2011

a[n_] := Sum[MoebiusMu[n/d]*Binomial[2d, d], {d, Divisors[n]}]/(2n); a[0] = 1; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 02 2015 *)

a(n)=if(n<1,n==0,sumdiv(n,d,moebius(n/d)*binomial(2*d,d))/2/n)

from sympy import mobius, binomial, divisors
def a(n):
    return 1 if n == 0 else sum(mobius(n//d)*binomial(2*d, d) for d in divisors(n))//(2*n)
print([a(n) for n in range(31)]) # Indranil Ghosh, Aug 05 2017

def a(n):
    return 1 if n ==0 else sum(moebius(n//d)*binomial(2*d, d) for d in divisors(n))//(2*n)
# F. Chapoton, Apr 23 2020

a(n) = A060165(n)/2 = A007727(n)/(2*n) = A045630(n)/n.
Product_n (1-x^n)^a(n) = 2/(1+sqrt(1-4*x));  a(n) = 1/(2*n) * Sum_{d|n} mu(n/d)*C(2*d,d). Also Moebius transform of A003239. - Christian G. Bower
a(n) ~ 2^(2*n-1) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Sep 11 2014
G.f.: 1 + Sum_{k>=1} mu(k)*log((1 - sqrt(1 - 4*x^k))/(2*x^k))/k. - Ilya Gutkovskiy, May 18 2019

A007727 Number of 2n-bead black-white strings with n black beads and fundamental period 2n.

Original entry on oeis.org

1, 2, 4, 18, 64, 250, 900, 3430, 12800, 48600, 184500, 705430, 2703168, 10400598, 40113164, 155117250, 601067520, 2333606218, 9075085776, 35345263798, 137846344000, 538257870990, 2104098258284, 8233430727598, 32247600966144

Offset: 0

Doug Bowman, bowman(AT)math.uiuc.edu

nonn

For n>0, a(n) is divisible by n^2 (cf. A268619) and 6*a(n) is divisible by n^3 (cf. A268592). - Max Alekseyev, Feb 07 2016

Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.

Cf. A045630, A060165, A022553.

A007727 := proc(n)
    if n = 0 then
        1;
    else
        add(numtheory[mobius](n/d)*binomial(2*d,d), d =numtheory[divisors](n)) ;
    end if ;
end proc:
seq(A007727(n),n=0..10) ; # R. J. Mathar, Nov 10 2021

a[n_] := If[n == 0, 1, Sum[MoebiusMu[n/d] Binomial[2d, d], {d, Divisors[n]}]];
Table[a[n], {n, 0, 24}] (* Jean-François Alcover, May 05 2023 *)

{ a(n) = if(n>0,sumdiv(n, d, moebius(n/d)*binomial(2*d, d)),0); }

For n>0, a(n) = Sum_{d|n} A008683(n/d)*A000984(d).
For n>0, a(n) = 2 * A045630(n).
a(0)=1, a(n) = n * A060165(n) = 2n * A022553(n). - Ralf Stephan, Sep 01 2003

Edited by Max Alekseyev, Feb 09 2016

A268592 a(n) = (6/n^3) * Sum_{d|n} moebius(n/d)binomial(2d,d).

Original entry on oeis.org

12, 3, 4, 6, 12, 25, 60, 150, 400, 1107, 3180, 9386, 28404, 87711, 275764, 880470, 2849916, 9336508, 30918732, 103384758, 348725540, 1185630123, 4060210764, 13996354586, 48541672872, 169293988125, 593488622344, 2090567755278, 7396924802052, 26281018091013, 93738717046476, 335563502259798

Offset: 1

Max Alekseyev, Feb 07 2016

nonn

G. C. Greubel, Table of n, a(n) for n = 1..1500
R. R. Aidagulov, M. A. Alekseyev. On p-adic approximation of sums of binomial coefficients. Journal of Mathematical Sciences 233:5 (2018), 626-634. doi:10.1007/s10958-018-3948-0 arXiv:1602.02632

Cf. A254593, A268618, A268619.

a[n_] := (6/n^3)* DivisorSum[n, MoebiusMu[n/#] Binomial[2 #, #] &]; Array[a, 50] (* G. C. Greubel, Dec 15 2017 *)

{ a(n) = sumdiv(n, d, moebius(n/d)*binomial(2*d, d))*6/n^3; }

a(n) = A007727(n)*6/n^3 = A045630(n)*12/n^3 = A060165(n)*6/n^2 = A022553(n)*12/n^2 = A268619(n)*6/n.

For n == 0, 1, or 3 (mod 4), a(n) = 2*A254593(n); for n == 2 (mod 4), a(n) = 2*A254593(n) - A254593(n/2)/2.

A268619 a(n) = (1/n^2) * Sum_{d|n} moebius(n/d)binomial(2d,d).

Original entry on oeis.org

2, 1, 2, 4, 10, 25, 70, 200, 600, 1845, 5830, 18772, 61542, 204659, 689410, 2347920, 8074762, 28009524, 97909318, 344615860, 1220539390, 4347310451, 15564141262, 55985418344, 202256970300, 733607281875, 2670698800548, 9755982857964, 35751803209918, 131405090455065, 484316704740126, 1789672012052256

Offset: 1

Max Alekseyev, Feb 09 2016

nonn

6*a(n) is divisible by n (cf. A268592).

Cf. A000984, A007727, A008683, A022553, A045630, A060165, A268592, A268617.

a[n_] := DivisorSum[n, MoebiusMu[n/#] * Binomial[2*#, #] &] / n^2; Array[a, 35] (* Amiram Eldar, Aug 24 2023 *)

{ a(n) = sumdiv(n, d, moebius(n/d)*binomial(2*d, d))/n^2; }

a(n) = (1/n^2)* Sum_{d|n} A008683(n/d)*A000984(d).

a(n) = A007727(n)/n^2 = A045630(n)*2/n^2 = A060165(n)/n = A022553(n)*2/n.

A333941 Triangle read by rows where T(n,k) is the number of compositions of n with rotational period k.

Original entry on oeis.org

1, 0, 1, 0, 2, 0, 0, 2, 2, 0, 0, 3, 2, 3, 0, 0, 2, 4, 6, 4, 0, 0, 4, 6, 9, 8, 5, 0, 0, 2, 6, 15, 20, 15, 6, 0, 0, 4, 8, 24, 32, 35, 18, 7, 0, 0, 3, 10, 27, 56, 70, 54, 28, 8, 0, 0, 4, 12, 42, 84, 125, 120, 84, 32, 9, 0, 0, 2, 10, 45, 120, 210, 252, 210, 120, 45, 10, 0

Offset: 0

Gus Wiseman, Apr 16 2020

A composition of n is a finite sequence of positive integers summing to n.

			Triangle begins:
   1
   0   1
   0   2   0
   0   2   2   0
   0   3   2   3   0
   0   2   4   6   4   0
   0   4   6   9   8   5   0
   0   2   6  15  20  15   6   0
   0   4   8  24  32  35  18   7   0
   0   3  10  27  56  70  54  28   8   0
   0   4  12  42  84 125 120  84  32   9   0
   0   2  10  45 120 210 252 210 120  45  10   0
   0   6  18  66 168 335 450 462 320 162  50  11   0
Row n = 6 counts the following compositions (empty columns indicated by dots):
  .  (6)       (15)    (114)  (1113)  (11112)  .
     (33)      (24)    (123)  (1122)  (11121)
     (222)     (42)    (132)  (1131)  (11211)
     (111111)  (51)    (141)  (1221)  (12111)
               (1212)  (213)  (1311)  (21111)
               (2121)  (231)  (2112)
                       (312)  (2211)
                       (321)  (3111)
                       (411)

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

Column k = 1 is A000005.
Row sums are A011782.
Diagonal T(2n,n) is A045630(n).
The strict version is A072574.
A version counting runs is A238279.
Column k = n - 1 is A254667.
Aperiodic compositions are counted by A000740.
Aperiodic binary words are counted by A027375.
The orderless period of prime indices is A052409.
Numbers whose binary expansion is periodic are A121016.
Periodic compositions are counted by A178472.
Period of binary expansion is A302291.
Numbers whose prime signature is aperiodic are A329139.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Rotational symmetries are counted by A138904.
- Constant compositions are A272919.
- Lyndon compositions are A275692.
- Co-Lyndon compositions are A326774.
- Aperiodic compositions are A328594.
- Rotational period is A333632.
- Co-necklaces are A333764.
- Reversed necklaces are A333943.
Cf. A000031, A001037, A008965, A019536, A211100, A291166, A328595, A328596, A329312, A329313, A329326.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Function[c,Length[Union[Array[RotateRight[c,#]&,Length[c]]]]==k]]],{n,0,10},{k,0,n}]

T(n,k)=if(n==0, k==0, sumdiv(n, m, sumdiv(gcd(k,m), d, moebius(d)*binomial(m/d-1, k/d-1)))) \\ Andrew Howroyd, Jan 19 2023

T(n,k) = Sum_{m|n} Sum_{d|gcd(k,m)} mu(d)*binomial(m/d-1, k/d-1) for n > 0. - Andrew Howroyd, Jan 19 2023

A081875 a(n) = Sum_{d|n} phi(n/d)C(2d,d)/2.

Original entry on oeis.org

1, 4, 12, 40, 130, 480, 1722, 6480, 24336, 92520, 352726, 1352640, 5200312, 20060040, 77559060, 300546720, 1166803126, 4537592928, 17672631918, 68923357200, 269128940724, 1052049834616, 4116715363822, 16123803207552

Offset: 1

Wouter Meeussen, Apr 12 2003

			G.f. = x + 4*x^2 + 12*x^3 + 40*x^4 + 130*x^5 + 480*x^6 + 1722*x^7 + ...

Robert Israel, Table of n, a(n) for n = 1..1656
V. A. Liskovets, Enumerative formulas for unrooted planar maps: a pattern, Electron. J. Combin., 11:1 (2004), R88.
J. Malenfant, On the Matrix-Element Expansion of a Circulant Determinant, arXiv preprint arXiv:1502.06012 [math.NT], 2015.

Cf. A000010, A045630, A088218.

f:= proc(n) local d; add(numtheory:-phi(n/d)*binomial(2*d,d)/2, d = numtheory:-divisors(n)) end proc:
map(f, [$1..30]); # Robert Israel, Nov 29 2024

Table[Fold[ #1+EulerPhi[n/#2]*Binomial[2#2, #2]/2&, 0, Divisors[n]], {n, 1, 32}]
a[ n_] := If[ n < 0, 0, Sum[ Binomial[2 d, d] EulerPhi[n / d], {d, Divisors @ n}] / 2]; (* Michael Somos, Nov 01 2014 *)

{a(n) = if( n<1, 0, sumdiv(n, d, binomial(2*d, d) * eulerphi(n/d)) / 2)}; /* Michael Somos, Nov 01 2014 */

Dirichlet convolution of A000010 and A088218. - R. J. Mathar, Mar 11 2017
a(n) ~ 2^(2*n-1) / sqrt(Pi*n). - Vaclav Kotesovec, Jun 08 2019
From Richard L. Ollerton, May 07 2021: (Start)
a(n) = Sum_{k=1..n} C(2*gcd(n,k),gcd(n,k))/2.
a(n) = Sum_{k=1..n} A088218(gcd(n,k)). (End)

A382503 a(n) = Sum_{d|n} binomial(2*d-1,d).

Original entry on oeis.org

1, 4, 11, 39, 127, 476, 1717, 6474, 24321, 92508, 352717, 1352589, 5200301, 20060020, 77558897, 300546669, 1166803111, 4537592436, 17672631901, 68923356953, 269128938947, 1052049834580, 4116715363801, 16123803200574, 63205303219003, 247959271674356

Offset: 1

Ilya Gutkovskiy, Apr 10 2025

nonn

Cf. A000005, A000984, A001700, A045630, A072929, A088218.

Table[Sum[Binomial[2 d - 1, d], {d, Divisors[n]}], {n, 1, 26}]
nmax = 26; CoefficientList[Series[Sum[Binomial[2 k - 1, k] x^k/(1 - x^k), {k, 1, nmax}], {x, 0, nmax}], x] // Rest

a(n) = sumdiv(n, d, binomial(2*d-1,d)); \\ Michel Marcus, Apr 17 2025

G.f.: Sum_{k>=1} binomial(2*k-1,k) * x^k / (1 - x^k).
a(n) = [(x*y)^n] Sum_{k>=1} x^k / (1 - x^k - y^k).
a(n) = Sum_{d|n} A088218(d).
a(n) = Sum_{d|n} A001700(d-1).
a(n) = Sum_{d|n} A045630(d) * A000005(n/d).
a(n) = A072929(n) / 2.

cp's OEIS Frontend

A022553 Number of binary Lyndon words containing n letters of each type; periodic binary sequences of period 2n with n zeros and n ones in each period.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Sage

Formula

A007727 Number of 2n-bead black-white strings with n black beads and fundamental period 2n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A268592 a(n) = (6/n^3) * Sum_{d|n} moebius(n/d)*binomial(2*d,d).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A268619 a(n) = (1/n^2) * Sum_{d|n} moebius(n/d)*binomial(2*d,d).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Formula

A333941 Triangle read by rows where T(n,k) is the number of compositions of n with rotational period k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A081875 a(n) = Sum_{d|n} phi(n/d)*C(2*d,d)/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A382503 a(n) = Sum_{d|n} binomial(2*d-1,d).

Views

Author

Keywords

Crossrefs

Programs

A268592 a(n) = (6/n^3) * Sum_{d|n} moebius(n/d)binomial(2d,d).

A268619 a(n) = (1/n^2) * Sum_{d|n} moebius(n/d)binomial(2d,d).

A081875 a(n) = Sum_{d|n} phi(n/d)C(2d,d)/2.