|
%I M2577 #75 Sep 08 2022 08:44:35
%S 1,1,3,6,14,27,60,117,246,490,1002,1998,4053,8088,16284,32559,65330,
%T 130626,261726,523374,1047690,2095314,4192479,8384808,16773552,
%U 33546736,67101273,134202258,268420086,536839446,1073710914,2147420250,4294904430,8589807438
%N Number of conjugacy classes in GL(n,2).
%C Unlabeled permutations of sets. - _Christian G. Bower_, Jan 29 2004
%C From _Joerg Arndt_, Jan 02 2013: (Start)
%C Set q=2 and f(m)=q^(m-1)*(q-1), then a(n) is the sum over all partitions P of n over all products Product_{k=1..L} f(m_k) where L is the number of different parts in the partition P=[p_1^m_1, p_2^m_2, ..., p_L^m_L], see the Macdonald reference.
%C Setting q to a prime power gives the sequence "Number of conjugacy classes in GL(n,q)":
%C q=3: A006952, q=4: A049314, q=5: A049315, q=7: A049316, q=8: A182603,
%C q=9: A182604, q=11: A182605, q=13: A182606, q=16: A182607, q=17: A182608,
%C q=19: A182609, q=23: A182610, q=25: A182611, q=27: A182612.
%C Sequences where q is not a prime power are:
%C q=6: A221578, q=10: A221579, q=12: A221580,
%C q=14: A221581, q=15: A221582, q=18: A221583, q=20: A221584.
%C (End)
%C From _Gus Wiseman_, Jan 21 2019: (Start)
%C Also the number of ways to split an integer partition of n into consecutive constant subsequences. For example, the a(5) = 27 ways (subsequences shown as rows) are:
%C 5 11111
%C .
%C 4 3 3 22 2 1111 1 111 11
%C 1 2 11 1 111 1 1111 11 111
%C .
%C 3 2 2 2 111 1 1 11 11 1
%C 1 2 11 1 1 111 1 11 1 11
%C 1 1 1 11 1 1 111 1 11 11
%C .
%C 2 11 1 1 1
%C 1 1 11 1 1
%C 1 1 1 11 1
%C 1 1 1 1 11
%C .
%C 1
%C 1
%C 1
%C 1
%C 1
%C (End)
%D W. D. Smith, personal communication.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Alois P. Heinz, <a href="/A006951/b006951.txt">Table of n, a(n) for n = 0..1000</a>
%H W. Feit and N. J. Fine, <a href="https://projecteuclid.org/euclid.dmj/1077468920">Pairs of commuting matrices over a finite field</a>, Duke Math. Journal, 27 (1960) 91-94.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=161">Encyclopedia of Combinatorial Structures 161</a>
%H I. G. Macdonald, <a href="https://doi.org/10.1017/S0004972700006882">Numbers of conjugacy classes in some finite classical groups</a>, Bulletin of the Australian Mathematical Society, vol.23, no.01, pp.23-48, (February-1981).
%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%F G.f.: Product_{n>=1} (1-x^n)/(1-2*x^n). - _Joerg Arndt_, Jan 02 2013
%F The number a(n) of conjugacy classes in the group GL(n, q) is the coefficient of t^n in Product_{k>=1} (1-t^k)/(1-q*t^k). - Noam Katz (noamkj(AT)hotmail.com), Mar 30 2001
%F Euler transform of A008965. - _Christian G. Bower_, Jan 29 2004
%F a(n) ~ 2^n - (1+sqrt(2) + (-1)^n*(1-sqrt(2))) * 2^(n/2-1). - _Vaclav Kotesovec_, Nov 21 2015
%F G.f.: exp(Sum_{k>=1} ( Sum_{d|k} d*(2^(k/d) - 1) ) * x^k/k). - _Ilya Gutkovskiy_, Sep 27 2018
%e For the 5 partitions of 4 (namely [1^4]; [2,1^2]; [2^2]; [3,1]; [4]) we have
%e (f(m) = 2^(m-1)*(2-1) = 2^(m-1) and)
%e f([1^4]) = 2^3 = 8,
%e f([2,1^2]) = 1*2^1 = 2,
%e f([2^2]) = 2^1 = 2,
%e f([3,1]) = 1*1 = 1,
%e f([4]) = 1,
%e the sum is 8+2+2+1+1 = 14 = a(4).
%e - _Joerg Arndt_, Jan 02 2013
%p with(numtheory):
%p b:= n-> add(phi(d)*2^(n/d), d=divisors(n))/n-1:
%p a:= proc(n) option remember; `if`(n=0, 1,
%p add(add(d*b(d), d=divisors(j)) *a(n-j), j=1..n)/n)
%p end:
%p seq(a(n), n=0..40); # _Alois P. Heinz_, Oct 20 2012
%t b[n_] := Sum[EulerPhi[d]*2^(n/d), {d, Divisors[n]}]/n-1; a[n_] := a[n] = If[n == 0, 1, Sum[Sum[d*b[d], {d, Divisors[j]}]*a[n-j], {j, 1, n}]/n]; Table[a[n], {n, 0, 40}] (* _Jean-François Alcover_, Feb 17 2014, after _Alois P. Heinz_ *)
%t Table[Sum[2^(Length[ptn]-Length[Split[ptn]]),{ptn,IntegerPartitions[n]}],{n,30}] (* _Gus Wiseman_, Jan 21 2019 *)
%o (Magma) /* The program does not work for n>19: */
%o [1] cat [NumberOfClasses(GL(n,2)): n in [1..19]]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006; edited by _Vincenzo Librandi_ Jan 24 2013
%o (PARI)
%o N=66; x='x+O('x^N);
%o gf=prod(n=1,N, (1-x^n)/(1-2*x^n) );
%o v=Vec(gf)
%o /* _Joerg Arndt_, Jan 02 2013 */
%Y Cf. A006952, A049314, A049315, A049316, A070933, A264685, A264687.
%Y Column k=0 of A218698. - _Alois P. Heinz_, Nov 04 2012
%Y Cf. A100471, A100883, A279784, A279786, A323433, A323582, A323583.
%K nonn
%O 0,3
%A _N. J. A. Sloane_
%E More terms from _Christian G. Bower_, Jan 29 2004
|
