Enumeration formulas involving partitions
Washington
webonfim at bol.com.br
Sat May 10 06:06:07 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)
graphs of order n.
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)
graphs of order n.
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} }.
The expression above is correct because there are sequences with repetitions.
We have to relabel the components to form a labeled graph on [n], so two
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, so the product above gives 4^{4-2}6^{6-2}^2 =
26,873,856.
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 .
The sum of (2) over the partitions of n with exactly m parts, gives A_U(n) equal
to all the graphs of order n with exactly m components, because given a graph G
with n vertices and m components, the m orders of those components correspond
to a unique partition of n with exactly m parts. The same holds for (3) and A_L(n).
In general we can select a subset of all the partitions with
-1- partitions with a given number m of parts, or
-2- partitions with parts in a subset S of {1,2,...,n}, or
-3- partitions with distinct parts, or
-4- partitions satisfying -1- and -2-, or
-5- partitions satisfying -1- and -3-, or
-6- partitions satisfying -2- and -3-.
Question: In terms of partitions to determine a particular sequence we choose
how to restrict the partitions generated. If we use transforms what
changes?
It is not difficult to see that
For the case -2- we have A_U(n)|A_L(n) equal to all the unlabeled|labeled
graphs of order n with components of order in S. For the case -3- we have
A_U(n)|A_L(n) equal to all the unlabeled|labeled graphs of order n with components
of distinct orders. For the case -4- we have A_U(n)|A_L(n) equal to all the
unlabeled|labeled graphs of order n with m components of order in S, and so on.
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 obtain triangle free graphs with
-2- and S = {2,4,...,n}. Graphs with components of even order are generated by
-2- and S = {2k: 1 =< k <= floor(n/2)}, etc.
For a particular case, i.e., unicyclic components, we can see that simple
formulas corresponding to partitions with 2 parts and 3 parts are easily obtained.
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. Why not
two people sending data to and organizing the information
in such a website? Not a wiki I think!!! Formulas involving partitions plus multiplication
of numbers with two digits, and reference to good introductory articles about multiplication
appear appropriate. 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. Long division forget!
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/20080510/3b483ec0/attachment-0001.htm>
More information about the SeqFan
mailing list