[seqfan] Asymptotic pattern in columns of "A005646 triangle"
Robert Munafo
mrob27 at gmail.com
Tue Dec 29 18:17:00 CET 2009
Franklin,
Your questions about the bottom of each column are interesting. I take it
that you are interested in seeing if there is asymptotic behaviour to the
bottom-most J terms of column J, or something like that. The result would be
similar to the appearance of the first J Catalan numbers (A000108) in row J
of the height-limited binary trees (A052154 and A137560, which are also
"Mandelbrot-related polynomials", see
http://mrob.com/pub/math/seq-a052154.html#trees )
Those columns definitely seem a bit hard to study computationally, as you
pointed out, because the relation N<=2^R allows N to grow so quickly. We
need to answer the questions:
What are the most number of objects that can be classified with the union
of R binary partitions? (Simple, 2^R and in exactly one way)
Considering the near-misses 2^R-1, 2^R-2, etc, and how many ways can sets
of each of those sizes be classified by R partitions?
(And thanks for the web-page correction, always appreciated!)
On Tue, Dec 29, 2009 at 06:21, <franktaw at netscape.net> wrote:
> Looking at your web site, it appears that the size 6 line graph is
> mislabeled. It should be f-d-b-a-c-e, not f-e-d-c-b-a.
>
> It feels like I can almost prove this, but the final result eludes me. It
> will suffice to prove that there must always (for R = N-1 > 0) be one
> classification that distinguishes a single point. The result then follows
> by induction - remove the point, find the graph for the remainder by
> induction, and there will be one point that is not distinguished from the
> removed point; join the edge to that point.
>
> -----
> I'm also interested in a question that is much less approachable with the
> development path you are following. That is what happens at the "bottom" of
> each column -- just before it becomes zeros. Does this have a limit? If
> so, it would be 1,1,3,...., reading up the columns. You would have to go to
> at least N=14 to get a clue to whether anything of this sort is happening
> (presumably the cases N=15 and N=16 can readily be shown to be 1).
>
> One can also ask about the column sums: 1,1,2,10,???
>
> Franklin T. Adams-Watters
>
> -----Original Message from: Robert Munafo
> Andrew Weimholt and I have been working on A005646. Franklin T.
> Adams-Watters suggested the importance of the triangle:
>
> N=1 1
> N=2 0 1
> N=3 0 0 1
> N=4 0 0 1 2
> N=5 0 0 0 3 3
> N=6 0 0 0 3 17 6
> N=7 0 0 0 1 36 74 11
> N=8 0 0 0 1 60 573 358 23
> N=9 0 0 0 0 56 2802 7311 1631 47
> N=10 0 0 0 0 50 10087 107938 83170 7563 106
>
> I've copied in row 10 from a later post - FTAW.
>>
>
> The main diagonal suggests a relation to sequence A000055, unlabaled
> unrooted trees.
>
> [...]
>
--
Robert Munafo -- mrob.com
More information about the SeqFan
mailing list