%I #37 Jan 03 2025 12:32:46
%S 1,0,6,20,81,324,1296,5184,20736,82944,331776,1327104,5308416,
%T 21233664,84934656,339738624,1358954496,5435817984,21743271936,
%U 86973087744,347892350976,1391569403904,5566277615616,22265110462464,89060441849856
%N Coefficient of q^n in (1-q)^4/(1-4q); dimensions of the enveloping algebra of the derived free Lie algebra on 4 letters.
%C 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
%C Also the number of monic polynomials of degree n over GF(4) without any linear factors. - _Greyson C. Wesley_, Jul 05 2022
%D 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.
%H Michael De Vlieger, <a href="/A118265/b118265.txt">Table of n, a(n) for n = 0..1661</a>
%H Nantel Bergeron, Christophe Reutenauer, Mercedes Rosas, and Mike Zabrocki, <a href="https://arxiv.org/abs/math/0502082">Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables</a>, arXiv:math.CO/0502082, 2005. See also <a href="https://doi.org/10.4153/CJM-2008-013-4 ">Canad. J. Math.</a> 60 (2008), no. 2, 266-296.
%H Joscha Diehl, Rosa Preiß, and Jeremy Reizenstein, <a href="https://arxiv.org/abs/2412.19670">Conjugation, loop and closure invariants of the iterated-integrals signature</a>, arXiv:2412.19670 [math.RA], 2024. See p. 21.
%H Milan Janjic, <a href="https://old.pmf.unibl.org/wp-content/uploads/2017/10/enumfun.pdf">Enumerative Formulas for Some Functions on Finite Sets</a>
%H <a href="/index/Rec#order_01">Index entries for linear recurrences with constant coefficients</a>, signature (4).
%F G.f.: (1-q)^4/(1-4q).
%F a(n) = Sum_{k=0..min(n,4)} (-1)^k*C(4,k)*4^(n-k).
%F a(n) = 81*4^(n-4) for n>3. - _Jean-François Alcover_, Dec 10 2018
%e 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.
%p f:=n->add((-1)^k*C(4,k)*4^(n-k),k=0..min(n,4)); seq(f(i),i=0..15);
%t a[n_] := If[n<4, {1, 0, 6, 20}[[n+1]], 81*4^(n-4)];
%t Table[a[n], {n, 0, 24}] (* _Jean-François Alcover_, Dec 10 2018 *)
%Y Cf. A027377, A118264, A118266.
%K nonn
%O 0,3
%A _Mike Zabrocki_, Apr 20 2006