A137503 Number of Frobenius equivalence classes of size n over GF(2^n) with their trace equal to the trace of their inverse.
1, 0, 1, 4, 3, 8, 16, 28, 45, 96, 167, 308, 579, 1100, 2018, 3852, 7280, 13776, 26133, 49996, 95223, 182248, 349474, 671176, 1289925, 2485644, 4793355, 9255700, 17894421, 34638296, 67105714, 130148812, 252644985, 490852972
Offset: 2
Keywords
Examples
Let g be a generator of the multiplicative group GF(2^6)^* with reduction polynomial t^6+t+1 = 0.
Pick g = t^3+1 (which generator is chosen doesn't matter for the sequence; but it matters for the table below).
Let n be an integer, 0 < n < 2^6 - 1. Let the smallest positive integer k such that (g^n)^(2^k) = g^n be k = 6, then the elements { g^n, (g^n)^2, (g^n)^(2^2), (g^n)^(2^3), (g^n)^(2^4), (g^n)^(2^5) } are all different and form an FEC with size 6.
These elements are equivalent, any may be chosen as representative.
The inverse of the FEC is an FEC with the inverse of those elements (all of which are in the same FEC of course).
The trace of each element is the same, of course and therefore we might as well speak about the inverse of the FEC and the trace of the FEC respectively.
In the table below, the FEC are denoted as {1,2,4,8,16,32} etc, only giving the exponents of g. All FEC with size 6 are given in both columns, the two columns give each others inverse.
The trace of the FEC is given after the FEC.
.......... x .......... Tr(x) ........ 1/x ........ Tr(1/x)
{ _1, _2, _4, _8, 16, 32} 0 { 31, 47, 55, 59, 61, 62} 1
{ _3, _6, 12, 24, 33, 48} 0 { 15, 30, 39, 51, 57, 60} 1
{ _5, 10, 17, 20, 34, 40} 1 { 23, 29, 43, 46, 53, 58} 1
{ _7, 14, 28, 35, 49, 56} 0 { _7, 14, 28, 35, 49, 56} 0
{ 11, 22, 25, 37, 44, 50} 1 { 13, 19, 26, 38, 41, 52} 0
{ 13, 19, 26, 38, 41, 52} 0 { 11, 22, 25, 37, 44, 50} 1
{ 15, 30, 39, 51, 57, 60} 1 { _3, _6, 12, 24, 33, 48} 0
{ 23, 29, 43, 46, 53, 58} 1 { _5, 10, 17, 20, 34, 40} 1
{ 31, 47, 55, 59, 61, 62} 1 { _1, _2, _4, _8, 16, 32} 0
This shows that there are 3 FEC (namely, 5, 7 and 23) whose trace is equal to the trace of its inverse and hence a(6) = 3.
Links
- Carlo Wood, Cracking parameter b of the elliptic curve.
Formula
Let b(1) = 0, b(2) = 1, b(n) = 2^(n-1) - b(n-1) - 2 * b(n-2) - 3.
Let c(1) = 1, c(n) = 2^(n-1) - sum_{0
Let w(n) = b(n) - sum_{1
Then a(n) = 2 * w(n) / n.
A126672 Third column of A126671.
0, 11, 46, 274, 1956, 16008, 147120, 1498320, 16742880, 203656320, 2678780160, 37888300800, 573444748800, 9248083891200, 158328230860800, 2867904245606400, 54799402065408000, 1101605810393088000, 23241327926648832000, 513476773573091328000, 11855774776045584384000
Offset: 2
Keywords
Links
- N. J. A. Sloane, Notes on Carlo Wood's Polynomials
A126671 Triangle read by rows: row n (n>=0) has g.f. Sum_{i=1..n} n!*x^i*(1+x)^(n-i)/(n+1-i).
0, 0, 1, 0, 1, 3, 0, 2, 7, 11, 0, 6, 26, 46, 50, 0, 24, 126, 274, 326, 274, 0, 120, 744, 1956, 2844, 2556, 1764, 0, 720, 5160, 16008, 28092, 30708, 22212, 13068, 0, 5040, 41040, 147120, 304464, 401136, 351504, 212976, 109584, 0, 40320
Offset: 1
Comments
The first nonzero column gives the factorial numbers, which are Stirling_1(*,1), the rightmost diagonal gives Stirling_1(*,2), so this triangle may be regarded as interpolating between the first two columns of the Stirling numbers of the first kind.
This is a slice (the right-hand wall) through the infinite square pyramid described in the link. The other three walls give A007318 and A008276 (twice).
The coefficients of the A165674 triangle are generated by the asymptotic expansion of the higher order exponential integral E(x,m=2,n). The a(n) formulas for the coefficients in the right hand columns of this triangle lead to Wiggen's triangle A028421 and their o.g.f.s. lead to the sequence given above. Some right hand columns of the A165674 triangle are A080663, A165676, A165677, A165678 and A165679. - Johannes W. Meijer, Oct 07 2009
Examples
Triangle begins: 0, 0, 1, 0, 1, 3, 0, 2, 7, 11, 0, 6, 26, 46, 50, 0, 24, 126, 274, 326, 274, 0, 120, 744, 1956, 2844, 2556, 1764, 0, 720, 5160, 16008, 28092, 30708, 22212, 13068, 0, 5040, 41040, 147120, 304464, 401136, 351504, 212976, 109584, 0, 40320, 367920, 1498320, 3582000, 5562576, 5868144, 4292496, 2239344, 1026576, ...
Links
- N. J. A. Sloane, Notes on Carlo Wood's Polynomials
Crossrefs
Programs
-
Maple
for n from 1 to 15 do t1:=add( n!*x^i*(1+x)^(n-i)/(n+1-i), i=1..n); series(t1,x,100); lprint(seriestolist(%)); od:
-
Mathematica
Join[{{0}}, Reap[For[n = 1, n <= 15, n++, t1 = Sum[n!*x^i*(1+x)^(n-i)/(n+1-i), {i, 1, n}]; se = Series[t1, {x, 0, 100}]; Sow[CoefficientList[se, x]]]][[2, 1]]] // Flatten (* Jean-François Alcover, Jan 07 2014, after Maple *)
Formula
Recurrence: T(n,0) = 0; for n>=0, i>=1, T(n+1,i) = (n+1)*T(n,i) + n!*binomial(n,i).
E.g.f.: x*log(1-(1+x)*y)/(x*y-1)/(1+x). - Vladeta Jovovic, Feb 13 2007
A126674 a(n) = n!*Sum_{j=0..n-1} 2^j/(j+1).
0, 1, 4, 20, 128, 1024, 9984, 115968, 1572864, 24477696, 430571520, 8452177920, 183175741440, 4343275192320, 111817607086080, 3105593229312000, 92539365359616000, 2944365169213440000, 99619235621240832000, 3571109329517936640000, 135199252993504444416000, 5390266968989421797376000
Offset: 0
Keywords
Comments
R. J. Mathar's recurrence is correct. a(n) has a new sum term in addition to what a(n-1) has, giving a(n) = n*a(n-1) + 2^(n-1)*(n-1)!. (Cf. A000165 = 2^n*n!.) The same for a(n-1) from a(n-2), and a factor, is 2*(n-1)*(a(n-1) - (n-1)*a(n-2)) = 2^(n-1)*(n-1)! too. Substitute it leaving a(n) in terms of a(n-1) and a(n-2). The recurrence shows the o.g.f. satisfies the differential equation (2*x^2-x+1)*g + 3*x^2*(2*x-1)*g' + 2*x^4*g'' - x = 0. - Kevin Ryde, Jul 11 2019
Links
- N. J. A. Sloane, Notes on Carlo Wood's Polynomials
Crossrefs
Row sums of A126671.
Programs
-
Magma
[0] cat [Factorial(n)*(&+[2^j/(j+1):j in [0..n-1]]):n in [1..21]]; // Marius A. Burtea, Jul 12 2019
-
Maple
F:=n->add( n!*2^i/(1+i), i=0..n-1);
-
Mathematica
Table[n!Sum[2^j/(j+1),{j,0,n-1}],{n,0,30}] (* Harvey P. Dale, Jun 14 2017 *) -
PARI
a(n) = n!*sum(j=0, n-1, 2^j/(j+1)); \\ Michel Marcus, Jul 12 2019
Formula
From Vladeta Jovovic, Feb 13 2007: (Start)
a(n) = 2^(n-1)*A003149(n-1).
O.g.f.: x*(Sum_{k>=0} k!*(2*x)^k)^2.
E.g.f.: log(1-2*x)/(x-1)/2. (End)
E.g.f.: E(x) = 1/2*log(1 - 2*x)/(x - 1) = x*(1 - x*G(0))/(x-1)/(2*x-1); G(k) = 1 + 2*x*(2*k+1)/(2*k + 3 - 2*x*(k+1)*(2*k+3)/(2*x*(k+1) + (k+2)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Dec 13 2011
G.f.: x*hypergeom([1,1],[],2*x)^2. - Mark van Hoeij, May 16 2013
Conjecture: a(n) + (-3*n+2)*a(n-1) + 2*(n-1)^2*a(n-2) = 0. - R. J. Mathar, May 23 2014
G.f.: x*(1/(1 - 2*x/(1 - 2*x/(1 - 4*x/(1 - 4*x/(1 - 6*x/(1 - 6*x/(1 - ...))))))))^2. - Ilya Gutkovskiy, May 10 2017
A126673 Third diagonal of A126671.
0, 2, 26, 274, 2844, 30708, 351504, 4292496, 55988640, 779171040, 11545476480, 181705299840, 3029581820160, 53376951801600, 991337037465600, 19363464423475200, 396915849843609600, 8520964324004966400, 191220598650009600000, 4477883953203763200000, 109242544826541772800000
Offset: 2
Keywords
Comments
It appears that a(n) = sum of invc(p) over all permutations p of {1,2,...,n}, where invc(p) is defined (by Carlitz) in the following way: express p in standard cycle form (i.e., cycles ordered by increasing smallest elements with each cycle written with its smallest element in the first position), then remove the parentheses and count the inversions in the obtained word. a(3)=2 because the six permutations 123,132,312,213,231 and 321 of {1,2,3} yield the words 123,123,132,123,123 and 132, respectively, having a total of 0+0+1+0+0+1 = 2 inversions. a(n) = Sum_{k>=0} k*A129178(n,k). - Emeric Deutsch, Oct 10 2007
References
- L. Carlitz, Generalized Stirling numbers, Combinatorial Analysis Notes, Duke University, 1968, 1-7.
Links
- G. C. Greubel, Table of n, a(n) for n = 2..445
- M. Shattuck, Parity theorems for statistics on permutations and Catalan words, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 5, Paper A07, 2005.
- N. J. A. Sloane, Notes on Carlo Wood's Polynomials
Programs
-
Magma
[Factorial(n)*(n*(n-5)/4 + HarmonicNumber(n)): n in [2..25]]; // G. C. Greubel, May 05 2019
-
Maple
seq(n!*(sum(1/k, k = 1 .. n)+(1/4)*n*(n-5)), n = 2 .. 21); # Emeric Deutsch, Oct 10 2007
-
Mathematica
Table[n!*(n*(n-5)/4 + HarmonicNumber[n]), {n,2,25}] (* G. C. Greubel, May 05 2019 *) -
PARI
my(x='x+O('x^30)); concat([0], Vec(serlaplace( (2*x - 3*x^2 + 2*(1-x)^2*log(1-x))/(2*(-1+x)^3) ))) \\ G. C. Greubel, May 05 2019 -
Sage
[factorial(n)*(n*(n-5)/4 + harmonic_number(n)) for n in (2..25)] # G. C. Greubel, May 05 2019
Formula
a(n) = n! * (n*(n-5)/4 + 1 + 1/2 + ... + 1/n). - Emeric Deutsch, Oct 10 2007
E.g.f.: (2*x - 3*x^2 + 2*(1-x)^2 * log(1-x)) / (2*(-1+x)^3). - G. C. Greubel, May 05 2019
a(n) = 2 * Sum_{k>=1} k * A381529(n,k). - Alois P. Heinz, Feb 26 2025
Comments