A087291 Number of pairs of polynomials (f,g) in GF(2)[x] satisfying 1 <= deg(f) <= n, 1 <= deg(g) <= n and gcd(f,g) = 1.

0, 2, 18, 98, 450, 1922, 7938, 32258, 130050, 522242, 2093058, 8380418, 33538050, 134184962, 536805378, 2147352578, 8589672450, 34359214082, 137437904898, 549753716738, 2199019061250, 8796084633602, 35184355311618, 140737454800898, 562949886312450

Offset

0,2

Comments

Unpublished result due to Stephen Suen, David desJardins, and W. Edwin Clark. This is the case k = 2, q = 2 of their formula (q^(n+1)-q)^k*(1-1/(q^(k-1))) for the number of ordered k-tuples (f_1, ..., f_k) of polynomials in GF(q)[x] such that 1 <= deg(f_i) <= n for all i and gcd(f_1, ..., f_k) = 1.

Links

Table of n, a(n) for n=0..24.

Index entries for linear recurrences with constant coefficients, signature (7,-14,8).

Formula

a(n) = 2*(2^n - 1)^2.

G.f.: 2*x*(1+2*x)/((1-x)*(1-2*x)*(1-4*x)). - Colin Barker, Feb 22 2012

From Elmo R. Oliveira, Sep 19 2025: (Start)

E.g.f.: 2*exp(x)*(1 - 2*exp(x) + exp(3*x)).

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

a(n) = 7*a(n-1) - 14*a(n-2) + 8*a(n-3). (End)

Example

a(1) = 2 since gcd(x,x+1) = 1 and gcd(x+1,x) = 1 and no other pair (f,g) of polynomials in GF(2)[x] of degree 1 satisfy gcd(f,g) = 1.

Prog

(PARI) concat(0, Vec(2*x*(1+2*x)/(1-7*x+14*x^2-8*x^3) + O(x^26))) \\ Elmo R. Oliveira, Sep 19 2025

Crossrefs

Cf. A060867, A087289, A087290, A087292.

Sequence in context: A052638 A127553 A055357 * A267691 A219758 A005969

Adjacent sequences: A087288 A087289 A087290 * A087292 A087293 A087294

Keyword

easy,nonn

Author

W. Edwin Clark, Aug 29 2003

Extensions

More terms from Elmo R. Oliveira, Sep 19 2025

Status

approved