[seqfan] Re: Gen. Functs. A039219

franktaw at netscape.net franktaw at netscape.net
Fri Sep 11 21:48:56 CEST 2009

Indeed, none of these are correct.

A rational generating function implies a finite (linear) recurrence; 
that is, a(n) is a function of a(n-1), ..., a(n-k) for fixed k.  Any 
sequence that has arbitrarily long identical subsequences, but is not 
periodic, thus cannot have a rational generating function.

The first differences of these sequences meet this criterion, and thus 
do not have rational generating functions.  But the generating 
functions for a sequence and its first differences are related by a 
factor of (1-x), so one is rational if and only if the other is.

Therefor, these sequences do not have rational generating functions.

See my paper with Frank Ruskey -- 
http://www.cs.uwaterloo.ca/journals/JIS/VOL12/Ruskey2/ruskey14.html -- 
for an approach to generating functions for this kind of sequence.

Franklin T. Adams-Watters

-----Original Message-----
From: Richard Mathar <mathar at strw.leidenuniv.nl>

I see that the generating function provided in A039219 is
incorrect, starting at the power [x^101] g(x), where it differs
from the correct value by a(n=101)=120 by 1. It is no surprise
that the g.f. is much more complicated than the one given, because
the number of digits to compare have these typical wrap-around feature
at the powers of 12 (in this case).

I fear the same problem appears in A039255, A039257, A039261,A039263,
A039266, A039270, A039268. Can s.o. check this independently?

In addition: is there any indication that the g.f. for the coding
function A(n,10,7) in A005855 or A005862 is correct, given that the 
tables give only lower bounds for values of n roughly larger than 22?


More information about the SeqFan mailing list