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