|
|
A003606
|
|
a(n) = number of types of conjugacy classes in GL(n,q) (this is independent of q).
(Formerly M3340)
|
|
2
|
|
|
1, 4, 8, 22, 42, 103, 199, 441, 859, 1784, 3435, 6882, 13067, 25366, 47623, 90312, 167344, 311603, 570496, 1045896, 1893886, 3426466, 6140824, 10984249, 19499214, 34526844, 60758733, 106613119, 186099976, 323883380, 561141244, 969308408
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
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
Recurrence relation: a(0)=1, a(n+1) = (1/(n+1)) * Sum_{k=0..n} a(k)*g(n-k+1) where g(n) = Sum_{d | n} d * A000041(d) * A000203(n/d). - Brett Witty (witty(AT)maths.anu.edu.au), Jul 12 2006
|
|
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
|
|
|
|