<!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><FONT face=Arial size=2>Neil,<BR></FONT></DIV>
<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 we
have sequences with repetitions.<BR>This is true since when
we relabel components to form a labeled graph on [n] we</FONT></DIV>
<DIV><FONT size=2>make two identical components become distinct. For
example, examine the trees</FONT></DIV>
<DIV><FONT size=2>depicted in figure 2. In this case, a_L(j) = j^{j-2}, and c_4
= 1, c_6 = 2, so the product</FONT></DIV>
<DIV><FONT size=2>above gives 4^{4-2}6^{6-2}^2 = 26,873,856
sequences.</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></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> </DIV>
<DIV><BR> 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.</DIV>
<DIV> </DIV>
<DIV> 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, with components
of the type considered in sequence a_U because</DIV>
<DIV>we have seen that the orders of the components of G correspond to a
unique</DIV>
<DIV>partition of the integer n. The same holds for (3) and
<STRONG>A_L</STRONG>(n).</DIV>
<DIV> </DIV>
<DIV>For example:</DIV>
<DIV> </DIV>
<DIV>A137917 Number of distinct unlabeled graphs with n vertices where all
components<BR> are unicyclic.</DIV>
<DIV>A137916 Number of labeled graphs on [n] with unicyclic
components.</DIV>
<DIV> </DIV>
<DIV><A
href="http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A137917 ">http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A137917
</A></DIV>
<DIV><A
href="http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A137916">http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A137916</A></DIV>
<DIV> </DIV>
<DIV> 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 of the type considered in</DIV>
<DIV>sequence a_U, because given a graph G with n vertices and m components,
the</DIV>
<DIV>m orders of those components correspond to a unique partition of n with
exactly</DIV>
<DIV>m parts. The same holds for (3) and <STRONG>A_L</STRONG>(n).</DIV>
<DIV> </DIV>
<DIV>In general, (but peraphs we can find another cases), we can select a
subset of all the partitions with</DIV>
<DIV> </DIV>
<DIV><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>.</DIV>
<DIV> </DIV>
<DIV><STRONG>Question</STRONG>: We determine a particular
sequence choosing the partitions generated.</DIV>
<DIV>
If we use transforms what changes when we want to determine a</DIV>
<DIV>
particular sequence?</DIV>
<DIV> </DIV>
<DIV>It is not difficult to see that</DIV>
<DIV> </DIV>
<DIV> For the case <STRONG>-2-</STRONG> we have
<STRONG>A_U</STRONG>(n) equal to all the unlabeled graphs of order n with</DIV>
<DIV>components of the type considered in sequence a_U of order in S. The
same holds</DIV>
<DIV>for (3) and <STRONG>A_L</STRONG>(n).</DIV>
<DIV> For the case <STRONG>-3-</STRONG> we have
<STRONG>A_U</STRONG>(n) equal to all the unlabeled graphs of order n with</DIV>
<DIV>components of the type considered in sequence a_U of distinct orders. The
same holds
<DIV>for (3) and <STRONG>A_L</STRONG>(n).</DIV></DIV>
<DIV> For the case <STRONG>-4-</STRONG> we have
<STRONG>A_U</STRONG>(n) equal to all the unlabeled graphs of order n with</DIV>
<DIV>m components of the type considered in sequence a_U of order in S. The
same holds
<DIV>for (3) and <STRONG>A_L</STRONG>(n). </DIV>
<DIV> Idem with respect to the cases
<STRONG>-5-</STRONG> and <STRONG>-6-</STRONG>.</DIV></DIV>
<DIV> </DIV>
<DIV>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.</DIV>
<DIV><A
href="http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A106238">http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A106238</A></DIV>
<DIV><A
href="http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A137918">http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A137918</A><BR><A
href="http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A106834">http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A106834</A></DIV>
<DIV> </DIV>
<DIV>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}.</DIV>
<DIV> </DIV>
<DIV>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}.</DIV>
<DIV> </DIV>
<DIV><A
href="http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A105784">http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A105784</A></DIV>
<DIV><A
href="http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A105820">http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A105820</A></DIV>
<DIV><A
href="http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/"><FONT
color=#000000><A
href="http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A106237">http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/</FONT></A>A106237</A> </DIV>
<DIV><A
href="http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A105786">http://www.research.att.com/cgi-bin/access.cgi/as/njas/<U><FONT
color=#0000ff>sequences/</FONT></U>A105786</A></DIV>
<DIV> </DIV>
<DIV> We should avoid trivial sequences, but we obtain graphs
without components</DIV>
<DIV> of order 3 with <STRONG>-2-</STRONG> and S = {2,4,...,n}. Graphs with
components of even order are</DIV>
<DIV>generated by <STRONG>-2-</STRONG> and S = {2k: 1 =< k <= floor(n/2)},
etc.</DIV>
<DIV> </DIV>
<DIV> For a particular case, i.e., unicyclic components, we
can see simple formulas</DIV>
<DIV>corresponding to partitions with 2 parts and 3 parts is the
sequences A138387</DIV>
<DIV>and A138388. Those formulas can be generalized for other types of
components</DIV>
<DIV>without difficulty.</DIV>
<DIV> </DIV>
<DIV>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.</DIV>
<DIV> </DIV>
<DIV><A
href="http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A138387">http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A138387</A></DIV>
<DIV><A
href="http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A138388">http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/A138388</A><BR>----------------------------------------------------------------------------------------------------------------------</DIV>
<DIV> </DIV>
<DIV>"I feel compelled to take a rare step into the realm of
mathematical<BR>philosophy; you've been warned.</DIV>
<DIV> </DIV>
<DIV>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.</DIV>
<DIV> </DIV>
<DIV>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.</DIV>
<DIV> </DIV>
<DIV>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.</DIV>
<DIV> </DIV>
<DIV>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.</DIV>
<DIV> </DIV>
<DIV>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."</DIV>
<DIV> </DIV>
<DIV> 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.</DIV>
<DIV> Why not two people sending data to and organizing the
information in such a</DIV>
<DIV>website? <STRONG>Not a wiki I think!!!</STRONG>. Information about formulas
involving partitions plus</DIV>
<DIV>the multiplication of numbers with two digits, and references
to good introductory</DIV>
<DIV>articles about "long multiplication" appear appropriate to the
audience of naive</DIV>
<DIV>seqfans. Forget long division!</DIV>
<DIV> This is the way because when we teach, the target are
the median</DIV>
<DIV>students, but we must to show the route to the gifted or motivated ones.
</DIV>
<DIV> </DIV>
<DIV>I implemented the Hindenburg's algorithm in C++. It is showed in</DIV>
<DIV> </DIV>
<DIV><A
href="http://www-cs-staff.stanford.edu/~knuth/fasc3b.ps.gz">http://www-cs-staff.stanford.edu/~knuth/fasc3b.ps.gz</A> pp
7.</DIV>
<DIV> </DIV>
<DIV>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.</DIV>
<DIV> </DIV>
<DIV>Thanks for the paper references.</DIV>
<DIV> </DIV>
<DIV>Any suggestions to improve the math? </DIV>
<DIV> </DIV>
<DIV>Best regards<BR>Washington</DIV>
<DIV> </DIV>
<DIV></FONT> </DIV></FONT></DIV></FONT></DIV></BODY></HTML>