cp's OEIS Frontend

A242587 The number of conjugacy classes of n X n matrices over F_3.

%I A242587 #31 Apr 12 2018 22:23:10
%S A242587 1,3,12,39,129,399,1245,3783,11514,34734,104754,314922,946623,2842077,
%T A242587 8532147,25603788,76830033,230513439,691598901,2074870002,6224790639,
%U A242587 18674600664,56024355396,168073769199,504222998115,1512671142432,4538018555652,13614062210490
%N A242587 The number of conjugacy classes of n X n matrices over F_3.
%C A242587 Apparently the Euler transform of A001867.
%H A242587 Alois P. Heinz, <a href="/A242587/b242587.txt">Table of n, a(n) for n = 0..1000</a>
%H A242587 K. E. Morrison, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Morrison/morrison37.html">Integer sequences and matrices over finite fields</a>, J. Int. Seq. 9 (2006) # 06.2.1, Section 1.16.
%F A242587 G.f.: 1/Product_{r>=1} (1-3*x^r).
%F A242587 a(n) = S(n,1), where S(n,m) = sum(k=m..n/2, 3*S(n-k,k))+3, S(n,n)=3, S(0,m)=1, S(n,m)=0 for n<m. - _Vladimir Kruchinin_, Sep 07 2014
%F A242587 a(n) ~ c * 3^n, where c = Product_{k>=1} 1/(1-1/3^k) = 1.7853123419985341903674... . - _Vaclav Kotesovec_, Mar 19 2015
%F A242587 G.f.: Sum_{i>=0} 3^i*x^i/Product_{j=1..i} (1 - x^j). - _Ilya Gutkovskiy_, Apr 12 2018
%p A242587 A242587 := proc(n)
%p A242587     local r,x ;
%p A242587     if n  = 0 then
%p A242587         1;
%p A242587     else
%p A242587         1/mul(1-3*x^r,r=1..n) ;
%p A242587         convert(%,parfrac,x) ;
%p A242587         coeftayl(%,x=0,n) ;
%p A242587     end if;
%p A242587 end proc:
%p A242587 # second Maple program:
%p A242587 b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
%p A242587       b(n, i-1) +`if`(i>n, 0, 3*b(n-i, i))))
%p A242587     end:
%p A242587 a:= n-> b(n$2):
%p A242587 seq(a(n), n=0..50);  # _Alois P. Heinz_, Sep 07 2014
%t A242587 b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, b[n, i-1] + If[i>n, 0, 3*b[n-i, i]]]] ; a[n_] := b[n, n]; Table[a[n], {n, 0, 50}] (* _Jean-François Alcover_, Apr 03 2015, after _Alois P. Heinz_ *)
%t A242587 (O[x]^20 - 2/QPochhammer[3, x])[[3]] (* _Vladimir Reshetnikov_, Nov 20 2015 *)
%o A242587 (Maxima)
%o A242587 S(n, m):=if n=0 then 1 else if n<m then 0 else if n=m then 3 else sum(3*S(n-k, k), k, m, n/2)+3;
%o A242587 makelist(S(n, 1), n, 0, 17); /* _Vladimir Kruchinin_, Sep 07 2014 */
%Y A242587 Cf. A070933 (over F_2).
%Y A242587 Column k=3 of A246935.
%K A242587 nonn
%O A242587 0,2
%A A242587 _R. J. Mathar_, May 18 2014