Enumeration formulas involving partitions

[webonfim]

I appreciate your inform about transforms. That is new to me.  I found in chapter 1, page 8 of “Harary and Palmer” the EGFs G(x) and C(x)
for labeled graphs and labeled connected graphs, and the relation

1 + G(x) = e^{C(x)}             (1.2.6)

that is probably related to the logarithm transform that you mention.

Below we can see two examples involving the sequences that you mention in your explanations about transforms, namely A001349 unlabeled connected graphs, and A001187 labeled connected graphs. Yesterday I made them.

The first example shows that problems that are resolved with the inverse Euler transform can also be resolved by a sum over partitions. The second example shows that problems that are resolved with the logarithm transform can also be resolved by a sum over partitions.  (Searches in OEIS with some terms indicate that the sequences corresponding to the examples do not appear in OEIS.)

Example 1) Number of unlabeled graphs on n nodes with m connected components.
offset 0
Formula
Sum over the partitions of n with exactly m parts
c_1 + 2c_2 + 
 + nc_n,  c_1, c_2, ... , c_n >= 0;  of

\prod_{j=1}^n\,{ C(A001349(j)+ c_j –1, c_j}

Triangle begins
1,
1,
1, 1
2, 1, 1
6, 3, 1, 1
21, 8, 3, 1, 1
112, 30, 9, 3, 1, 1
853, 145, 32, 9, 3, 1, 1

The sum of the terms of the m_th line is equal to A000088(m).

Example 2) Number of graphs on n labeled nodes with m connected components
offset 0
Formula
Sum over the partitions of n with exactly m parts
c_1 + 2c_2 + 
 + nc_n,  c_1, c_2, ... , c_n >= 0;  of

n!\prod_{j=1}^n\,{\frac{ A001187(j)^{c_j}} {j!^{c_j}c_j!}}

Triangle begins
1,
1,
1, 1
4, 3, 1
38, 19, 6, 1
728, 230, 55, 10, 1
26704, 5098, 825, 125, 15, 1

The sum of the terms of the m_th line is equal to A006125(m).
----------------------------------------------------------------------------

So anybody can use those formulas because they are simple, no GFs, etc. If one has the ability to use transforms, the formulas can be used to check the results so obtained. I am thinking in implementation errors like overflow of values and the like.

Now, at what extent those “partition formulas” can do what those transforms do? Let me make some questions in this direction.

The mentioned transforms allowed one to count graphs with components of two (or more) “types”. For example graphs with trees and unicycles?
I guess they do. If this is true they are superior to the formulas in this aspect.

Those transforms allowed one to count graphs with restrictions on the order and number of components? If this is true, it is easy to do that particularly concerning the inverse Euler transform?

----------------------------------------------------------------------------

I always enjoyed when I visited the site
http://www.research.att.com/~njas/sequences/transforms.html. I did it three or four times I think. Once I went to the task of extend the sequence A001429 with formula a(n) = A068051(n) - A027852(n) - A000081(n). I worked well with A027852 but I cannot understand the DIK transform, so I did not extend A001429. When that happened I almost sent an Email to you to help me with the "DIK" transform. Now I am happy to talk with you.

Washington

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20080503/4649d291/attachment-0001.htm>