Talk:Pólya enumeration theorem

From Wikipedia, the free encyclopedia

Contents

[edit] Expert required

The section "Example computation: enumerating rooted ternary trees" is strange:

  • the definiton of ternary tree doesn't match the image
  • what the heck is "flat tree"?
  • funny language: "a leaf of size zero"

Sorry have to run now, but there is more. `'mikka 02:36, 14 March 2007 (UTC)

Hello there, did you read the caption on the image, which says that leaves (green) are not shown. If you add the leaves, you will see that the definition matches the image (outdegree three, including leaves). I was not able to find the word "flat" in the article. Do you mean planar? You will find the definition of planar trees in any introductory textbook on graph theory. Furthermore, the generating function counts the number of nodes, excluding leaves. A node contributes one to the total and a leaf, zero, hence the phrase "size zero." The use of the word "size" or "size function" is standard terminology from generating functions, again to be found in any introductory textbook on the subject. -Zahlentheorie 14:04, 14 March 2007 (UTC)
Hey, please don't refer me to "intgroductory books". I already know I am an ignoramus. We are talking about the wikipedia article, right? That said, we have to restrict the talk to the article at hand and wikipedia in general, right? I am not asking you to educate me in graph theory, I am too old and lazy to learn something new, that's why I am writing wikipedia :-) That said, back to the problems.
  1. Image: Last time I've read a book in graphs, a leaf is a vertex. On the pic I see graphs on 4 vertices. The blurb about "leaves not shown" I noted as a yet another strange piece.
  2. yes, "planar" (like I said above, I was in a hurry). Please direct me to wikipedia article about "planar trees" Last time I read a book in graph theory about planar graphs I was surprized to learn that all trees are planar, who would believe this?
  3. "leaf of size zero": sorry to insist, but this language is sloppy and good in a chat among experts, but not in an encyclopedia article. There are at least 3 different problems with this phase in our context.
In conclusion, judging your attitude, I would kindly ask to refrain from further answers to me on the topic, if you are going to continue in the same defensive way, and let other experts say. `'mikka 18:21, 14 March 2007 (UTC)

Here is another puzzle:

  1. "The set T3 of rooted ternary trees"
  2. "an element of T3 is either a leaf of size zero, or a node with three children"

And another one: "The slots in this problem are the three slots where the children are attached to their parent node". All my life I thought that "children are attached to their parent node" by edges or arcs, but not by slots.

Now, looking into the intro:

  • "and a generating function f(x, y, ...) of the objects by weight." What is weight and how it is related to generating function? The article "generating function" says nothing about weights.
  • "permutation group" better be linked (done)
  • back to ternary trees: how/what "weight" is to do with them?

I am inclined to insist that this article reads like Turboencabulator. Probably I was mistaken to ask for expert's attention. For an expert all may be OK: a couple of "evident" (to expert) links in a train of logic omitted, no big deal. `'mikka 18:21, 14 March 2007 (UTC)

P.S. The Russian wikipedia version is in a sharp contrast with this one, but don't tell me that it is probably my problem with English language comprehension. `'mikka 18:24, 14 March 2007 (UTC)

Hello there, thanks for the many useful observations, which will lead to a better article. The word slot is used in all of the examples. It's the common term that links them. PET says that if you have a generating function by weight of some objects, and distribute them into some slots, with a group permuting the slots, then you get the generating function of the new class by substituting into the cycle index. That's why a common term is used rather than a more specific one. It's to illustrate the common structure of these problems. E.g. for the tree example the slots are the three locations where subtrees are attached to the parent node. For the colored cube, it's the faces of the cube etc. As for generating functions by weight, these are sums of monomials in some variables, with the power of the respective variable indicating the value of the parameter, and the value of the parameter of the derived class being the sum of the values for the constituents (the objects in the slots). -Zahlentheorie 00:46, 15 March 2007 (UTC)
As a starter of Russian version of this article, I am pleased to hear good words about it. As of English version, I've already corrected and extended references and some other stuff, and there is more to come ;) Maxal (talk) 14:56, 1 February 2008 (UTC)

[edit] Moved knights example to talk page

Wikipedia deserves only the best, and this example is extremely contrived. -Zahlentheorie 15:45, 29 April 2007 (UTC) Deleted from the talk page. -Zahlentheorie 20:08, 29 April 2007 (UTC)


[edit] Moved proof of the theorem to talk page

This proof needs the attention of an expert to provide an introduction, check all the steps, and explain what is being done. -Zahlentheorie 21:41, 18 May 2007 (UTC)

The Pólya enumeration theorem follows from Burnside's lemma, which says that the number of orbits (equivalence classes of filled slot configurations) is the average of the number of elements of BA fixed by a permutation g of G over all permutations g.

Applying the lemma to orbits of weight ω, the number of orbits of this weight is

\frac{1}{|G|} \sum_{g\in G} |\mbox{Fix}_\omega(g)|

where Fixω(g) is the set of functions of weight ω fixed by g.

Summing over all possible weights we have

\sum_{\omega} \omega \frac{1}{|G|} \sum_{g\in G} |\mbox{Fix}_\omega(g)| = \frac{1}{|G|} \sum_{g\in G} \sum_{\omega} \omega |\mbox{Fix}_\omega(g)|.

Let the cycle structure of g be represented by

a_1^{j_1(g)} a_2^{j_2(g)} \cdots a_n^{j_n(g)}.

If g fixes an element of BA then it must be constant on every cycle c of g. The generating function by weight of a cycle c of |c| identical elements from the set of objects enumerated by f(x, y, z, ...) is

f(x^{|c|}, y^{|c|}, z^{|c|}, \ldots). \,\!

It follows that the generating function by weight of the points fixed by g is the product of the above term over all cycles of g, i.e.

\sum_{\omega} \omega |\mbox{Fix}_\omega(g)| = \prod_{c\in g} f(x^{|c|}, y^{|c|}, z^{|c|}, \ldots)

or

f(x, y, z, \ldots)^{j_1(g)} f(x^2, y^2, z^2, \ldots)^{j_2(g)} \cdots f(x^n, y^n, z^n)^{j_n(g)}

and the claim follows.

[edit] Some thoughts on improvement

This is a good article; but I agree with many of the criticisms presented by Mikka. In the philosophy of "edit boldly", I'll try to make these changes, but what follows is my thinking:

Above all, we need a formal mathematical statement of the theorem: something like "Given a set A of cardinality n, a group G which acts on A, a set B, and a weighting function w on B such that w maps each element of B into some ring R[x,y,..], define f(x,y, ...) as sum(b in B, w(b)). Then if we define the generating function g(x,y, ...) by weight of the equivalence classes of B^A under the action of G, then g(x,y,...) = P_G(f(x,y,...), f(x^2,y^2, ...), ..., f(x^n, y^n, ...))".

Given this starting point, I found the "slots into which objects are distributed" metaphor generally confusing; it seems terribly backwards to me as it is used in the examples.

When I read that the "objects" in B (for which we have a counting function) are to be "distributed" into the "slots" of set A (which are to be permuted), my impulse is to imagine that no object from B will be in two slots at once: we seem to be talking about a function /from/ B /into/ A.

But the actual sets under consideration are the elements of B^A: mappings /from/ A /into/ B. In that sense, the "slots" are really being "placed" into "objects" in B. Given some configuration of "slots" from A placed into "objects" of B, we permute the "slots" in A according to the elements of G to form the set of all equivalent configurations (orbits).

Another metaphor that might be more generally used is coloring or labeling: we have a set A of "objects", which will be permuted by G. We have a set B of "colors" or "labels", for which we have a weighting function w. We color or label the elements of A with the elements of B.

In either case, the enumeration theorem is closely related to Burnside's lemma: we start with the set B^A; we form equivalence classes (orbits); and then count these orbits. (Some of the diagrams could be altered (particularly the 3-graph example) to show this more clearly: show all possible maps B^A; show the equivalence classes under the group action; finally, show a unique representative from each the equivalence class).

In Burnside's lemma, the method of counting is indirect: we instead count the elements left unchanged (fixed) by each element g in G. If we think of the "slots" in A as being placed into the various "buckets" of B (rather than the other way round) or "colored" by the elements of B, then it is easy to count these elements given some g in G: each cycle of g corresponds to some set of elements of A. For each cycle, all of those elements /must/ be in the same "bucket" of B (or have the same color of B) for g to leave the result unchanged; and vice versa. So if there are 3 cycles in g and 5 "buckets" in B (or colors in B), then there are 5^3 elements of B^A which are left unchanged by g. And thus follows the whole examination of G by looking at the number of cycles of the elements of G.

The main difference between Burnside's lemma and the enumeration theorem is that the theorem expresses the above in the language of generating functions. Springer Online at http://eom.springer.de/p/p073550.htm has a nice summary that made the whole formula much easier for me to understand (they use R^D instead of B^A, where n is the number of elements in D (the "number of slots" in the current article))

If for the weights of the elements of one takes powers of an independent variable (or the product of powers of several variables), then for
\phi(x) = \sum_{k=0}^{\inf} {a_k x^k}
(the so-called "series that enumerates figures", where ak is the number of elements in R of weight xk) and
\psi(x) = \sum_{k=0}^{\inf} {b_k x^k}
(the so-called "series that enumerates configurations", where bk is the number of classes in RD of weight xk), the following applies, according to Pólya's theorem:
\psi(x) = P_G(\phi(x), \phi(x^2), \ldots, \phi(x^n))

This makes much clearer what the "generating function f(x,y, ...) of the objects by weight" is: it's a statement about how we count elements in the labeling set (R or B). And the result is clearer: given a way of counting the elements in the labeling set R and some group G, we get a generating function that lets us count the equivalence classes we are interested in.

The whole issue of "generating functions" and "weights" and what they mean really needs to be addressed. There currently appears to be no place in Wikipedia where it is clearly stated how a generating function f(x,y, ...) is supposed to be understood as a way of talking about counting elements of some set. Should this be amplified upon here? In the generating function article? In the formal power series article? In a new article?

In the examples, let's be consistent with the statement of the theorem: always clearly identify what are the /elements/ of A, what are the /elements/ of B, and what is the weight function w (it should assign a value to each element of B in a non-arbitrary way). For example, the weight function in the first example is on the set B = {0,1}, where 0 means "0 edges present", 1 means "1 edge is present". The weight function is then w(b) = z^b. /That's/ why we have f(z) = a_0*z^0 + a_1*z^1 = 1 + z; in B, there is one instance of "0 edges present" and 1 instance of "1 edge present".

The "ternary tree" example is really good idea, in that it shows how you can go far beyond a simple application of Burnside's lemma. It also breaks us out of the idea that G always refers to some sort of Euclidean /spatial/ symmetry (which I think often accompanies the use of the term "symmetry"). And it really shows the strength of using generating functions.

But it needs to be edited a bit. I really have no idea what is being stated regarding whether ternary trees or binary trees are planar; but it doesn't matter: it's pretty clear what is meant by "isomorphic ternary trees", and what we want to know is /how to count them/. So really, the rest should just be removed.

I intuitively understood what a ternary tree was by extension of the term binary tree: a rooted tree where every node has (outgoing) degree 0 or 3. But when I looked at the diagram, I thought I might be wrong. Yes, one can eventually figure out what is meant: blue is the root, red is a non-root node, nodes without children are not shown. But this requires a fair amount of consideration to figure out; simply using a larger diagram would make the result more immediate. And really, once I understand the concept, I can already imagine from the text what is meant by "isomorphic"; a diagram is almost unneeded.

It's also unclear how we get the result from the actual statement of the theorem using A, B, G, and w. In the text, we essentially equate both A and B with T3, and G with S_3; and no explicit value is given for w. There are 6 elements in S_3. Given an arbitrary element t of A = T3, what element of A = T3 does each of the elements of S_3 send t to? How should we understand the set of mappings B^A = T3^T3 here? What is w, as applied to the elements of B = T3? How do we show that T(z) = sum(b in B = T3, w(b)), as required by the theorem? A bit more detail would really help in reducing the above confusions.

As regards the proof moved to the Talk Page, all that is required of the weight function is that it map each element in B into "some" commutative ring. That ring could be Z, Z[x], Z[x,y], C, or any commutative ring. The choice of the ring and the mapping is obviously going to be meaningful in terms of understanding the result; but the proof follows in any case. It needs to be made consistent when the symbol "ω" is being used to refer to the weighting /function/ on B, and some particular /value/ in the ring that that the weighting function maps B into. The assertion regarding f(x | c | ,y | c | ,...) needs a bit more explanation. The final step needs to be made clearer than "the claim follows"; we haven't even stated a claim yet!

Anyway, I'll take a stab at these; please feel to comment, revert, add, modify, rant, etc. 71.198.111.245 02:12, 27 August 2007 (UTC)

[edit] Weights

"Suppose you have a set of n slots and a set of objects being distributed into these slots and a generating function f(x, y, ...) of the objects by weight."

The terminology 'weight' seems unclear to me... it is not explained what is meant by weight, nor does it have a link to follow. What is meant by weight, please? --Hirak 99 (talk) 10:44, 1 February 2008 (UTC)

The weight of objects let you distinguish (groups of) them. The simplest "weight" is just constant 1 for every object, so that the weight of a group of objects is the number of elements in this group. Informally speaking, in this case counting of equivalence classes of a certain weight W corresponds to counting of equivalence classes that have exactly W elements. I will elaborate on this in the article. Maxal (talk) 15:13, 1 February 2008 (UTC)

[edit] Spanish references

Does it really make sense to keep Spanish references in this English article? I do not see a point, especially since there is a lot of English references around. So, if there are no objections, I will move those references to Spanish wikipedia and create there a stub for Spanish version of this article. Maxal (talk) 15:02, 1 February 2008 (UTC)