<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-1">
<META content="MSHTML 6.00.6000.16640" name=GENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=#ffffff>
<DIV><FONT face=Arial size=2>
<DIV><FONT face=Arial size=2>Neil,<BR></FONT></DIV>
<DIV><FONT face=Arial size=2>I will send some of my sequences to superseeker. I
am curious to see the output.<BR>Thanks.</FONT></DIV>
<DIV> </DIV>
<DIV><FONT face=Arial size=2>Best regards<BR>Washington</FONT></DIV>
<DIV> </DIV>
<DIV><FONT face=Arial
size=2>--------------------------------------------------------------------------------</FONT></DIV>
<DIV>
<P><FONT face=Arial size=2>Christian,</FONT></P></DIV>
<DIV><FONT face=Arial size=2>"Without access to H&P, I can only go by your
examples and based on those,<BR>I would say the partition formulas you are using
are equivalent to the EULERi and LOG transforms."</FONT></DIV>
<DIV> </DIV>
<DIV><FONT face=Arial size=2>Probably they are. Below I will give some more
examples, but before let us<BR>examine some facts relating graphs to
partitions.</FONT></DIV>
<DIV> </DIV>
<DIV align=justify><FONT face=Arial size=2>Let G be a graph with n nodes. The
orders of the components of G form a unique<BR>partition P of n. If G has c_1
components of order 1, c_2 components of order 2,<BR> ... , and c_n
components of order n, c_1, c_2, ..., c_n >= 0, clearly</FONT></DIV>
<DIV> </DIV>
<DIV><FONT face=Arial size=2> P = c_1 + 2c_2 + ... +
nc_n.
(1)</FONT></DIV>
<DIV> </DIV><FONT face=Arial>
<DIV><BR><FONT face=Terminal><FONT size=2>
+--------------------+<BR>
| 1
1
|<BR>
| / | \ / | \
|<BR> |
2 3 4 2 4 3
|<BR>
| / \ / \
|<BR>
| 5 6 5 6
| <FONT face=Arial><STRONG>==> 6*2 +
4*1.</STRONG></FONT><BR>
|
|<BR>
|
1
| </FONT><FONT size=2><FONT face=Arial>The order of the parts
is immaterial.
Here<BR></FONT>
| / |
\ |
</FONT><FONT size=2><FONT face=Arial>we have n = 16, c_1 = c_2 = c_3 = c_5 =
0,<BR></FONT>
| 2 3
4
| </FONT><FONT size=2><FONT face=Arial> and c_4 = 1, c_6 =
2.<BR></FONT>
+--------------------+</FONT></FONT><BR><FONT
size=2> <STRONG>Fig
1</STRONG>. The orders 6,6, and 4 corresponding to the partition <STRONG>4*1 +
6*2</STRONG>.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV><FONT size=2></FONT>
<DIV align=justify><BR><FONT size=2> On the other hand, P
corresponds to several graphs because two distinct<BR>graphs can have the same
order. The following proposition gives the number of<BR>graphs corresponding to
P for the case of unlabeled components.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2><STRONG>Proposition 1</STRONG>. Let a_U(n) be a sequence that
counts connected
unlabeled<BR>
combinatorial objects. In this case, the partition P of
(1)<BR>
corresponds to</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>prod_{j=1}^n\(C(a_U(j) + c_j -1,
c_j)
(2)</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>graphs of order n.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV align=justify><FONT size=2><STRONG>Proof</STRONG><BR> The
value of (2) is determined only by the parts of P because if c_j =
0,<BR>C(a_U(j) + c_j -1, c_j) = 1.<BR> If c_j = 1, C(a_U(j) +
c_j -1, c_j) = a_U(j). It is clear that a_U(j) is the<BR>number of ways to
choose a component of order j to put in a graph, so the part j<BR>of P
corresponds to a_U(j) distinct graphs. All the components of those
a_U(j)<BR>graphs are the same, except the a_U(j) components of order j that
makes each one<BR>of those a_U(j) graphs different from all the
others.<BR> If cj > 1, we have combinations of a_U(j)
objects with repetitions, whose<BR>number is C(a_U(j) + c_j -1, c_j). So the
partition P corresponds to the number<BR>of graphs given by (2). <STRONG><FONT
size=4>//</FONT></STRONG></FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>Now we turn our attention to the labeled case, where we have
to relabel the<BR>components to form a labeled graph on [n]. See figure
2.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><BR><FONT
size=2>
</FONT><FONT size=2><FONT
face=Terminal>+--------------------+
+--------------------+<BR>
| 1
1
|
| 16
15
|<BR>
| / | \ / | \
|
| / | \ / | \
|<BR> |
2 3 4 2 3 4
| | 12
7 8 2 3 4
|<BR>
| / \ / \
|
| / \ / \
|<BR>
| 5 6 5 6
| ==> | 11
6 5 13
|<BR>
|
|
|
|<BR>
|
1
|
|
1
|<BR>
| / |
\
|
| / |
\
|<BR>
| 2 3
4
|
| 10 9 14
|<BR>
+--------------------+
+--------------------+</FONT><BR> <STRONG>
Fig 2.</STRONG> The labels can change in many ways. Two identical trees
on<BR>
the left become distinct. </FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><BR><FONT size=2><STRONG>Proposition 2</STRONG>. Let a_L(n) be a sequence
that counts connected
labeled<BR>
combinatorial objects. In this case, the partition P of
(1)<BR>
corresponds to</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>n!prod_{j=1}^n\{ \frac{ a_L(j)^{c_j} } { j!^{c_j}c_j! }
}
(3)</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>graphs of order n.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2><STRONG>Proof</STRONG><BR> The partition P
corresponds to several sequences of labeled components whose<BR>orders
correspond to the parts of P. The number of those sequences is</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2> prod_{j=1}^n\,{
a_L(j)^{c_j} }.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2> The expression above is correct because
there are sequences with repetitions.<BR>We have to relabel the components to
form a labeled graph on [n], so two<BR>identical components become
distinct.<BR> For example, examine the trees depicted in
figure 2. In this case, a_L(j) =<BR>j^{j-2}, and c_4 = 1, c_6 = 2, so the
product above gives 4^{4-2}6^{6-2}^2 =<BR>26,873,856.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2> Note that if there are c_j parts j in P,
there are also c_j components of<BR>order j in each sequence. Note also that if
c_j = 0, a_L(j)^{c_j} = 1.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2> The components of a sequence S are
relabeled forming distinct graphs on<BR>[n]. To determine the number of those
graphs, we begin choosing any component K<BR>of S. Let j be the number of
vertices of K. To choose K in S is equivalent to<BR>choose the part j of P, or
the summand c_jj of P. All the graphs corresponding<BR>to S have c_j components
of order j. The summand c_jj corresponds to</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2> C(n, j)C(n-j, j) ... C(n-(c_j - 1)j,
j)
n!<BR> -----------------------------------------------
= -------------- graphs because we can
<BR>
c_j!
j!^{c_j}c_j!</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>choose the labels of the first component in C(n, j) ways, we
can choose the labels of </FONT></DIV>
<DIV><FONT size=2>the second component in C(n-j, j) ways, etc. We divide by c_j!
because the product</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2> C(n, j)C(n-j, j) ... C(n-(c_j-1)j,
j)</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>considers the c_j! permutations of components, and those
permutations form a<BR>unique graph. Proceeding with all summands of P, we can
write a product of<BR>binomial coefficients, that simplifies giving the total
number of graphs on [n]<BR>corresponding to the sequence S
as<BR>
n!<BR>
---------------------------------
.<BR>
prod_{j=1}^n\,j!^{c_j}c_j!<BR></FONT></DIV>
<DIV><FONT size=2>Note that j!^{c_j}c_j! = 1 if c_j = 0.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>We obtain (3) multiplying the number of sequences by the
number of graphs that<BR>corresponds to each sequence.</FONT><FONT
size=4><STRONG> //</STRONG></FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><BR><FONT size=2> Now let <STRONG>A_U</STRONG>(n) be a
sequence that counts unlabeled combinatorial objects, and<BR>let
<STRONG>A_L</STRONG>(n) be a sequence that counts labeled combinatorial
objects.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2> The sum of (2) over all the partitions of n
gives <STRONG>A_U</STRONG>(n) equal to all the graphs<BR>G of order n, because
we have seen that the orders of the components of G correspond<BR>to a unique
partition of the integer n. The same holds for (3) and
<STRONG>A_L</STRONG>(n).</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>For example:</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>A137917 Number of distinct unlabeled graphs with n
vertices where all components<BR> are
unicyclic.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>A137916 Number of labeled graphs on [n] with unicyclic
components.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><A href=""><FONT
size=2>http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A137917</FONT></A><FONT
size=2> ,<BR></FONT><A href=""><FONT
size=2>http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A137916</FONT></A><FONT
size=2> .</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2> The sum of (2) over the partitions of n
with exactly m parts, gives <STRONG>A_U</STRONG>(n) equal<BR>to all the graphs
of order n with exactly m components, because given a graph G<BR>with n vertices
and m components, the m orders of those components correspond<BR>to a unique
partition of n with exactly m parts. The same holds for (3) and
<STRONG>A_L</STRONG>(n).</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>In general we can select a subset of all the partitions
with</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2><STRONG>-1-</STRONG> partitions with a given number m of
parts, or<BR><STRONG>-2-</STRONG> partitions with parts in a subset S of
{1,2,...,n}, or<BR><STRONG>-3-</STRONG> partitions with distinct parts,
or<BR><STRONG>-4-</STRONG> partitions satisfying <STRONG>-1-</STRONG> and
<STRONG>-2-</STRONG>, or<BR><STRONG>-5-</STRONG> partitions satisfying
<STRONG>-1-</STRONG> and <STRONG>-3-</STRONG>, or<BR><STRONG>-6-</STRONG>
partitions satisfying <STRONG>-2-</STRONG> and
<STRONG>-3-</STRONG>.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2><STRONG>Question</STRONG>: In terms of partitions to determine
a particular sequence we
choose<BR> how to restrict
the partitions generated. If we use transforms
what<BR>
changes?</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>It is not difficult to see that</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2> For the case <STRONG>-2-</STRONG> we have
<STRONG>A_U</STRONG>(n)|<STRONG>A_L</STRONG>(n) equal to all the
unlabeled|labeled<BR>graphs of order n with components of order in S. For the
case <STRONG>-3-</STRONG> we
have<BR><STRONG>A_U</STRONG>(n)|<STRONG>A_L</STRONG>(n) equal to all the
unlabeled|labeled graphs of order n with components<BR>of distinct orders. For
the case <STRONG>-4-</STRONG> we have
<STRONG>A_U</STRONG>(n)|<STRONG>A_L</STRONG>(n) equal to all
the<BR>unlabeled|labeled graphs of order n with m components of order in S, and
so on.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>Examples of <STRONG>-1-</STRONG><BR>A106238 Triangle read
by rows: T(n,m) = number of unlabeled digraphs of order
n,<BR> with m strongly connected
components.<BR>A137918 Array read by columns: T(n,m) = number of unlabeled
graphs with n<BR> vertices and m
unicyclic components.<BR>A106834 Triangle read by rows: T(n, m) = number of
painted forests on labeled<BR> vertex
set [n] with m trees. Also number of painted forests with
exactly<BR> n - m edges.<BR></FONT><A
href=""><FONT
size=2>http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A106238</FONT></A><BR><A
href=""><FONT
size=2>http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A137918</FONT></A><BR><A
href=""><FONT
size=2>http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A106834</FONT></A></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>Example of <STRONG>-2-</STRONG><BR>A105784 Number of
different forests of unrooted trees, without
isolated<BR> vertices, on n labeled
nodes.<BR>We have S = {2,...,n}.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>Examples of <STRONG>-4-</STRONG><BR>A105820 Triangle
giving the numbers of different unlabeled forests of m
trees<BR> without isolated
vertices.<BR>A106237 Triangle of the numbers of different forests with m
trees having distinct<BR>
orders.<BR>A105786 Triangle of the numbers of different forests of m
unrooted trees of<BR> smallest order
2, i.e. without isolated vertices, on n labeled nodes.<BR>We have S =
{2,...,n}.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><A href=""><FONT
size=2>http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A105784</FONT></A><BR><A
href=""><FONT
size=2>http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A105820</FONT></A><BR><A
href=""><FONT
size=2>http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A106237</FONT></A><BR><A
href=""><FONT
size=2>http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A105786</FONT></A></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2> We should avoid trivial sequences, but we
obtain triangle free graphs with<BR><STRONG>-2-</STRONG> and S = {2,4,...,n}.
Graphs with components of even order are generated by<BR><STRONG>-2-</STRONG>
and S = {2k: 1 =< k <= floor(n/2)}, etc.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2> For a particular case, i.e., unicyclic
components, we can see that simple<BR>formulas corresponding to partitions with
2 parts and 3 parts are easily obtained.<BR>Those formulas can be generalized
for other types of components without difficulty.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>Examples:<BR>A138387 Numbers of unlabeled graphs with n
vertices and 2 unicyclic components.<BR>A138388 Numbers of unlabelled
graphs with n vertices and 3 unicyclic components.<BR></FONT><A href=""><FONT
size=2>http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A138387</FONT></A><BR><A
href=""><FONT
size=2>http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A138388</FONT></A></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT
size=2>----------------------------------------------------------------------------------------------------------------------</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>"I feel compelled to take a rare step into the realm of
mathematical<BR>philosophy; you've been warned.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>A transform is basically a function of sequences. A thing that
maps one<BR>sequence to another. It is not the algorithm used, but the mapping
itself.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>One can multiply through successive addition, the way they
taught<BR>you in school or some fancy method in a high speed computer chip.
As<BR>long as it gives the same answer, it's multiplication. The same is
true<BR>of any of these transforms.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>What you have shown in the examples is the same mapping as the
transforms,<BR>so it is just another expression (or algorithm) for the same
transform.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>Just as a new student may benefit from a demonstration of
multiplication<BR>as successive addition before learning a more efficient
algorithm, I<BR>think there may be benefits to presenting these transforms
through<BR>partition formulas, perhaps on a webpage illustrating this
connection<BR>would be nice if someone wanted to create one. Maybe it could be
hosted<BR>at the OEIS or a math site like mathworld.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>When I started playing with these formulas in the 90s, I wrote
programs<BR>to implement them that involved enumerating all partitions before
I<BR>read about more efficient techniques. The techniques should be
easy<BR>enough to implement in any programming language."</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>Nice text, almost all of it, verbatim, could be in a webpage
like that you mention.<BR>I think that some of the stuff that we wrote in those
messages could be there. I<BR>speak Portuguese, so I do not write very well in
English. Besides that, I am a<BR>Computer Science teacher, so my text frequently
will deserve some edit. Why not<BR>two people sending data to and organizing the
information<BR>in such a website? <STRONG>Not a wiki I think!!!</STRONG>
Formulas involving partitions plus multiplication</FONT></DIV>
<DIV><FONT size=2>of numbers with two digits, and reference to good
introductory articles about multiplication</FONT></DIV>
<DIV><FONT size=2>appear appropriate. This is the way because when we teach, the
target are the median</FONT></DIV>
<DIV><FONT size=2>students, but we must to show the route to the gifted or
motivated ones. Long division forget!</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>I implemented the Hindenburg's algorithm in C++. It is showed
in</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><A href=""><FONT
size=2>http://www-cs-staff.stanford.edu/~knuth/fasc3b.ps.gz</FONT></A><FONT
size=2> pp 7.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>This method was discovered in 1779 but it is efficient and
generates partitions<BR>with several kinds of restrictions. This is nice because
in many instances we do<BR>not have to generate all the partitions.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>Thanks for the paper references.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>Any suggestions to improve the math? </FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>Best regards<BR>Washington</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV></FONT> </DIV></FONT></DIV></BODY></HTML>