%I M3340 #36 Sep 19 2023 08:20:35
%S 1,4,8,22,42,103,199,441,859,1784,3435,6882,13067,25366,47623,90312,
%T 167344,311603,570496,1045896,1893886,3426466,6140824,10984249,
%U 19499214,34526844,60758733,106613119,186099976,323883380,561141244,969308408
%N a(n) = number of types of conjugacy classes in GL(n,q) (this is independent of q).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A003606/b003606.txt">Table of n, a(n) for n = 1..500</a>
%H J. A. Green, <a href="https://doi.org/10.1090/S0002-9947-1955-0072878-2">The characters of the finite general linear groups</a>, Trans. Amer. Math. Soc., 80 (1955), 402-447.
%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>.
%H R. Steinberg, <a href="https://doi.org/10.1090/S0002-9947-1951-0043784-0">A geometric approach to the representations of the full linear group over a Galois field</a>, Trans. Amer. Math. Soc., 71 (1951), 274-282.
%F 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).
%F 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
%F Euler transform of A047968(n). - _Vladeta Jovovic_, Jun 23 2004
%F 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
%e a(2) = 4 as there are four types of conjugacy classes of 2 X 2 matrices over GF(q):
%e * the scalar matrices (diagonal matrix with both entries the same)
%e * the direct sum of two scalars (diagonal matrix with both entries different)
%e * the non-diagonalizable Jordan block (upper triangular matrix with the same entry along the diagonal and a 1 in the superdiagonal)
%e * companion matrices of irreducible quadratics over GF(q)
%e This example can be found in Green's paper (in the references).
%t 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. *)
%o (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;
%o 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;;
%o # This code is significantly faster if you store previously computed values of a(n) and g(n).
%o # Brett Witty (witty(AT)maths.anu.edu.au), Jul 17 2003
%o (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
%Y Cf. A001970.
%Y Cf. A006951, A006952, A049314, A049315, A049316.
%K nonn,nice,easy
%O 1,2
%A _N. J. A. Sloane_, _Mira Bernstein_
%E More terms from Brett Witty (witty(AT)maths.anu.edu.au), Jul 17 2003
|