Analogy of A018805 for the ring GF(2)[x]

[Edwin Clark]

On Thu, 28 Aug 2003, Yuval Dekel wrote:

> Let R be the polynomial ring GF(2)[x] and a(n) be the cardinality of (f,g) 
> in RxR with :
> {(f,g): 1<=deg(f),deg(g)<=n, 1=gcd(f,g)} .
> 
> Can someone compute a(n) ? is it in the OEIS ?
> 


I don't know if it's in the OEIS. However, in 1997 Stephen Suen, David
des Jardin and I wrote a paper (which we never got around to
publishing) in which we proved that for n > 0 and k > 1 the number of
k-tuples of polynomials (f_1, f_2, . . . , f_k) in GF(q)[x] each of degree
from 1 to n such that gcd(f_1, f_2, . . . , f_k) = 1 is exactly 

       (q^(n+1)-q)^k*(1-1/(q^(k-1)))

It is a curious fact that for fixed positive integers n_i, i=1..k, the
number of k-tuples of polynomials (f_1, f_2, . . . , f_k) in GF(q)[x] with
deg(f_i) = n_i and gcd(f_1, . . . , f_k) = 1 is given by the same
formula!. 

We also calculated the number of k-tuples of polynomials (f_1, . . .,
f_k) where deg(f_i) <= n and gcd(f_1,...,f_k) = 1 to be:

   q^((n+1)*k) * (1 - 1/q^(k-1) + (q-1)/q^((n+1)*k))

I still have a copy of the paper if you'd like a copy. However, I think
that  knowing the answer makes it easy enough to prove these facts.

--Edwin