Jean Francis Michon - cp's OEIS frontend

User: Jean Francis Michon

Jean Francis Michon has authored 4 sequences.

A165912 Number of alternating polynomials of degree 3n in GF(2)[X], n>0.

2, 0, 2, 2, 4, 6, 12, 20, 38, 66, 124, 224, 420, 774, 1456, 2720, 5140, 9690, 18396, 34918, 66576, 127038, 243148, 465920, 894784, 1720530, 3314018, 6390930, 12341860, 23860200, 46182444, 89477120, 173534032, 336857610, 654471204, 1272578048, 2476377540, 4822410222, 9397535280

Offset: 1

Jean Francis Michon and Philippe Ravache (philippe.ravache(AT)univ-rouen.fr), Sep 30 2009

We define an alternating polynomial as follows: let I be the set of irreducible polynomials of degree > 1 over GF(2) and Sym_3 the symmetric group on 3 elements. For a polynomial P in I of degree n, we define P*(X) = X^n P(1/X) and P+(X) = P(X+1). The operators define an action of the group Sym_3 over I. Then an alternating polynomial is defined by the property that P*=P+.

The degree of an alternating polynomial is always 0 mod 3. The numbers in the sequence are always even. These polynomials are invariant under the action of the alternating subgroup Alt_3 of S3.

G. C. Greubel, Table of n, a(n) for n = 1..3300
J.-F. Michon, P. Ravache, On different families of invariant irreducible polynomials over F_2, Finite fields & Applications 16 (2010) 163-174

A001037 is the enumeration by degree of the polynomials of the set I.

A000048 is the enumeration by degree of the polynomials such that P=P* (self-reciprocal polynomials) which is the same as the one for the polynomials such that P=P+ or P=((P+)*)+.

a[n_] := 2*DivisorSum[n, Boole[Mod[n/#, 3] != 0] MoebiusMu[n/#]*(2^# - (-1)^#) &]/(3 n); Array[a, 40] (* Jean-François Alcover, Dec 03 2015, adapted from PARI *)

L(n, k) = sumdiv(gcd(n,k), d, moebius(d) * binomial(n/d, k/d) );
a(n) = sum(k=0, n, if( (n+k)%3!=0, L(n, k), 0 ) ) / n;
vector(55,n,a(n))
/* Joerg Arndt, Jun 28 2012 */

a(n) = 2*(sum_{d|n, n/d != 0 mod 3} mu(n/d)*(2^d - (-1)^d))/(3n).

a(n) = 2 * A165920(n).

Edited by N. J. A. Sloane, May 15 2010

A165921 Number of 6-elements orbits of S3 action on irreducible polynomials of degree n > 1 over GF(2).

Original entry on oeis.org

0, 0, 0, 1, 1, 3, 4, 9, 15, 31, 53, 105, 189, 363, 672, 1285, 2407, 4599, 8704, 16641, 31713, 60787, 116390, 223696, 429975, 828495, 1597440, 3085465, 5964488, 11545611, 22368256, 43383477, 84212475, 163617801, 318140816, 619094385, 1205595657, 2349383715, 4581280972, 8939118925, 17452532040, 34093383807

Offset: 2

Jean Francis Michon, Philippe Ravache (philippe.ravache(AT)univ-rouen.fr), Sep 30 2009

The terms are denoted h_6 in the Michon/Ravache reference.

J. E. Iglesias, Enumeration of polytypes MX and MX_2 through the use of the symmetry of the Zhadanov symbol, Acta Cryst. A 62 (3) (2006) 178-194, Table 1.

J.-F. Michon, P. Ravache, On different families of invariant irreducible polynomials over F_2[X], Finite fields & Applications, 16 (2010) 163-174.

A001037 is the enumeration by degree of the irreducible polynomials over GF(2), A000048 is the number of 3-elements orbits, A165920 is the number of 2-elements orbits.
Cf. A011957.
Cf. A096060 = A165921 o A000040 (on 3..oo), a subsequence of this sequence.

L[n_, k_] := DivisorSum[GCD[n, k], MoebiusMu[#]*Binomial[n/#, k/#] &];
A165920[n_] := Sum[If[(n + k) ~Mod~ 3 == 1, L[n, k], 0], {k, 0, n}]/n;
A001037[n_] := If[n == 0, 1, DivisorSum[n, MoebiusMu[#]*2^(n/#) &]/n];
A000048[n_] := DivisorSum[n, Mod[#, 2]*(MoebiusMu[#]*2^(n/#)) &]/(2*n);
A165921[n_] := Module[{an},
  If[n <= 2, Return[0]];
  an = A001037[n];
  If[Mod[n, 2] == 0, an -= 3*A000048[n/2]];
  If[Mod[n, 3] == 0, an -= 2*A165920[n/3]];
  an /= 6;
  Return[an]
];
Table[A165921[n], {n, 2, 50}] (* Jean-François Alcover, Dec 02 2015, adapted from Joerg Arndt's PARI script *)

L(n, k)=sumdiv(gcd(n, k), d, moebius(d) * binomial(n/d, k/d) );
A165920(n)=sum(k=0, n, if( (n+k)%3==1, L(n, k), 0 ) ) / n;
A001037(n)=if(n<1, n==0, sumdiv(n, d, moebius(d)*2^(n/d))/n);
A000048(n)=sumdiv(n, d, (d%2)*(moebius(d)*2^(n/d)))/(2*n);
A165921(n)= /* this sequence */
{
    my(an);
    if ( n<=2, return(0) );
    an = A001037(n);
    if (n%2==0, an -= 3*A000048(n/2) );
    if (n%3==0, an -= 2*A165920(n/3) );
    an /= 6;
    return( an );
}
/* Joerg Arndt, Jul 12 2012 */

A165921(n)=if(n>2,A001037(n)-if(!bittest(n,0),3*A000048(n\2))-if(n%3==0,2*A165920(n\3)))\6 \\ Based on Joerg Arndt's code from Jul 12 2012. Take up-to-date code for other sequences from the respective record. - M. F. Hasler, Sep 27 2018

(see PARI code)

a(p) = (2^(p-1)-1)/3p = A096060(n) for all primes p = prime(n) >= 5, n >= 3: A165921 o A000040 = A096060 on the domain [3..oo) of that sequence. - M. F. Hasler, Sep 27 2018

Incorrect formula removed and more terms added by Joerg Arndt, Jul 12 2012

A165920 Number of 2-elements orbits of S3 action on irreducible polynomials of degree 3n, n > 0, over GF(2).

Original entry on oeis.org

1, 0, 1, 1, 2, 3, 6, 10, 19, 33, 62, 112, 210, 387, 728, 1360, 2570, 4845, 9198, 17459, 33288, 63519, 121574, 232960, 447392, 860265, 1657009, 3195465, 6170930, 11930100, 23091222, 44738560, 86767016, 168428805, 327235602, 636289024, 1238188770, 2411205111, 4698767640, 9162588158, 17878237850

Offset: 1

Jean Francis Michon, Philippe Ravache (philippe.ravache(AT)univ-rouen.fr), Sep 30 2009

Arndt's PARI code computes a(n) as the sum, divided by n, of every 3rd term in row n of L = A050186 = Möbius transform of binomials, starting with k = (1-n) mod 3 (nonnegative remainder), where k = 0 and k = n give L(n, k) = 0 and can be omitted. Cf. A053727, EXAMPLE and second PROGRAM. - M. F. Hasler, Sep 27 2018

			Illustrating computation via L = A050186, cf. COMMENTS: a(1) = [L(1,0)] = 0. a(2) = [L(2,2)] = 0. a(3) = L(3,1)/3 = 3/3 = 1. a(4) = ([L(4,0)] + L(4,3))/4 = 4/4 = 1. a(5) = (L(5,2) + [L(5,5)])/5 = 10/5 = 2. In [...] are terms L(n,0) = L(n,n) = 0.

Robert Israel, Table of n, a(n) for n = 1..3331
J. E. Iglesias, Enumeration of polytypes of MX and MX_2 through the use of the symmetry of the Zhadanov symbol, Acta Cryst. A 62 (3) (2006) 176-194, Table 1.
J.-F. Michon, P. Ravache, On different families of invariant irreducible polynomials over F_2, Finite fields & Applications 16 (2010) 163-174.

This sequence is the half of A165912 (the number of alternate polynomials). A001037 is the enumeration by degree of the polynomials of I. A000048 is the number of 3-elements orbits of S3 action on I.

f:= proc(n) local D,d;
  D:=remove(d -> (n/3/d)::integer, numtheory:-divisors(n));
  add(numtheory:-mobius(n/d)*(2^d - (-1)^d),d=D)/(3*n)
end proc:
map(f, [$1..100]); # Robert Israel, Jul 14 2019

a[n_] := Sum[If[Mod[n/d, 3] == 0, 0, MoebiusMu[n/d]*(2^d - (-1)^d)/(3n)], {d, Divisors[n]}];
Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Feb 02 2023 *)

L(n, k) = sumdiv(gcd(n,k), d, moebius(d) * binomial(n/d, k/d) );
a(n) = sum(k=0, n, if( (n+k)%3==1, L(n, k), 0 ) ) / n;
vector(55,n,a(n))
/* Joerg Arndt, Jun 28 2012 */

A165920(n,k=(1-n)%3)=sum(i=0,(n-k)\3,A050186(n,k+3*i))\n \\ For illustration. - M. F. Hasler, Sep 30 2018

a(n) = (sum_{d|n, n/d != 0 mod 3} mu(n/d)*(2^d - (-1)^d))/(3n).

A100344 Gives the i-th coefficient M(k,i) of the decomposition of the polynomials B(k,X^2) in the basis of all B(i,X), where B(i,X) is the i-th binomial polynomial: B(i,X) = X(X-1)...(X-i+1)/i! for any i > 0 and B(0,X) = 1 by definition.

Original entry on oeis.org

1, 0, 1, 2, 0, 0, 6, 18, 12, 0, 0, 4, 72, 248, 300, 120, 0, 0, 1, 123, 1322, 4800, 7800, 5880, 1680, 0, 0, 0, 126, 3864, 32550, 121212, 235200, 248640, 136080, 30240

Offset: 0

Jean Francis Michon, Nov 18 2004

The binomial polynomials are a basis of the space of all polynomials and the decomposition of a polynomial in this basis is called its Mahler's expansion. So the sequence gives the Mahler's expansion of the binomial polynomials composed with "squaring".
For example:
B(0,X^2) = 1*B(0,X)
B(1,X^2) = 0*B(0,X)+1*B(1,X)+2*B(2,X)
B(2,X^2) = 0*B(0,X)+0*B(1,X)+6*B(2,X)+18*B(3,X)+12*B(4,X)
The coefficients may be written in a "Pascal's triangle" arrangement:
1
0 1 2
0 0 6 18 12
0 0 4 72 248 300 120
0 0 1 1 123 1322 4800 7800 5880 1680
They are always < binomial(i^2, k) or equal to it when i^2+1 > k > (i-1)^2. They are 0 if i > 2k or k > i^2.
They have a combinatorial interpretation if i > 0. Let the set I={1,...,i} and I X I the set of pairs, M(k,i) is the number of subsets with k pairs in I X I such that any element of I appears as a coordinate in at least one pair.
Example: M(2,2) = 6 because all subsets with 2 elements in IxI = {(1,1),(1,2),(2,1),(2,2)} satisfy the property and there are 6 such subsets.
The M(k,i) sequence allows the enumeration of quasi-reduced ordered binary decision diagram (QROBDD) canonically associated to Boolean functions (see references).

			M(2,2)=6 because B(2,X^2) = 0*B(0,X) + 0*B(1,X) + 6*B(2,X) + 18*B(3,X) + 12*B(4,X).

J. F. Michon, J.-B. Yunes and P. Valarcher, On maximal QROBDD's of Boolean functions, Theor. Inform. Appl. 39 (2005), no. 4, 677-686.

Cf. for binomial polynomials: A080959.

M(0, 0) = 1 and, for all i > 0, M(0, i) = 0. Let M(k, i) = 0 if all i < 0 and all k for ease. Then, for all k > 0, i > 0: M(k, i)= [(i^2-k+1)M(k-1, i) + i(2i-1)M(k-1, i-1) + i(i-1)M(k-1, i-2) ]/k.

cp's OEIS Frontend

User: Jean Francis Michon

A165912 Number of alternating polynomials of degree 3n in GF(2)[X], n>0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A165921 Number of 6-elements orbits of S3 action on irreducible polynomials of degree n > 1 over GF(2).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A165920 Number of 2-elements orbits of S3 action on irreducible polynomials of degree 3n, n > 0, over GF(2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A100344 Gives the i-th coefficient M(k,i) of the decomposition of the polynomials B(k,X^2) in the basis of all B(i,X), where B(i,X) is the i-th binomial polynomial: B(i,X) = X(X-1)...(X-i+1)/i! for any i > 0 and B(0,X) = 1 by definition.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula