A027377 -id:A027377 - cp's OEIS frontend

A005377 Number of low discrepancy sequences in base 4.

0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94, 97, 100, 103, 106, 109, 112, 115, 118, 121, 124, 127, 130, 133, 136, 139

Offset: 1

N. J. A. Sloane, Simon Plouffe

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Harald Niederreiter, Low-discrepancy and low-dispersion sequences, J. Number Theory 30 (1988), no. 1, 51-70.

Cf. A005356 (base 2), A005357 (base 3), A005358 (base 5), A274039 (Plouffe's g.f.)

Cf. A001037 (N(2,n)), A027376 (N(3,n)), A027377 (N(4,n)), A062692 (M(2,n)), A114945 (M(3,n)), A114946 (M(4,n)).

N := proc(b,n)
    option remember;
    local d;
    add(b^d*numtheory[mobius](n/d),d=numtheory[divisors](n)) ;
    %/n ;
end proc:
M := proc(b,n)
    local h;
    if n = 0 then
        0;
    else
        add(N(b,h),h=1..n) ;
    end if;
end proc:
nMax := proc(b,s)
    local n;
    for n from 0 do
        if M(b,n) > s then
            return n-1 ;
        end if;
    end do:
end proc:
A005377 := proc(s)
    local n,b;
    b := 4 ;
    n := nMax(b,s) ;
    n*(s-M(b,n))+add( (h-1)*N(b,h),h=1..n) ;
end proc:
seq(A005377(n),n=1..40) ; # R. J. Mathar, Jun 09 2016

Np[b_, n_] := Np[b, n] = Sum[b^d*MoebiusMu[n/d], {d, Divisors[n]}]/n;
M[b_, n_] := If[n == 0, 0, Sum[Np[b, h], {h, 1, n}]];
nMax[b_, s_] := Module[{n}, For[n = 0, True, n++, If[M[b, n] > s, Return[n - 1]]]];
a[s_] := Module[{n, b}, b = 4; n = nMax[b, s]; n*(s - M[b, n]) + Sum[(h - 1)*Np[b, h], {h, 1, n}]];
Table[a[n], {n, 1, 61}] (* Jean-François Alcover, Sep 12 2023, after R. J. Mathar *)

Let N(b,n) = (1/n) * Sum_{d|n} mobius(n/d) * b^d. Let M(b,n) = Sum_{k=1..n} N(b,k) with M(b,0) = 0. Let r = r(b,n) be the largest value r such that M(b,r) <= n. Then a(n) = r * (n - M(4, r)) + Sum_{h=1..r} (h-1) * N(4, h) [From Niederreiter paper]. - Sean A. Irvine, Jun 07 2016

G.f.: z^4 * (z^2+1) * (z^4-z^2+1) / (z-1)^2; [Conjectured by Simon Plouffe in his 1992 dissertation, but is incorrect.]

Terms, offset, and formula corrected by Sean A. Irvine, Jun 07 2016

A056289 Number of primitive (period n) n-bead necklaces with exactly four different colored beads.

Original entry on oeis.org

0, 0, 0, 6, 48, 260, 1200, 5100, 20720, 81828, 318000, 1222870, 4675440, 17813820, 67769504, 257695800, 980240880, 3731732200, 14222737200, 54278498154, 207438936800, 793940157900, 3043140078000, 11681056021300, 44900438149248, 172824327151140, 666070256468960

Offset: 1

Marks R. Nester

nonn

Turning over the necklace is not allowed.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Cf. A027377.

Column k=4 of A254040.

with(numtheory):
b:= proc(n, k) option remember; `if`(n=0, 1,
      add(mobius(n/d)*k^d, d=divisors(n))/n)
    end:
a:= n-> add(b(n, 4-j)*binomial(4, j)*(-1)^j, j=0..4):
seq(a(n), n=1..30);  # Alois P. Heinz, Jan 25 2015

b[n_, k_] := b[n, k] = If[n==0, 1, DivisorSum[n, MoebiusMu[n/#]*k^#&]/n]; a[n_] := Sum[b[n, 4-j]*Binomial[4, j]*(-1)^j, {j, 0, 4}]; Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Feb 20 2017, after Alois P. Heinz *)

a(n) = Sum_{d|n} mu(d)*A056284(n/d).

A056300 Number of primitive (period n) n-bead necklace structures using a maximum of four different colored beads.

Original entry on oeis.org

1, 1, 2, 5, 10, 35, 102, 360, 1232, 4427, 15934, 58465, 215250, 799593, 2983204, 11187200, 42109450, 159081482, 602809326, 2290679807, 8726308212, 33318645341, 127479700198, 488672244040, 1876500180280

Offset: 1

Marks R. Nester

nonn

Turning over the necklace is not allowed. Colors may be permuted without changing the necklace structure.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Cf. A008683, A027377, A056292.

a(n) = Sum_{d|n} mu(d) * A056292(n/d); mu = A008683.

A118265 Coefficient of q^n in (1-q)^4/(1-4q); dimensions of the enveloping algebra of the derived free Lie algebra on 4 letters.

Original entry on oeis.org

1, 0, 6, 20, 81, 324, 1296, 5184, 20736, 82944, 331776, 1327104, 5308416, 21233664, 84934656, 339738624, 1358954496, 5435817984, 21743271936, 86973087744, 347892350976, 1391569403904, 5566277615616, 22265110462464, 89060441849856

Offset: 0

Mike Zabrocki, Apr 20 2006

nonn

For n>=4, a(n) is equal to the number of functions f:{1,2,...,n}->{1,2,3,4} such that for fixed, different x_1, x_2, x_3, x_4 in {1,2,...,n} and fixed y_1, y_2, y_3, y_ 4 in {1,2,3,4} we have f(x_i)<>y_i, (i=1,2,3,4). - Milan Janjic, May 13 2007

Also the number of monic polynomials of degree n over GF(4) without any linear factors. - Greyson C. Wesley, Jul 05 2022

			The enveloping algebra of the derived free Lie algebra is characterized as the intersection of the kernels of all partial derivative operators in the space of non-commutative polynomials, a(0) = 1 since all constants are killed by derivatives, a(1) = 0 since no polys of degree 1 are killed, a(2) = 6 since all Lie brackets [x1,x2], [x1,x3], [x1, x4], [x2,x3], [x2,x4], [x3,x4] are killed by all derivative operators.

C. Reutenauer, Free Lie algebras. London Mathematical Society Monographs. New Series, 7. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1993. xviii+269 pp.

Michael De Vlieger, Table of n, a(n) for n = 0..1661
Nantel Bergeron, Christophe Reutenauer, Mercedes Rosas, and Mike Zabrocki, Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables, arXiv:math.CO/0502082, 2005. See also Canad. J. Math. 60 (2008), no. 2, 266-296.
Joscha Diehl, Rosa Preiß, and Jeremy Reizenstein, Conjugation, loop and closure invariants of the iterated-integrals signature, arXiv:2412.19670 [math.RA], 2024. See p. 21.
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets
Index entries for linear recurrences with constant coefficients, signature (4).

Cf. A027377, A118264, A118266.

f:=n->add((-1)^k*C(4,k)*4^(n-k),k=0..min(n,4)); seq(f(i),i=0..15);

a[n_] := If[n<4, {1, 0, 6, 20}[[n+1]], 81*4^(n-4)];
Table[a[n], {n, 0, 24}] (* Jean-François Alcover, Dec 10 2018 *)

G.f.: (1-q)^4/(1-4q).
a(n) = Sum_{k=0..min(n,4)} (-1)^k*C(4,k)*4^(n-k).
a(n) = 81*4^(n-4) for n>3. - Jean-François Alcover, Dec 10 2018

A006169 Number of factorization patterns of polynomials of degree n over F_4.

Original entry on oeis.org

1, 3, 5, 11, 16, 32, 47, 84, 124, 206, 299, 481, 687, 1058, 1506, 2255, 3163, 4638, 6444, 9258, 12757, 18021, 24604, 34307, 46445, 63926, 85948, 117021, 156156, 210617, 279202, 373252, 491801, 652264, 854343, 1125152, 1465587, 1917282, 2484733

Offset: 1

N. J. A. Sloane

nonn

R. A. Hultquist, G. L. Mullen and H. Niederreiter, Association schemes and derived PBIB designs of prime power order, Ars. Combin., 25 (1988), 65-82.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=1..1000
R. A. Hultquist, G. L. Mullen and H. Niederreiter, Association schemes and derived PBIB designs of prime power order, Ars. Combin., 25 (1988), 65-82. (Annotated scanned copy)

Cf. A006167-A006171.

Cf. A027377.

Euler transform of sequence b(n) = sum_{d|n, A027377(d)>=n/d} 1. - Franklin T. Adams-Watters, Jun 19 2006

More terms from Franklin T. Adams-Watters, Jun 19 2006

A185172 Dimensions of primitive Lie algebras connected with the Mantaci-Reutenauer algebra MR^(3).

Original entry on oeis.org

3, 6, 20, 60, 204, 670, 2340, 8160, 29120, 104754, 381300, 1397740, 5162220, 19172790, 71582716, 268431360, 1010580540, 3817733920, 14467258260, 54975528948, 209430785460, 799644629550, 3059510616420, 11728123327840, 45035996273664, 173215367702370

Offset: 1

N. J. A. Sloane, Jan 23 2012

Maybe the definition should say: "Number of generators of degree n ...". The paper is a little unclear.
From Petros Hadjicostas, Jun 18 2019: (Start)
An unmarked cyclic composition of n >= 1 is an equivalence class of ordered partitions of n such that two such ordered partitions are equivalent iff one can be obtained from the other by rotation.
Here, a(n) is the number of aperiodic unmarked cyclic compositions of n where up to three colors can be used.
It is also the CHK (circular, identity, unlabeled) transform of the sequence 3, 3, 3, ... See the link by Bowers about such transforms.
If c = (c(n): n >= 1) is the input sequence with g.f. C(x) = Sum_{n >= 1} c(n)*x^n, then the g.f. of the output sequence ((CHK c)d: d >= 1) is -Sum{d >= 1} (mu(d)/d) * log(1 - C(x^d)). Here, c(n) = 3 for all n >= 1, and thus, C(x) = 3*x/(1 - x). It follows that the g.f. of the output sequence is -Sum_{d >= 1} (mu(d)/d) * log(1 - 3*x^d/(1 - x^d)).
(End)

			From _Petros Hadjicostas_, Jun 18 2019: (Start)
Suppose we have three colors, say, A, B, C. Here, a(1) = 3 because we have the following aperiodic unmarked cyclic compositions of n = 1: 1_A, 1_B, 1_C.
We have a(2) = 6 because we have the following aperiodic unmarked cyclic compositions of n = 2: 2_A, 2_B, 2_C, 1_A + 1_B, 1_B + 1_C, 1_C + 1_A.
We have a(3) = 20 because we have the following aperiodic unmarked cyclic compositions of n = 3: 3_X, where X \in {A, B, C}; 1_X + 2_Y, where (X, Y) \in {(A, A), (A, B), (A, C), (B, A), (B, B), (B, C), (C, A), (C, B), (C, C)}; 1_A + 1_B + 1_C and 1_C + 1_B + 1_A; and 1_X + 1_Y + 1_Y, where (X, Y) \in {(A, B), (A, C), (B, A), (B, C), (C, A), (C, B)}.
(End)

G. C. Greubel, Table of n, a(n) for n = 1..1650
C. G. Bower, Transforms (2).
Jean-Christophe Novelli and Jean-Yves Thibon, Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions, arXiv:0806.3682 [math.CO], 2008. See Eqs. (94) and (95).
Jean-Christophe Novelli and Jean-Yves Thibon, Free quasi-symmetric functions and descent algebras for wreath products, and noncommutative multi-symmetric functions, Discrete Math. 310 (2010), no. 24, 3584-3606. See Eqs. (99) and (100).

Cf. A024036, A032253, A185171.

Essentially the same as A027377.

a[1] = 3; a[n_] := DivisorSum[n, MoebiusMu[#]*4^(n/#)&]/n; Array[a, 26] (* Jean-François Alcover, Dec 07 2015, adapted from PARI *)

a(l=3,n) = if (n==1, l, sumdiv(n, d, moebius(d)*(1+l)^(n/d))/n);  \\ Michel Marcus, Feb 09 2013

From Petros Hadjicostas, Jun 17 2019: (Start)
a(1) = 3 and a(n) = (1/n) * Sum_{d|n} mu(d) * 4^(n/d) for n > 1 (from Eq. (95) in Novelli and Thibon (2008) or Eq. (100) in Novelli and Thibon (2010)).
a(n) = (1/n) * Sum_{d|n} mu(d) * (4^(n/d) - 1) = (1/n) * Sum_{d|n} mu(d) *A024036(n/d) for n >= 1.
G.f.: -Sum_{d >= 1} (mu(d)/d) * log(1 - 3*x^d/(1 - x^d)) = -x - Sum_{d >= 1} (mu(d)/d) * log(1 - 4*x^d).
(End)

More terms from Michel Marcus, Feb 09 2013

Name edited by Petros Hadjicostas, Jun 17 2019

A114946 Number of monic irreducible polynomials over GF(4) of degree <= n.

Original entry on oeis.org

4, 10, 30, 90, 294, 964, 3304, 11464, 40584, 145338, 526638, 1924378, 7086598, 26259388, 97842104, 366273464, 1376854004, 5194587924, 19661846184, 74637375132, 284068160592, 1083712790142, 4143223406562, 15871346734402, 60907343008066, 234122710710436

Offset: 1

Gary L Mullen (mullen(AT)math.psu.edu) and Ken Hicks, Jan 06 2006

nonn

Partial sums of A027377. 4th column of A143328. - Alois P. Heinz, Sep 23 2008

with(numtheory):
b:= n-> add(mobius(d) *4^(n/d)/n, d=divisors(n)):
a:= n-> add(b(k), k=1..n):
seq(a(n), n=1..30); # Alois P. Heinz, Sep 23 2008

f[n_] := DivisorSum[n, MoebiusMu[#] * 4^(n/#) &] / n; Accumulate[Array[f, 26]] (* Amiram Eldar, Aug 24 2023 *)

a(n)=sum(m=1, n, 1/m* sumdiv(m, d, moebius(d)*4^(m/d) ) ); /* Joerg Arndt, Jul 04 2011 */

More terms from Alois P. Heinz, Sep 23 2008

A210424 Number of 2-divided words of length n over a 4-letter alphabet.

Original entry on oeis.org

0, 0, 6, 40, 186, 816, 3396, 14040, 57306, 233000, 943608, 3813000, 15378716, 61946640, 249260316, 1002158880, 4026527706, 16169288640, 64901712996, 260410648680, 1044535993800, 4188615723280, 16792541033556, 67309233561240, 269746851976156

Offset: 1

N. J. A. Sloane, Mar 21 2012

See A210109 for further information.
It appears that A027377 gives the number of 2-divided words that have a unique division into two parts. - David Scambler, Mar 21 2012
From R. J. Mathar, Mar 25 2012: (Start)
Row sums of the following table which shows how many words of length n over a 4-letter alphabet are 2-divided in k>=1 different ways:
  6;
  20, 20;
  60, 66, 60;
  204, 204, 204, 204;
  670, 690, 676, 690, 670;
  2340, 2340, 2340, 2340, 2340, 2340;
  8160, 8220, 8160, 8226, 8160, 8220, 8160;
First column of the following triangle which shows how many words of length n over a 4-letter alphabet are k-divided:
  6;
  40, 4;
  186, 60, 1;
  816, 374, 44, 0;
  3396, 1960, 450, 12, 0;
  14040, 9103, 3175, 275, 0, 0;
  57306, 40497, 17977, 2915, 66, 0, 0;
  233000, 174127, 91326, 22243, 1318,..
(End)

Cf. A210109, A209970, A001868.

a(n) = 4^n - A001868(n) (see A209970 for proof).

a(1)-a(10) computed by R. J. Mathar, Mar 20 2012

a(13) onwards from N. J. A. Sloane, Mar 21 2012

A295521 a(n) = (1/n) * Sum_{d|n} mu(n/d)*(4^d - 3^d - 2^d + 1).

Original entry on oeis.org

0, 2, 10, 39, 150, 545, 2010, 7320, 26880, 98775, 365010, 1353185, 5038950, 18830145, 70623958, 265737270, 1002976350, 3796197160, 14406059010, 54801140307, 208932573650, 798218035245, 3055417070010, 11716354754030, 45002103387120, 173117601112575

Offset: 1

Seiichi Manyama, Nov 23 2017

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..1666
Wikipedia, Möbius function

Cf. A001037, A008683, A020988, A027376, A027377.

a[n_] := DivisorSum[n, MoebiusMu[n/#] * (4^# - 3^# - 2^# + 1) &] / n; Array[a, 26] (* Amiram Eldar, Oct 04 2023 *)

{a(n) = sumdiv(n, d, moebius(n/d)*(4^d-3^d-2^d+1))/n}

a(n) = A027377(n) - A027376(n) - A001037(n) for n > 1.

A349002 The number of Lyndon words of size n from an alphabet of 4 letters and 1st, 2nd and 3rd letter of the alphabet with equal frequency in the words.

Original entry on oeis.org

1, 1, 0, 2, 6, 12, 34, 120, 354, 1082, 3636, 12270, 40708, 139062, 484866, 1692268, 5944470, 21134808, 75625330, 271720146, 982116648, 3569558058, 13025614962, 47714385708, 175470892468, 647508620070, 2396613522804, 8896422981608, 33114570409896, 123566641829256

Offset: 0

R. J. Mathar, Nov 05 2021

nonn

Counts a subset of the Lyndon words in A027377. Here there is no requirement of how often the 4th letter of the alphabet occurs in the admitted word, only on the frequency of the 1st to 3rd letter of the alphabet.

			Examples for the alphabet {0,1,2,3}:
a(0)=1 counts (), the empty word.
a(3)=2 counts (021) (012).
a(4)=6 counts (0321) (0231) (0312) (0132) (0213) (0123).
a(5)=12 counts (03321) (03231) (02331) (03312) (03132) (01332) (03213) (02313) (03123) (01323) (02133) (01233).
a(6)=34 counts (020211) (002211) (012021) (002121) (010221) (001221) (033321) (033231) (032331) (023331) (012102) (011202) (002112) (010212) (001212) (033312) (011022) (010122) (001122) (033132) (031332) (013332) (033213) (032313) (023313) (033123) (031323) (013323) (032133) (023133) (031233) (013233) (021333) (012333).

Index entries for sequences related to Lyndon words

Cf. A027377, A060165, A344560.

a(n) = if(n>0, sumdiv(n, d, moebius(n/d)*sum(k=0, d\3, d!/(k!^3*(d-3*k)!)))/n, n==0) \\ Andrew Howroyd, Jan 14 2023

n*a(n) = Sum_{d|n} mu(d)*A344560(n/d) where mu = A008683.

Terms corrected and extended by Andrew Howroyd, Jan 14 2023

cp's OEIS Frontend

A005377 Number of low discrepancy sequences in base 4.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A056289 Number of primitive (period n) n-bead necklaces with exactly four different colored beads.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A056300 Number of primitive (period n) n-bead necklace structures using a maximum of four different colored beads.

Views

Author

Keywords

Comments

References

Crossrefs

Formula

A118265 Coefficient of q^n in (1-q)^4/(1-4q); dimensions of the enveloping algebra of the derived free Lie algebra on 4 letters.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A006169 Number of factorization patterns of polynomials of degree n over F_4.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A185172 Dimensions of primitive Lie algebras connected with the Mantaci-Reutenauer algebra MR^(3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A114946 Number of monic irreducible polynomials over GF(4) of degree <= n.

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A210424 Number of 2-divided words of length n over a 4-letter alphabet.

Views