q. about g.f.'s from a correspondent

[Max Alekseyev]

Suppose that we want to find sequences whose generating function z(x)
satisfies a quadratic equation:
p(x)*z(x)^2 + q(x)*z(x) + r(x) = 0
where degree of the polynomial p(x), q(x) and r(x) are bounded by some
integer k.

I suggest the following procedure to test a sequence a() from OEIS.
Suppose that the terms a(0), ..., a(n) are present in OEIS where
n>=3*(k+1) (if this does not hold, reject the sequence as "too
short").
Let z(x) = a(0) + a(1)*x + ... + a(n)*x^n.
Build a matrix M where each row represents coefficients of x^0 ... x^n
in the expansion of the following functions:
1
x
x^2
...
x^k
z(x)
x*z(x)
x^2*z(x)
...
x^k*z(x)
z(x)^2
x*z(x)^2
x^2*z(x)^2
...
x^k*z(x)^2
The matrix M has 3*(k+1) rows and n+1 columns (it is important that
the number of columns is greater than the number of rows). Compute the
rank of M and compare it to the number of rows 3*(k+1).
If rank(M)<3*(k+1), then the sequence is likely to be what we are
looking for, otherwise (i.e., if rank(M)>=3*(k+1)) reject the
sequence.

The idea behind this test is the following:
The inequality rank(M)<3*(k+1) then there exists a linear combination
of the rows of M equal 0. Let the coefficients in this combination be
(r_0,r_1,...,r_k,q_0,q_1,...,q_k,p_0,p_1,...,p_k)
then the coefficients of x^0, ..., x^n in the polynomial
r_0 + r_1*x + ... + r_k*x^k + q_0*z(x) + q_1*x*z(x) + ... +
q_k*x^k*z(x) + p_0*z(x)^2 + p_1*x*z(x)^2 + ... + p_k*x^k*z(x)^2
are all zero, giving a great chance that the generating function of
the sequence a() satisfy the equation:
r(x) + q(x)*z(x) + p(x)*z(x)^2 = 0
where
r(x) = r_0 + r_1*x + ... + r_k*x^k
q(x) = q_0 + q_1*x + ... + q_k*x^k
p(x) = p_0 + p_1*x + ... + p_k*x^k

Regards,
Max

On 3/2/07, N. J. A. Sloane <njas at research.att.com> wrote:
> Can anyone help here?
> Neil
>
> From P.J.Larcombe at Derby.ac.uk  Fri Mar  2 10:08:09 2007
> Subject: O.G.F. Info Request
> Date: Fri, 2 Mar 2007 15:07:17 -0000
> From: "Peter Larcombe" <P.J.Larcombe at Derby.ac.uk>
> To: <njas at research.att.com>
>
> Neil,=20
>
> I have a query you may be able to help with. I'm looking for sequences
> whose O.G.F.=20
>
> satisfies a QUADRATIC equation (examples: Catalan, Schroder, Motzkin,
> Fibonnaci),=20
>
> but playing around trying to find some other using the O.E.I.S. is
> proving difficult - I need=20
>
> as many as I can to test some code on, then I need to move on to cubics,
> etc.=20
>
> =20
>
> Question:=20
>
> Is there a listing anywhere of=20
>
> Sequences whose O.G.F. satisfies a QUADRATIC=20
>
> Sequences whose O.G.F. satisfies a CUBIC
>
> etc., =20
>
> =20
>
> or, failing that, could you (with your vast knowledge) suggest any
> others to keep me=20
>
> going (or could you suggest anyone else who might know about this).=20
>
>