<DIV style="FONT-SIZE: 12px; FONT-FAMILY: verdana, arial">
<DIV>
<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>objects of order n with components of the type considered in sequence a_U.</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>objects of order n with components of the type considered in sequence a_L.</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> We consider sequences with repetitions since we have to relabel the components</FONT></DIV>
<DIV><FONT size=2>to form a labeled graph on [n], so identical components become distinct. For example,</FONT></DIV>
<DIV><FONT size=2>examine the trees depicted in figure 2. In this case, a_L(j) = j^{j-2}, and c_4 = 1, c_6 = 2.</FONT></DIV>
<DIV><FONT size=2>There are 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><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>
<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> the partitions with a given number m of parts, or<BR><STRONG>-2-</STRONG> the partitions with parts in a subset S of {1,2,...,n}, or<BR><STRONG>-3-</STRONG> the partitions with distinct parts, or<BR><STRONG>-4-</STRONG> the partitions satisfying <STRONG>-1-</STRONG> and <STRONG>-2-</STRONG>, or<BR><STRONG>-5-</STRONG> the partitions satisfying <STRONG>-1-</STRONG> and <STRONG>-3-</STRONG>, or<BR><STRONG>-6-</STRONG> the 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 we choose how to restrict the partitions to determine</FONT></DIV>
<DIV><FONT size=2> a particular sequence. If we use transforms what changes?</FONT></DIV></DIV>
<DIV><FONT size=2> </FONT></DIV>
<DIV><FONT size=2> The sum of (2) over the partitions of n with exactly m parts, i.e., case <STRONG>-1-</STRONG> , gives</FONT></DIV>
<DIV><FONT size=2><STRONG>A_U</STRONG>(n) equal to all the graphs of order n with exactly m components of the type</FONT></DIV>
<DIV><FONT size=2>considered in </FONT><FONT size=2>sequence a_U, because given a graph G with n vertices and m</FONT></DIV>
<DIV><FONT size=2>components of that kind, </FONT><FONT size=2>the m orders of those components correspond to a</FONT></DIV>
<DIV><FONT size=2>unique partition of n with </FONT><FONT size=2>exactly m parts. The same holds for labeled objects (3).</FONT></DIV>
<DIV><FONT size=2> It </FONT><FONT size=2>is not difficult to see that for </FONT><FONT size=2>the case <STRONG>-2-, </STRONG></FONT><FONT size=2><STRONG>A_U</STRONG> counts </FONT><FONT size=2>unlabeled graphs</FONT></DIV>
<DIV><FONT size=2>with </FONT><FONT size=2>components of orders in S, <STRONG>A_L</STRONG> counts <FONT size=2>labeled graphs </FONT><FONT size=2>with </FONT><FONT size=2>components of</FONT></FONT></DIV>
<DIV><FONT size=2><FONT size=2>orders in S,</FONT>etc.</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 count graphs without components</FONT></DIV>
<DIV><FONT size=2>of order 3 with <STRONG>-2-</STRONG> and S = {2,4,...,n}, we count graphs with components of even</FONT></DIV>
<DIV><FONT size=2>orders with <STRONG>-2-</STRONG> and S = {2k: 1 =< k <= floor(n/2)}, etc.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2> In the sequences below, for the particular case of unicyclic components, we can</FONT></DIV>
<DIV><FONT size=2>see simple formulas </FONT><FONT size=2>corresponding to partitions with 2 parts and 3 parts. Those</FONT></DIV>
<DIV><FONT size=2>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.</FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>I 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. So why not<BR>two people sending data to and organizing the information in such a website?</FONT></DIV>
<DIV><FONT size=2><STRONG>Not a wiki I think!!!</STRONG></FONT></DIV>
<DIV><FONT size=2></FONT> </DIV>
<DIV><FONT size=2>This site could have formulas involving partitions, "multiplication </FONT><FONT size=2>of numbers with two digits",</FONT></DIV>
<DIV><FONT size=2>and references to good introductory articles about "multiplication". Those "topics" appear</FONT></DIV>
<DIV><FONT size=2>appropriate to the naive seqfans. </FONT><FONT size=2>This is the way because </FONT><FONT size=2>when we teach, the target are</FONT></DIV>
<DIV><FONT size=2>the median </FONT><FONT size=2>students, but we must to show the route to the gifted or motivated ones.</FONT></DIV>
<DIV><FONT size=2>Forget long division!</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></DIV></DIV>