[seqfan] Re: Divisibility sequences

[Paul Raff]

Hi everyone,

In regards to spanning trees, I've verified (using Wilf-Zeilberger
methods) the divisibility property of the number of spanning trees of
the grid graph G x P_n for all graphs G with at most 5 vertices.

Just this week I was able to put the finishing touches on a
combinatorial proof that proves the divisibility property for all
graphs G. I believe all relevant information on graphs up to 4
vertices is on OEIS; I am working on putting up the information on
graphs with 5 and 6 vertices on OEIS and a webpage I made for it
(since it will become a sizable part of my PhD thesis):

http://math.rutgers.edu/~praff/span/index.xml

As Prof. Guy mentioned, there are relationships and interesting
equalities abound in regards to these sequences, beyond divisibility.


                                      [paul]

On Fri, Mar 27, 2009 at 11:42 AM, Richard Guy <rkg at cpsc.ucalgary.ca> wrote:
> There are infinitely many of these, a few
> already being in OEIS, though not always
> indicated as such.  I don't have the energy,
> endurance or expertise to get any amount of
> them into acceptable shape for OEIS, and Neil
> is already overwhelmed.  If anyone else is
> interested (Tony Noe wd be an excellent
> candidate) I could send them several long
> TeX files of inchoate, incompetent and
> incomplete ramblings and calculations, and
> suggestions for further work.
>
> Here's a small sample:
>
>        A003733 = 5*(A143699)^2
>       A003751 = 5^3*(A004187)^4
>   A003753 = 4*(A001109)*(A001353)^2
>    A003755 = (A001109)*(A001906)^2
>
> These last two emerged after a complete
> analysis of all such fourth order
> recurrences by my colleague Hugh Williams.
> As they involve spanning trees of graphs,
> there are probably combinatorial proofs
> as well.
>
> Here's a variant of  A003735  (which is
> NOT a divisibility sequence) with the same
> recurrence relation, but different initial
> conditions, which I believe not to be in
> OEIS:
>
> 0, 1, 44, 1833, 76208, ...
>
> It is the case  b = 44, c = 1536  in the
> following parody of part of Hugh Williams's
> theory.
>
> Characteristic polynomial
>
> x^4 - bx^3 + (1/4)(b^2 - c + 8)x^2 - bx + 1
>
> assume that  a_{-n} = a_n  and take  a_0 = 0,
> a_1 = 1,
> a_2 = b = \alpha_1+\beta_1+\alpha_2+\beta_2,
> then
>
> a_3 = \frac{3}{4}b^2+\frac{1}{4}c+2 =
>   \alpha_1^2+\beta_1^2+\alpha_2^2+\beta_2^2 +
>   2(\alpha_1+\beta_1+\alpha_2+\beta_2)+1
>
> and I cd clutter you up all the way to a_{10},
> but anyone can work them out who wants to.
>
> The case  b = 2, c = 20  has recently been
> added to OEIS as A138573 by Tony Noe,
> possibly as the result of some previous
> emission of mine.
>
> b = 19, c = 205  is  A143699   (cf.  A003729)
>
> sqrt(A003739 / 5) = (A001906)*(b = 15, c = 105)
>
> b = 1, c = 33  is  A003757
>
> ...  but I've probably already alarmed the
> moderator by now.   Best to all,   R.
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>



-- 
Paul Raff
Graduate Assistant - Monitoring Message Streams
Rutgers University
http://math.rutgers.edu/~praff