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.

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

Author

Mike Zabrocki, Apr 20 2006

Keywords

• nonn

Comments

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

Examples

			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.
		

References

• 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.

Links

• 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).

Crossrefs

Cf. A027377, A118264, A118266.

Programs

Maple

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

Mathematica

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 *)

Formula

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