login
Number of Schur rings over Z_{2^n}.
2

%I #46 Oct 25 2018 02:44:17

%S 1,1,3,10,37,151,657,2989,14044,67626,332061,1656893,8379773,42871890,

%T 221528317,1154624725,6063752579,32058277129,170492969062,

%U 911505351447,4896187116904,26411691702030,143019573086693,777143219649275,4236216759058815

%N Number of Schur rings over Z_{2^n}.

%H Gheorghe Coserea, <a href="/A270789/b270789.txt">Table of n, a(n) for n = 0..1001</a>

%H Andrew Misseldine, <a href="http://arxiv.org/abs/1508.03757">Counting Schur Rings over Cyclic Groups</a>, arXiv preprint arXiv:1508.03757 [math.RA], 2015.

%F G.f.: ((2-x-sqrt(1-4*x) - sqrt(1-6*x+x^2))*(1-x) + 2*(x^2-1))/((2-x-sqrt(1-4*x)-sqrt(1-6*x+x^2))*(1-x-x^2) + 2*(x^3+x^2+x-1)) (see Misseldine link); equivalently, the g.f. can be rewritten as (x - 1)*(y*x - 1)/(y*x*(x^2 + x - 1) - 2*x + 1), where y = A000108(x) + A006318(x) - 1. - _Gheorghe Coserea_, Sep 12 2018

%t A000108[x_] = (1 - Sqrt[1 - 4x])/(2x);

%t A006318[x_] = (1 - x - (1 - 6x + x^2)^(1/2))/(2x);

%t y = A000108[x] + A006318[x] - 1;

%t gf = (x-1) (y x-1) / (y x (x^2 + x - 1) - 2x + 1);

%t CoefficientList[gf + O[x]^25, x] (* _Jean-François Alcover_, Oct 06 2018, after _Gheorghe Coserea_ *)

%o (PARI)

%o seq(N) = {

%o my(a=vector(N), sv=vector(N), cs=vector(N), c(k)=binomial(2*k, k)/(k+1),

%o s(k) = sum(j=0, k, binomial(2*j, j)*binomial(k + j, 2*j)/(j+1)));

%o a[1] = 1; a[2] = 1; a[3] = 3; a[4] = 10;

%o sv[1] = s(1); cs[1] = c(1) + sv[1];

%o for (j = 2, #cs, sv[j] = s(j); cs[j] = cs[j-1] + c(j) + sv[j]);

%o for (n = 4, #a-1,

%o a[n+1] = sum(k = 1, 3, 2^k * a[n+1-k]) - (c(n-1) + sv[n-1]) +

%o sum(k = 4, n, (c(k-1) + sv[k-1] - cs[k-3]) * a[n+1-k]));

%o return(a);

%o };

%o seq(25)

%o (PARI)

%o seq(N) = {

%o my(x='x+O('x^N), c=(1-(1-4*x)^(1/2))/(2*x),

%o s=(1-x-(1-6*x+x^2)^(1/2))/(2*x), y=c+s-1);

%o Vec((x - 1)*(y*x - 1)/(y*x*(x^2 + x - 1) - 2*x + 1));

%o };

%o seq(25) \\ _Gheorghe Coserea_, Sep 12 2018

%Y Cf. A000108, A006318, A269750, A270785, A270786, A270787.

%K nonn

%O 0,3

%A _N. J. A. Sloane_, Mar 23 2016

%E More terms from _Gheorghe Coserea_, Mar 24 2016

%E a(0)=1 prepended by _Gheorghe Coserea_, Sep 12 2018