Talk:Pólya enumeration theorem

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)

With you permission I will continue the approach via colored permutations introduced to another section below.

Take now $\sum \ of\ all\ colored\ permutations\ like\ would\ be\ \color {red}c_{1}\color {green}c_{1}\color {blue}c_{1}\color {green}c_{3}$ and re-groupe it like

$\sum of\ colored\ permutations\ like\ (\color {red}c_{1}\color {black}+\color {green}c_{1}\color {black}+\color {blue}c_{1}\color {black})\cdot (\color {red}c_{1}\color {black}+\color {green}c_{1}\color {black}+\color {blue}c_{1}\color {black})\cdot (\color {red}c_{1}\color {black}+\color {green}c_{1}\color {black}+\color {blue}c_{1}\color {black})\cdot (\color {red}c_{3}\color {black}+\color {green}c_{3}\color {black}+\color {blue}c_{3}\color {black})$

We build now a generating polynomial by formally replacing in the above expression colored cycles with "counters"

$\sum of\ factors\ like\ (r+g+b)\cdot (r+g+b)\cdot (r+g+b)\cdot (r^{3}+g^{3}+b^{3})$

the exponents of the "counters" r, g, b are not counting only the length of cycles but also indicate the distribution of colors on the colored cube.

For our cube, the generating polynomial has 28 terms. Suppose we want to know the number of colorings depending on one color - the other not being specified. We take $g=b=1$ (the so called zero weight) and we obtain :

$r^{6}+2r^{5}+6r^{4}+10r^{3}+16r^{2}+12r+10$ 

10 stands here for 10 different colorings using only g and b. Hubby56 (talk) 09:34, 27 January 2021 (UTC)

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)

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 $B^{A}$ fixed by a permutation g of G over all permutations g.

Applying the lemma to orbits of weight $\omega$, the number of orbits of this weight is

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

where ${\mbox{Fix}}_{\omega }(g)$ is the set of functions of weight $\omega$ 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 $B^{A}$ 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.

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 $a_{k}$ is the number of elements in $R$ of weight $x^{k}$) and

$\psi (x)=\sum _{k=0}^{\inf }{b_{k}x^{k}}$

(the so-called "series that enumerates configurations", where $b_{k}$ is the number of classes in $R^{D}$ of weight $x^{k}$), 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 "$\omega$" 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)

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)

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)

Slots vs. Colorings

Google on "polya enumeration theorem slots". 829 hits (with many based on a mismatching of "poly(A)" for "polya", and the term "slot blot" for "slot"). Alternatively, google on "polya enumeration theorem coloring": 83,100 hits. I would propose that whatever its subjective merits for some readers, the "objects to be placed into slots" and "slots (which will later have objects placed in them)" metaphor is idiosyncratic and detrimental to this article. Instead, the content should be phrased so as to conform to the more common metaphor of "colors" and "colorings". Chas zzz brown (talk) 06:14, 8 November 2008 (UTC)

The problem with this is that the coloring metaphor only applies in a very limited way to graph enumeration and not at all to tree enumeration. Describing graph enumeration in terms of colorings seems highly contrived. The slot metaphor encompasses these two important cases. The bar of adjacent slots is what the permutation group acts on. It permutes the slots. This is the common fact that links these seemingly quite different examples. Also, colorings lend themselves to cases where the objects being distributed all have the same weight. This is not always the case. (Consider molecules, for example.) -Zahlentheorie (talk) 22:38, 8 November 2008 (UTC)

Don't get me wrong - I agree that the coloring metaphor has its limitations; and that for many applications, slots which will have objects placed in them from some set (with replenishment) can be a good one. But my point was not that the metaphor of slots and objects is an inappropriate or "bad" metaphor; but that it is demonstrably very unusual for an introductory article. This makes it difficult to integrate this article with most other treatments I have seen of the subject; and I would maintain that that is sufficient reason to discourage its use.

As regards whether this article should initially focus on graph enumeration, I would disagree. After all, we don't start explaining group theory by giving examples from Galois theory or topological groups, we start with simple figures being rotated in the Euclidean plane and use the accompanying terminology of "symmetry"; despite the fact that most of the theory was developed for the former applications rather than the latter. Ultimately, I would like to see this article proceed from the simplest coloring examples which are most accessible, and then to the "pure" notion of the theorem in terms of equivalence classes under the action of a group G (and not a group A, another idiosyncrasy) of mappings from one set into another; and then proceed to more complex notions such as the enumeration of graphs. Chas zzz brown (talk) 00:59, 9 November 2008 (UTC)

Unfortunately I don't have the time for a detailed reply at the moment, but as for idiosyncracies like the group A, these are not mine. If you look at the history of the article you'll see that I was using G throughout. Then another contributor added content that uses A, so I re-worked the article to make the notation consistent. I do suggest you study the evolution of the article before making changes. Zahlentheorie (talk) 00:28, 10 November 2008 (UTC)

Many changes made for readability

I am a mathematics professor, and I decided to use this article for my class. However, the article was very confusing in its old form and came across as too technical. I edited the article to make it more readable. Greg Kuperberg (talk) 23:43, 26 May 2010 (UTC)

Mistake in the Proof of theorem?

I do not think I agree with the sentence:

"The element g fixes an element of $Y^{X}$ if and only if it is constant on every cycle q of g."

For example, if X={red,blue}, then which element is fixed by g=(1)(2)...(n)=id ? Note that both $f_{1}$ with $f_{1}$(y)=red for all y in Y and $f_{2}$ with $f_{2}$(y)=blue for all y in Y are constant in every cycle q of g.

Bilingsley (talk) 14:30, 22 January 2014 (UTC)

First of all, a minor point: $Y^{X}$ consists of all functions from X to Y, and we think of Y as the set of colors and X as the set of objects to be colored. Second, the statement you question is indeed correct. If g=(1)(2)...(n)=id, then every element of $Y^{X}$ is fixed by g (the identity doesn't move anything). And every element of $Y^{X}$ is constant on every cycle q of g, since all these cycles have size 1 and every function is constant on every 1-element set. AxelBoldt (talk) 01:30, 21 November 2015 (UTC)

Take an uncolored permutation, e.g. $\sigma =(A)(B)(C)(D,E,F)$. Suppose we can color permutations i.e. elements in the same cycle have the same color.

Then, for each colored $\sigma _{c}$, e.g. $\sigma _{c}=\color {red}(A)\color {green}(B)\color {blue}(C)\color {green}(D,E,F)$ we associate a colored partition $|\ \color {red}A}\ |\ {\color {green}B,D,E,F}\ |\ {\color {blue}C\ |$ that is fixed by $\sigma =(A)(B)(C)(D,E,F)$.

Different colorings of $\sigma =(A)(B)(C)(D,E,F)$ produces different colored partitions.

Reversely, given a colored partition eg. $|\ \color {red}A,B\ |\ \color {green}C,D,E,F\ |$ we observe that, to be fixed by fixed by $\sigma$, the color must be constant over a cycle.

Thus, there is a coloring $\sigma _{c}=\color {red}(A)(B)\color {green}(C)(D,E,F)$ that produces the given partition.

In conclusion, there is a one-to-one correspondence between colorings of a permutation and colored partitions fixed by that permutation. Hubby56 (talk) 12:28, 21 January 2021 (UTC)