OFFSET
1,2
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
T. D. Noe, Table of n, a(n) for n = 1..500
J. A. Green, The characters of the finite general linear groups, Trans. Amer. Math. Soc., 80 (1955), 402-447.
N. J. A. Sloane, Transforms.
R. Steinberg, A geometric approach to the representations of the full linear group over a Galois field, Trans. Amer. Math. Soc., 71 (1951), 274-282.
FORMULA
G.f.: Product_{k >= 1} f(x^k)^p_k, where f(x) = Product_{k >= 0} 1/(1-x^k) = Sum_{k >= 0} p_k*x^k and p_k is the number of partitions of k (A000041).
Recurrence relation: a(n+1) = (1/(n+1)) * Sum_{k=0..n} a(k)*g(n-k+1) where g(n) = Sum_{i*j | n} p(i)*i*j, with the sum over all ordered pairs (i, j) such that their products divide n and p(i) is the number of partitions of i. Also a(0)=1. - Brett Witty (witty(AT)maths.anu.edu.au), Jul 17 2003
Euler transform of A047968(n). - Vladeta Jovovic, Jun 23 2004
EXAMPLE
a(2) = 4 as there are four types of conjugacy classes of 2 X 2 matrices over GF(q):
* the scalar matrices (diagonal matrix with both entries the same)
* the direct sum of two scalars (diagonal matrix with both entries different)
* the non-diagonalizable Jordan block (upper triangular matrix with the same entry along the diagonal and a 1 in the superdiagonal)
* companion matrices of irreducible quadratics over GF(q)
This example can be found in Green's paper (in the references).
MATHEMATICA
m = 32; f[x_] = Product[1/(1-x^k), {k, 1, m}]; gf[x_] = Product[f[x^k]^PartitionsP[k], {k, 1, m}]; Drop[ CoefficientList[ Series[gf[x], {x, 0, m}], x], 1] (* Jean-François Alcover, Aug 01 2011, after g.f. *)
PROG
(GAP) a := function(n) local k, sum; sum := 0; for k in [0..n-1] do sum := sum + a(k)*g(n-k); od; return sum/n; end;
g := function(n) local i, j, sum; for i in DivisorsInt(n) do for j in DivisorsInt(n/i) do sum := sum + NrPartitions(i)*i*j; od; od; return sum; end;;
# This code is significantly faster if you store previously computed values of a(n) and g(n).
# Brett Witty (witty(AT)maths.anu.edu.au), Jul 17 2003
(GAP) a := function(n) if( n = 0) then return 1; else return Sum([0..n], i -> t(i) * Sum(DivisorsInt(n-i), d -> d * NrPartitions(d) * Sigma(n/d)) )/n; fi; end;; # Brett Witty (witty(AT)maths.anu.edu.au), Jul 12 2006
CROSSREFS
KEYWORD
nonn,nice,easy
AUTHOR
EXTENSIONS
More terms from Brett Witty (witty(AT)maths.anu.edu.au), Jul 17 2003
STATUS
approved