[seqfan] Re: Help needed

[Jonathan Post]

Especially as D. J. Kleitman has an Erdos number of 1!

2010/3/12 Richard Guy <rkg at cpsc.ucalgary.ca>:
> I don't find the sequence ..., 125, 384, 1183, ...
> in OEIS, though it is evidently (part of) that
> found in the papers
>
>  MR0364002 (51 #257)
> Kleitman, D. J.; Golden, B.
> Counting trees in a certain class of graphs.
> Amer. Math. Monthly 82 (1975), 40--44.
>
> Let $G_n$ denote the graph with nodes, $1,2,\cdots,n$, in which nodes $i$
> and $j$ are joined if and only if the difference between $i$ and $j$, modulo
> $n$, equals one or two. The authors show that $G_n$ has $nf_n{}^2$ spanning
> trees, where $f_n$ denotes the $n$th Fibonacci number.
> Reviewed by J. W. Moon
>
> and
>
>  MR0806296 (87c:05045)
> Baron, G.(A-TUWN); Prodinger, H.(A-TUWN); Tichy, R. F.(A-TUWN); Boesch, F.
> T.(1-STIT); Wang, J. F.(RC-TAIN)
> The number of spanning trees in the square of a cycle.
> Fibonacci Quart. 23 (1985), no. 3, 258--264.
>
> The number mentioned in the title is $n$ times the square of the $n$th
> Fibonacci number, where $n$ is the length of the cycle. This result has been
> found by \n D. J. Kleitman\en and \n B. Golden\en [Amer. Math. Monthly 82
> (1975), 40--44; MR0364002 (51 #257)] by purely combinatorial methods. In the
> present paper the formula is proved by Kirchhoff's matrix tree theorem.
> Reviewed by J. Sedláček
>
> There are (for me) two (at least) difficulties:
>
> (a) the earlier members of the sequence,
>
> 0, 1, 2, 12, 36,
>
> may not be appropriate to the definitions
> in the papers.
>
> (b)  I can't reconcile the definitions
> of the graph.  Shouldn't  C_n^2, the
> square of the n-cycle, have  n^2  vertices
> and  2n^2  edges, being 4-valent?  The pix
> in Kleitman & Golden are indeed 4-valent,
> but have only  n  vertices and  2n  edges.
>
> And what is ``the third power of a cycle''
> [A005822] -- which refers to the Baron et
> al paper ?       R.
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
>