A055779

[franktaw at netscape.net]

OK.  It didn't occur to me that having put 1,2 together in a part, you 
would have an edge connecting one of them to a neighbor.  I was 
expecting that you would simply have an edge connecting the entire part 
to its neighbor.

Your other assumptions are correct.  People often use "free tree" 
instead of just "tree" precisely because rooted trees are very common 
in certain contexts, to the point that the "rooted" gets left off.  By 
having a separate modifier, the reference is always unambiguous.  (It 
was, in fact, the graph theory context that led me to think that you 
probably meant free trees.)

Thanks for the prompt response.

Franklin T. Adams-Watters


-----Original Message-----
From: Thomas Zaslavsky <zaslav at math.binghamton.edu>

  On Mon, 12 Jun 2006, franktaw at netscape.net wrote:

  > I am unable to make sense of this sequence. The definition of "fat 
tree" > reads: "A fat tree on vertex set V is a partition of V together 
with edges > that link the parts of the partition in a tree-like 
pattern: that is, when > the parts are collapsed to points, the edges 
are a tree." From offset 1, the > first 3 values given are 1,2,10.
 >
  > This definition doesn't specify whether the vertices are to be 
considered > distinct (although from context it appears that they are), 
nor what kind of > tree is meant (the context suggests free trees). 
However, none of the > available choices produce these numbers.
 >
 > Distinct vertices, free trees: 1,2,7.
 > Distinct vertices, rooted trees: 1,3,16.
 > Identical vertices, free trees: 1,2,3.
 > Identical vertices, rooted trees: 1,2,5.
 >
  > There is a formula given, in Tex, but I can't make sense of it 
either: > "$\frac{n!}{n^2} Sum_{\mu \vdash n} \prod_{j=1}^{\infty} > 
\frac{n^{\mu_j}}{{\mu_j}!(j-1)!^{\mu_j}}$". In the sum, it appears that 
mu > is a simple integer, but inside the product it is treated as a 
sequence.
 >
 > Franklin T. Adams-Watters

  Gee, I'm sorry for the confusion. Some of it is linguistic but there 
may be a math problem.

  I'm not sure what you mean by "free tree" but in graph theory, 
usually, trees are unrooted unless called "rooted". I don't know what 
you mean by "distinct"; probably you mean "labelled". ("Distinct" means 
"different from each other". It makes no sense for a graph to have more 
than one "identical" vertex. If they're identical, they're the same.) 
If you mean that a graph with vertices 1,2,3 and edges 12,13 is 
different from a graph with the same vertices and edges 12,23, then you 
mean "labelled".

  The symbol \vdash means \mu partitions the integer n. That means \mu 
is a sequence $(\mu_1,\mu_2,...)$ such that $\mu_i \geq 0$ and $\sum_i 
i \mu_i = n$ (at least, I hope that's what I meant). If this works, 
then that's what I meant.

  I've just recalculated the actual numbers by looking at the fat trees. 
I get 1,2,10. Here's how:

 n=1: One vertex, partition has one block.

 n=2: Partition {12} (one block): 1 way.
 Partition {1,2} (two blocks), one connecting edge: 1 way.

 n=3: Partition {123}: 1 way.
 Partition {1,2,3}: 3 ways to connect to make a tree.
  Partition {12,3}: There are 2 ways to connect in a treelike pattern: 
add edge 13 or edge 23. There are 2 other similar partitions, {13,2} 
and {23,1}, so we get 6 fat trees here.

  I hope this helps. I'm not sure why you got the numbers you did; maybe 
you've invented new kinds of "fat trees", different from mine. Please 
let me know what's going on! I'm curious.

 Best wishes,
 Tom Zaslavsky


___________________________________________________
Try the New Netscape Mail Today!
Virtually Spam-Free | More Storage | Import Your Contact List
http://mail.netscape.com