组合数学 (Fall 2011)/Pólya's theory of counting and W.D. Hamilton: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
 
imported>Macdonald-ross
(prose...)
 
Line 1: Line 1:
== Groups ==
'''William Donald Hamilton''' [[Royal Society|FRS]] (1 August 1936 – 7 March 2000) was an [[English people|English]] [[evolutionary biology|evolutionary biologist]] whom [[Richard Dawkins]] praised as one of the greatest [[evolution]]ary theorists of the 20th century.<ref>[http://www.edge.org/3rd_culture/hamilton/hamilton_index.html Obituary by Richard Dawkins – ''The Independent'' – 10 March 2000]</ref>
A group <math>(G,\cdot)</math> is set <math>G</math> along with a binary operator <math>\cdot</math> which satisfies the following axioms:
* closure: <math>\forall g,h\in G, g\cdot h \in G</math>;
* associativity: <math>\forall f,g,h\in G, f\cdot(g\cdot h)=(f\cdot g)\cdot h</math>;
* identity: there exists a special element <math>e\in G</math>, called the '''identity''', such that <math>e\cdot g=g</math> for any <math>g\in G</math>;
* inverse: <math>\forall g\in G</math>, there exists an <math>h\in G</math> such that <math>g\cdot h=e</math>, and we denote that <math>h=g^{-1}</math>.


=== Permutation groups===
Hamilton became famous through his [[Theory|theoretical]] work on [[kin selection]] and [[altruism]]. He explained its [[Genetics|genetic]] basis, and this was a key part of the  gene-centered view of [[evolution]]. In doing this, he became one of the forerunners of [[sociobiology]], as popularized by [[E.O. Wilson]]. Hamilton was certainly a big influence on Dawkins. He also published important work on [[sex ratio]]s and the [[evolution of sex]]. From 1984 to his death in 2000, he was the [[Royal Society]] Research Professor at [[Oxford University]]. He died of [[malaria]] contracted in the [[Democratic Republic of the Congo]].


==== Cycle decomposition ====
== Hamilton's equation ==
Hamilton's equation describes whether or not a gene for altruistic behaviour will spread in a population.<ref>Hamilton W.D. 1996. ''Narrow roads of geneland: the collected papers of W.D. Hamilton'', vol 1. Freeman, Oxford.</ref> The gene will spread if '''r'''x'''b''' is greater than '''c''':
:<math>rb > c \ </math>   
where:
* <math>c \ </math> is the reproductive cost to the altruist,
* <math>b \ </math> is the reproductive benefit to the recipient of the altruistic behavior, and
* <math>r \ </math> is the probability, above the population average, of the individuals sharing an altruistic gene – the "degree of relatedness".


=== Group action ===
== Collected papers ==
{{Theorem|Definition (group action)|
Hamilton started to publish his collected papers starting in 1996, with short essays giving each paper context. He died after the preparation of the second volume, so the commentaries for the third volume came from his coauthors.
:A '''group action''' of a group <math>G</math> on a set <math>X</math> is a binary operator:
::<math>\circ:G\times X\rightarrow X</math>
:satisfying:
:* Associativity: <math>(g\cdot h)\circ x=g\circ (h\circ x)</math> for all <math>g,h\in G</math> and <math>x\in X</math>;
:* Identity: <math>e\circ x=x</math> for all <math>x\in X</math>.
}}


==== Example: coloring a necklace ====
* Hamilton W.D. 1996. ''Narrow roads of gene land vol. 1: Evolution of social behaviour''. Freeman, Oxford. ISBN 0-7167-4530-5
Suppose a necklace is made of <math>n</math> beads, each with one of the <math>m</math> colors. Formally, a necklace is an assignment <math>x:[n]\rightarrow[m]</math> of <math>m</math> colors to <math>n</math> positions. Let <math>X=\{x:[n]\rightarrow[m]\}</math> be the set of all such assignments.
* Hamilton W.D. 2002. ''Narrow roads of gene land vol. 2: Evolution of sex''. Oxford University Press, Oxford. ISBN 0-19-850336-9
* Hamilton W.D. 2005. ''Narrow roads of gene land, vol. 3: Last words'' (with essays by coauthors, ed. M. Ridley). Oxford University Press, Oxford. ISBN 0-19-856690-5


For example, when <math>n=4</math> and <math>m=2</math>, <math>X</math> contains all possible 2-colorings (say red and blue) of 4 positions.
== References ==
:<math>X=\{{\color{blue}bbbb}, {\color{blue}bbb}{\color{red}r}, {\color{blue}bb}{\color{red}r}{\color{blue}b}, {\color{blue}bb}{\color{red}rr}, {\color{blue}b}{\color{red}r}{\color{blue}b}{\color{red}r}, {\color{blue}b}{\color{red}rr}{\color{blue}b}, {\color{blue}b}{\color{red}rrr},  {\color{red}r}{\color{blue}bbb}, {\color{red}r}{\color{blue}bb}{\color{red}r}, {\color{red}r}{\color{blue}b}{\color{red}r}{\color{blue}b}, {\color{red}r}{\color{blue}b}{\color{red}rr}, {\color{red}rr}{\color{blue}bb}, {\color{red}rr}{\color{blue}b}{\color{red}r}, {\color{red}rrr}{\color{blue}b}, {\color{red}rrrr}\}</math>
{{Reflist}}


We consider two kinds of symmetric operations on necklaces:
{{DEFAULTSORT:Hamilton, William Donald}}
* Rotation: the corresponding group is the cyclic group <math>C_n</math>.
[[Category:1936 births]]
* Rotation and reflection: the corresponding group is the dihedral group <math>D_n</math>.
[[Category:2000 deaths]]
 
[[Category:English mathematicians]]
Mathematically, these operations on necklaces are described as group actions on <math>X</math>. Recall that each member <math>x\in X</math> is an <math>m</math>-coloring <math>x:[n]\rightarrow[m]</math> of <math>n</math> positions. Suppose the permutation group is <math>G</math>, for any <math>\pi\in G</math> and any <math>x\in X</math>, the group action <math>\pi\circ x</math> is naturally defined as such:
[[Category:Geneticists]]
:<math>(\pi\circ x)(i)=x(\pi(i))</math>.
[[Category:English evolutionary biologists]]
 
[[Category:Fellows of the Royal Society]]
== Burnside's Lemma ==
 
=== Orbits ===
Let <math>G</math> be a permutation group acting on a set <math>X</math>. Let <math>\pi\in G, x\in X</math>.
* The '''invariant set''' of <math>\pi</math>:
::<math>X_\pi=\{x\in X\mid \pi\circ x=x\}</math>.
* The '''stabilizer''' of <math>x</math>:
::<math>G_x=\{\pi\in G\mid \pi\circ x=x\}</math>.
* The '''orbit''' of <math>x</math> under action of <math>G</math>:
::<math>Gx=\{\pi\circ x\mid \pi\in G\}</math>.
 
We think of <math>X</math> as a set of configurations which we may count up to certain symmetry induced by the group action.
 
=== Counting orbits===
 
{{Theorem|Lemma|
:Let <math>G</math> be a permutation group acting on a set <math>X</math>. For any <math>x\in X</math>,
::<math>|G_x||Gx|=|G|\,</math>.
}}
{{Proof|
Recall that the orbit <math>Gx=\{\pi\circ x\mid \pi\in G\}</math>. Suppose that <math>Gx=\{x_1,x_2,\ldots,x_t\}</math>. Then there exist a set <math>P=\{\pi_1,\pi_2,\ldots,\pi_t\}</math> of permutations such that <math>\pi_i\circ x=x_i\,</math> for <math>i=1,2,\ldots,t</math>. We construct a bijection between <math>G</math> and <math>P\times G_x</math>, which will prove the lemma.
 
For any <math>\pi\in G</math>, it holds that <math>\pi\circ x=x_i</math> for some <math>x_i</math>, and since <math>\pi_i\circ x=x_i</math>, we have
<math>\pi_i\circ x=\pi\circ x</math>, hence
:<math>(\pi_i^{-1}\cdot\pi)\circ x=\pi_i^{-1}\circ(\pi\circ x)=\pi_i^{-1}\circ(\pi_i\circ x)=(\pi_i^{-1}\cdot\pi_i)\circ x=e\circ x=x</math>.
Denote that <math>\sigma=\pi_i^{-1}\cdot \pi</math>. Then
*<math>\pi_i\cdot\sigma=\pi_i\cdot(\pi_i^{-1}\cdot\pi)=\pi</math>, and
*<math>\sigma\circ x=(\pi_i^{-1}\cdot\pi)\circ x=x</math>, which implies that <math>\sigma\in G_x</math>.
Therefore, each <math>\pi\in G</math> corresponds to a unique pair <math>(\pi_i,\sigma)\in P\times G_x</math>. We have a 1-1 mapping from <math>G</math> to <math>P\times G_x</math>.
 
For every <math>\pi_i\in P</math> and every <math>\sigma\in G_x</math>, <math>\pi=\pi_i\cdot\sigma\in G</math>. We show that this is a 1-1 mapping. Suppose that <math>\pi_i\cdot\sigma=\pi_j\cdot\tau</math> for some <math>\pi_i,\pi_j\in P</math> and <math>\sigma,\tau\in G_x</math>. Then <math>(\pi_i\cdot\sigma)\circ x=\pi_i\circ(\sigma\circ x)=\pi_i\circ x=x_i</math> and <math>(\pi_j\cdot \tau)\circ x=\pi_j\circ(\tau\circ x)=\pi_j\circ x=x_j</math>, which implies <math>x_i=x_j</math> and correspondingly <math>\pi_i=\pi_j</math>. Since <math>\pi_i\cdot\sigma=\pi_j\cdot\tau</math>, <math>\sigma=\tau</math>. Therefore, we show that the mapping is 1-1.
 
In conclusion, there exists a bijection between <math>P\times G_x</math> and <math>G</math>. As a consequence, <math>|Gx||G_x|=|P||G_x|=|P\times G_x|=|G|</math>.
}}
 
{{Theorem|Burnside's Lemma|
:Let <math>G</math> be a permutation group acting on a set <math>X</math>. The number of orbits, denoted <math>|X/G|</math>, is
::<math>|X/G|=\frac{1}{|G|}\sum_{\pi\in G}|X_{\pi}|.</math>
}}
{{Proof|
Let
:<math>A(\pi,x)=\begin{cases}1 & \pi\circ x=x,\\ 0 & \text{otherwise.}\end{cases}</math>
Basically <math>A(\pi,x)</math> indicates whether <math>x</math> is invariant under action of <math>\pi</math>. We can think of <math>A</math> as a matrix indexed by <math>G\times X</math>. An important observation is that the row sums and column sums of <math>A</math> are <math>|X_\pi|</math> and <math>|G_x|</math> respectively, namely,
:<math>|X_\pi|=\sum_{x\in X}A(\pi,x)</math> and <math>|G_x|=\sum_{\pi\in G}A(\pi,x)</math>.
Then a double counting gives that
:<math>\sum_{\pi\in G}|X_\pi|=\sum_{\pi\in G}\sum_{x\in X}A(\pi,x)=\sum_{x\in X}\sum_{\pi\in G}A(\pi,x)=\sum_{x\in X}|G_x|</math>.
 
Due to the above lemma, <math>|G_x|=\frac{|G|}{|Gx|}</math>, thus
:<math>\sum_{x\in X}|G_x|=\sum_{x\in X}\frac{|G|}{|Gx|}=|G|\sum_{x\in X}\frac{1}{|Gx|}</math>.
We may enumerate the <math>x\in X</math> in the sum by first enumerating the orbits and then the elements in each orbit. Suppose there are <math>m</math> orbits <math>X_1,X_2,\ldots,X_m</math>. They forms a partition of <math>X</math>, and for any <math>X_i</math> and every <math>x\in X_i</math>, <math>X_i=Gx</math>. Thus,
:<math>|G|\sum_{x\in X}\frac{1}{|Gx|}=|G|\sum_{i=1}^m\sum_{x\in X_i}\frac{1}{|Gx|}=|G|\sum_{i=1}^m\sum_{x\in X_i}\frac{1}{|X_i|}=|G|\sum_{i=1}^m1=|G|m</math>.
Combining everything together
:<math>\sum_{\pi\in G}|X_\pi|=\sum_{x\in X}|G_x|=|G|\sum_{x\in X}\frac{1}{|Gx|}=|G|m</math>,
which gives us that the number of orbits is
:<math>m=\frac{1}{|G|}\sum_{\pi\in G}|X_\pi|</math>.
}}
 
==Pólya's Theory of Counting ==
=== The cycle index ===
 
=== Pólya's enumeration formula ===
 
=== de Bruijn's generalization===

Latest revision as of 09:43, 22 December 2013

William Donald Hamilton FRS (1 August 1936 – 7 March 2000) was an English evolutionary biologist whom Richard Dawkins praised as one of the greatest evolutionary theorists of the 20th century.[1]

Hamilton became famous through his theoretical work on kin selection and altruism. He explained its genetic basis, and this was a key part of the gene-centered view of evolution. In doing this, he became one of the forerunners of sociobiology, as popularized by E.O. Wilson. Hamilton was certainly a big influence on Dawkins. He also published important work on sex ratios and the evolution of sex. From 1984 to his death in 2000, he was the Royal Society Research Professor at Oxford University. He died of malaria contracted in the Democratic Republic of the Congo.

Hamilton's equation

Hamilton's equation describes whether or not a gene for altruistic behaviour will spread in a population.[2] The gene will spread if rxb is greater than c:

[math]\displaystyle{ rb \gt c \ }[/math]

where:

  • [math]\displaystyle{ c \ }[/math] is the reproductive cost to the altruist,
  • [math]\displaystyle{ b \ }[/math] is the reproductive benefit to the recipient of the altruistic behavior, and
  • [math]\displaystyle{ r \ }[/math] is the probability, above the population average, of the individuals sharing an altruistic gene – the "degree of relatedness".

Collected papers

Hamilton started to publish his collected papers starting in 1996, with short essays giving each paper context. He died after the preparation of the second volume, so the commentaries for the third volume came from his coauthors.

  • Hamilton W.D. 1996. Narrow roads of gene land vol. 1: Evolution of social behaviour. Freeman, Oxford. ISBN 0-7167-4530-5
  • Hamilton W.D. 2002. Narrow roads of gene land vol. 2: Evolution of sex. Oxford University Press, Oxford. ISBN 0-19-850336-9
  • Hamilton W.D. 2005. Narrow roads of gene land, vol. 3: Last words (with essays by coauthors, ed. M. Ridley). Oxford University Press, Oxford. ISBN 0-19-856690-5

References

Template:Reflist

  1. ↑ Obituary by Richard Dawkins – The Independent – 10 March 2000
  2. ↑ Hamilton W.D. 1996. Narrow roads of geneland: the collected papers of W.D. Hamilton, vol 1. Freeman, Oxford.
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=组合数学_(Fall_2011)/Pólya%27s_theory_of_counting&oldid=7721"