imported>Etone |
imported>Macdonald-ross |
| Line 1: |
Line 1: |
| == Principle of Inclusion-Exclusion ==
| | {{otheruse|biological fitness}} |
| Let <math>A</math> and <math>B</math> be two finite sets. The cardinality of their union is
| | '''Fitness''' in [[biology]] is the relative ability of an organism to survive and pass on its [[gene]]s to the next generation.<ref>King R.C. Stansfield W.D. & Mulligan P.K. 2006. ''A dictionary of genetics'', 7th ed. Oxford.</ref><sup>p160</sup> It is a central idea in [[evolution|evolutionary theory]]. Fitness is usually equal to the proportion of the individual's [[gene]]s in all the genes of the next generation. |
| :<math>|A\cup B|=|A|+|B|-{\color{Blue}|A\cap B|}</math>.
| |
| For three sets <math>A</math>, <math>B</math>, and <math>C</math>, the cardinality of the union of these three sets is computed as
| |
| :<math>|A\cup B\cup C|=|A|+|B|+|C|-{\color{Blue}|A\cap B|}-{\color{Blue}|A\cap C|}-{\color{Blue}|B\cap C|}+{\color{Red}|A\cap B\cap C|}</math>.
| |
| This is illustrated by the following figure.
| |
| ::[[Image:Inclusion-exclusion.png|200px|border|center]]
| |
|
| |
|
| Generally, the '''Principle of Inclusion-Exclusion''' states the rule for computing the union of <math>n</math> finite sets <math>A_1,A_2,\ldots,A_n</math>, such that
| | Like all terms in evolutionary biology, fitness is defined in terms of an interbreeding [[Population genetics|population]], which might or might not be a whole [[species]]. If differences in individual genotypes affect fitness, then the frequencies of the genotypes will change over generations; the genotypes with higher fitness become more common. This is the process called [[natural selection]]. |
| {{Equation|
| |
| <math>
| |
| \begin{align}
| |
| \left|\bigcup_{i=1}^nA_i\right|
| |
| &=
| |
| \sum_{I\subseteq\{1,\ldots,n\}}(-1)^{|I|-1}\left|\bigcap_{i\in I}A_i\right|.
| |
| \end{align}
| |
| </math>
| |
| }}
| |
| -----
| |
|
| |
|
| In combinatorial enumeration, the Principle of Inclusion-Exclusion is usually applied in its complement form.
| | An individual's fitness is caused by its [[phenotype]], and passed on by its [[genotype]]. The fitnesses of different individuals with the same genotype are not necessarily equal. It depends on the [[environment]] in which the individuals live, and on accidental [[event]]s. However, since the fitness of the genotype is an [[average]]d quantity, it reflects the reproductive outcomes of ''all'' individuals with that genotype. |
|
| |
|
| Let <math>A_1,A_2,\ldots,A_n\subseteq U</math> be subsets of some finite set <math>U</math>. Here <math>U</math> is some universe of combinatorial objects, whose cardinality is easy to calculate (e.g. all strings, tuples, permutations), and each <math>A_i</math> contains the objects with some specific property (e.g. a "pattern") which we want to avoid. The problem is to count the number of objects without any of the <math>n</math> properties. We write <math>\bar{A_i}=U-A_i</math>. The number of objects without any of the properties <math>A_1,A_2,\ldots,A_n</math> is
| | == Relatedness == |
| {{Equation|
| | Fitness measures the number of the ''copies'' of the genes of an individual in the next generation. It doesn't really matter how the genes arrive in the next generation. For an individual, it is equally "beneficial" to reproduce itself, or to help relatives with similar genes to reproduce, ''as long as similar number of copies of individual's genes get passed on to the next generation''. Selection which promotes this kind of helper behaviour is called [[kin selection]]. |
| <math>
| |
| \begin{align}
| |
| \left|\bar{A_1}\cap\bar{A_2}\cap\cdots\cap\bar{A_n}\right|=\left|U-\bigcup_{i=1}^nA_i\right|
| |
| &=
| |
| |U|+\sum_{I\subseteq\{1,\ldots,n\}}(-1)^{|I|}\left|\bigcap_{i\in I}A_i\right|.
| |
| \end{align}
| |
| </math>
| |
| }}
| |
| For an <math>I\subseteq\{1,2,\ldots,n\}</math>, we denote | |
| :<math>A_I=\bigcap_{i\in I}A_i</math>
| |
| with the convention that <math>A_\emptyset=U</math>. The above equation is stated as:
| |
| {{Theorem|Principle of Inclusion-Exclusion|
| |
| :Let <math>A_1,A_2,\ldots,A_n</math> be a family of subsets of <math>U</math>. Then the number of elements of <math>U</math> which lie in none of the subsets <math>A_i</math> is
| |
| ::<math>\sum_{I\subseteq\{1,\ldots, n\}}(-1)^{|I|}|A_I|</math>.
| |
| }}
| |
|
| |
|
| Let <math>S_k=\sum_{|I|=k}|A_I|\,</math>. Conventionally, <math>S_0=|A_\emptyset|=|U|</math>. The principle of inclusion-exclusion can be expressed as
| | Our closest relatives (parents, siblings, and our own children) share on average 50% (half) of our genes. One step further removed are grandparents. With each of them we share on average 25% (a quarter) of our genes. That is a measure of our relatedness to them. Next come first cousins (children of our parents' siblings). We share 12.5% (1/8) of their genes.<ref name=JMS>Maynard Smith, John. 1999. ''Evolutionary genetics''. 2nd ed, Cambridge University Press.</ref><sup>p100</sup> |
| {{Equation|<math>
| |
| \left|\bar{A_1}\cap\bar{A_2}\cap\cdots\cap\bar{A_n}\right|=
| |
| S_0-S_1+S_2+\cdots+(-1)^nS_n.
| |
| </math> | |
| }}
| |
|
| |
|
| === Surjections === | | === Hamilton's rule === |
| In the twelvefold way, we discuss the counting problems incurred by the mappings <math>f:N\rightarrow M</math>. The basic case is that elements from both <math>N</math> and <math>M</math> are distinguishable. In this case, it is easy to count the number of arbitrary mappings (which is <math>m^n</math>) and the number of injective (one-to-one) mappings (which is <math>(m)_n</math>), but the number of surjective is difficult. Here we apply the principle of inclusion-exclusion to count the number of surjective (onto) mappings.
| | [[W.D. Hamilton|William Hamilton]] added various ideas to the notion of fitness. His rule suggests that a costly action should be performed if: |
| {{Theorem|Theorem|
| | :<math>C < R \times B </math> where: |
| :The number of surjective mappings from an <math>n</math>-set to an <math>m</math>-set is given by
| | * <math>c \ </math> is the reproductive cost to the altruist, |
| ::<math>\sum_{k=1}^m(-1)^{m-k}{m\choose k}k^n</math>.
| | * <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". |
| {{Proof|
| | Fitness costs and benefits are measured in [[fecundity]].<ref>Hamilton W.D. 1964. The genetical evolution of social behavior. ''Journal of Theoretical Biology'' '''7''' (1): 1–52. doi:10.1016/0022-5193(64)90038-4.</ref> |
| Let <math>U=\{f:[n]\rightarrow[m]\}</math> be the set of mappings from <math>[n]</math> to <math>[m]</math>. Then <math>|U|=m^n</math>.
| |
|
| |
|
| For <math>i\in[m]</math>, let <math>A_i</math> be the set of mappings <math>f:[n]\rightarrow[m]</math> that none of <math>j\in[n]</math> is mapped to <math>i</math>, i.e. <math>A_i=\{f:[n]\rightarrow[m]\setminus\{i\}\}</math>, thus <math>|A_i|=(m-1)^n</math>.
| | === Inclusive fitness === |
| | Inclusive fitness is a term which is essentially the same as fitness, but emphasises the group of genes rather than individuals. |
|
| |
|
| More generally, for <math>I\subseteq [m]</math>, <math>A_I=\bigcap_{i\in I}A_i</math> contains the mappings <math>f:[n]\rightarrow[m]\setminus I</math>. And <math>|A_I|=(m-|I|)^n\,</math>.
| | Biological fitness says how well an organism can reproduce, and spread its genes to its offspring. The theory of inclusive fitness says that the fitness of an organism is also increased to the extent that its close relatives also reproduce. This is because relatives share genes in proportion to their relationship. |
|
| |
|
| A mapping <math>f:[n]\rightarrow[m]</math> is surjective if <math>f</math> lies in none of <math>A_i</math>. By the principle of inclusion-exclusion, the number of surjective <math>f:[n]\rightarrow[m]</math> is
| | Another way of saying it: ''the inclusive fitness of an organism is not a property of itself, but a property of its set of [[genes]]''. It is calculated from from the reproductive success of the individual, plus the reproductive success of its relatives, each one weighed by an appropriate coefficient of relatedness.<ref>Adapted from Dawkins R. 1982. ''The extended phenotype''. Oxford: Oxford University Press, p186. ISBN 0-19-288051-9</ref> |
| :<math>\sum_{I\subseteq[m]}(-1)^{|I|}\left|A_I\right|=\sum_{I\subseteq[m]}(-1)^{|I|}(m-|I|)^n=\sum_{j=0}^m(-1)^j{m\choose j}(m-j)^n</math>.
| |
| Let <math>k=m-j</math>. The theorem is proved.
| |
| }}
| |
|
| |
|
| Recall that, in the twelvefold way, we establish a relation between surjections and partitions.
| | == History == |
| | The [[British]] [[Sociology|social]] [[philosopher]] [[Herbert Spencer]] coined the phrase ''[[survival of the fittest]]'' in his 1864 work ''Principles of biology'' to mean what [[Charles Darwin]] called [[natural selection]].<ref> Herbert Spencer 1864. ''Principles of Biology'' London, vol 1, 444, wrote “This survival of the fittest, which I have here sought to express in mechanical terms, is that which Mr. Darwin has called ‘natural selection’, or the preservation of favoured races in the struggle for life. </ref> The original phrase was "survival of the best fitted". |
|
| |
|
| * Surjection to ordered partition:
| | == References == |
| :For a surjective <math>f:[n]\rightarrow[m]</math>, <math>(f^{-1}(0),f^{-1}(1),\ldots,f^{-1}(m-1))</math> is an '''ordered partition''' of <math>[n]</math>.
| | {{Reflist}} |
| * Ordered partition to surjection:
| | |
| :For an ordered <math>m</math>-partition <math>(B_0,B_1,\ldots, B_{m-1})</math> of <math>[n]</math>, we can define a function <math>f:[n]\rightarrow[m]</math> by letting <math>f(i)=j</math> if and only if <math>i\in B_j</math>. <math>f</math> is surjective since as a partition, none of <math>B_i</math> is empty.
| |
|
| |
|
| Therefore, we have a one-to-one correspondence between surjective mappings from an <math>n</math>-set to an <math>m</math>-set and the ordered <math>m</math>-partitions of an <math>n</math>-set.
| | [[Category:Classical genetics]] |
| | | [[Category:Evolutionary biology]] |
| The Stirling number of the second kind <math>\left\{{n\atop m}\right\}</math> is the number of <math>m</math>-partitions of an <math>n</math>-set. There are <math>m!</math> ways to order an <math>m</math>-partition, thus the number of surjective mappings <math>f:[n]\rightarrow[m]</math> is <math>m! \left\{{n\atop m}\right\}</math>. Combining with what we have proved for surjections, we give the following result for the Stirling number of the second kind.
| |
| | |
| {{Theorem|Proposition|
| |
| :<math>\left\{{n\atop m}\right\}=\frac{1}{m!}\sum_{k=1}^m(-1)^{m-k}{m\choose k}k^n</math>.
| |
| }}
| |
| | |
| === Derangements ===
| |
| We now count the number of bijections from a set to itself with no fixed points. This is the '''derangement problem'''.
| |
| | |
| For a permutation <math>\pi</math> of <math>\{1,2,\ldots,n\}</math>, a '''fixed point''' is such an <math>i\in\{1,2,\ldots,n\}</math> that <math>\pi(i)=i</math>.
| |
| A [http://en.wikipedia.org/wiki/Derangement '''derangement'''] of <math>\{1,2,\ldots,n\}</math> is a permutation of <math>\{1,2,\ldots,n\}</math> that has no fixed points.
| |
| | |
| {{Theorem|Theorem|
| |
| :The number of derangements of <math>\{1,2,\ldots,n\}</math> given by
| |
| ::<math>n!\sum_{k=0}^n\frac{(-1)^k}{k!}\approx \frac{n!}{\mathrm{e}}</math>.
| |
| }}
| |
| {{Proof|
| |
| Let <math>U</math> be the set of all permutations of <math>\{1,2,\ldots,n\}</math>. So <math>|U|=n!</math>.
| |
| | |
| Let <math>A_i</math> be the set of permutations with fixed point <math>i</math>; so <math>|A_i|=(n-1)!</math>. More generally, for any <math>I\subseteq \{1,2,\ldots,n\}</math>, <math>A_I=\bigcap_{i\in I}A_i</math>, and <math>|A_I|=(n-|I|)!</math>, since permutations in <math>A_I</math> fix every point in <math>I</math> and permute the remaining points arbitrarily. A permutation is a derangement if and only if it lies in none of the sets <math>A_i</math>. So the number of derangements is
| |
| :<math>\sum_{I\subseteq\{1,2,\ldots,n\}}(-1)^{|I|}(n-|I|)!=\sum_{k=0}^n(-1)^k{n\choose k}(n-k)!=n!\sum_{k=0}^n\frac{(-1)^k}{k!}.</math>
| |
| By Taylor's series,
| |
| :<math>\frac{1}{\mathrm{e}}=\sum_{k=0}^\infty\frac{(-1)^k}{k!}=\sum_{k=0}^n\frac{(-1)^k}{k!}\pm o\left(\frac{1}{n!}\right)</math>.
| |
| It is not hard to see that <math>n!\sum_{k=0}^n\frac{(-1)^k}{k!}</math> is the closest integer to <math>\frac{n!}{\mathrm{e}}</math>.
| |
| }}
| |
| | |
| Therefore, there are about <math>\frac{1}{\mathrm{e}}</math> fraction of all permutations with no fixed points.
| |
| | |
| === Permutations with restricted positions ===
| |
| We introduce a general theory of counting permutations with restricted positions. In the derangement problem, we count the number of permutations that <math>\pi(i)\neq i</math>. We now generalize to the problem of counting permutations which avoid a set of arbitrarily specified positions.
| |
| | |
| It is traditionally described using terminology from the game of chess. Let <math>B\subseteq \{1,\ldots,n\}\times \{1,\ldots,n\}</math>, called a '''board'''. As illustrated below, we can think of <math>B</math> as a chess board, with the positions in <math>B</math> marked by "<math>\times</math>".
| |
| {{Chess diagram small
| |
| |
| |
| |
| |
| |=
| |
| 8 |__|xx|xx|__|xx|__|__|xx|=
| |
| 7 |xx|__|__|xx|__|__|xx|__|=
| |
| 6 |xx|__|xx|xx|__|xx|xx|__|=
| |
| 5 |__|xx|__|__|xx|__|xx|__|=
| |
| 4 |xx|__|__|__|xx|xx|xx|__|=
| |
| 3 |__|xx|__|xx|__|__|__|xx|=
| |
| 2 |__|__|xx|__|xx|__|__|xx|=
| |
| 1 |xx|__|__|xx|__|xx|__|__|=
| |
| a b c d e f g h
| |
| |
| |
| }}
| |
| For a permutation <math>\pi</math> of <math>\{1,\ldots,n\}</math>, define the '''graph''' <math>G_\pi(V,E)</math> as
| |
| :<math>
| |
| \begin{align}
| |
| G_\pi &= \{(i,\pi(i))\mid i\in \{1,2,\ldots,n\}\}.
| |
| \end{align}
| |
| </math>
| |
| This can also be viewed as a set of marked positions on a chess board. Each row and each column has only one marked position, because <math>\pi</math> is a permutation. Thus, we can identify each <math>G_\pi</math> as a placement of <math>n</math> rooks (“城堡”，规则同中国象棋里的“车”) without attacking each other.
| |
| | |
| For example, the following is the <math>G_\pi</math> of such <math>\pi</math> that <math>\pi(i)=i</math>.
| |
| {{Chess diagram small
| |
| |
| |
| |
| |
| |=
| |
| 8 |rl|__|__|__|__|__|__|__|=
| |
| 7 |__|rl|__|__|__|__|__|__|=
| |
| 6 |__|__|rl|__|__|__|__|__|=
| |
| 5 |__|__|__|rl|__|__|__|__|=
| |
| 4 |__|__|__|__|rl|__|__|__|=
| |
| 3 |__|__|__|__|__|rl|__|__|=
| |
| 2 |__|__|__|__|__|__|rl|__|=
| |
| 1 |__|__|__|__|__|__|__|rl|=
| |
| a b c d e f g h
| |
| |
| |
| }}
| |
| Now define
| |
| :<math>\begin{align}
| |
| N_0 &= \left|\left\{\pi\mid B\cap G_\pi=\emptyset\right\}\right|\\
| |
| r_k &= \mbox{number of }k\mbox{-subsets of }B\mbox{ such that no two elements have a common coordinate}\\
| |
| &=\left|\left\{S\in{B\choose k} \,\bigg|\, \forall (i_1,j_1),(i_2,j_2)\in S, i_1\neq i_2, j_1\neq j_2 \right\}\right|
| |
| \end{align}
| |
| </math>
| |
| Interpreted in chess game,
| |
| * <math>B</math>: a set of marked positions in an <math>[n]\times [n]</math> chess board.
| |
| * <math>N_0</math>: the number of ways of placing <math>n</math> non-attacking rooks on the chess board such that none of these rooks lie in <math>B</math>.
| |
| * <math>r_k</math>: number of ways of placing <math>k</math> non-attacking rooks on <math>B</math>.
| |
| | |
| Our goal is to count <math>N_0</math> in terms of <math>r_k</math>. This gives the number of permutations avoid all positions in a <math>B</math>.
| |
| | |
| {{Theorem|Theorem|
| |
| :<math>N_0=\sum_{k=0}^n(-1)^kr_k(n-k)!</math>.
| |
| }}
| |
| {{Proof|
| |
| For each <math>i\in[n]</math>, let <math>A_i=\{\pi\mid (i,\pi(i))\in B\}</math> be the set of permutations <math>\pi</math> whose <math>i</math>-th position is in <math>B</math>.
| |
| | |
| <math>N_0</math> is the number of permutations avoid all positions in <math>B</math>. Thus, our goal is to count the number of permutations <math>\pi</math> in none of <math>A_i</math> for <math>i\in [n]</math>.
| |
| | |
| For each <math>I\subseteq [n]</math>, let <math>A_I=\bigcap_{i\in I}A_i</math>, which is the set of permutations <math>\pi</math> such that <math>(i,\pi(i))\in B</math> for all <math>i\in I</math>. Due to the principle of inclusion-exclusion,
| |
| :<math>N_0=\sum_{I\subseteq [n]} (-1)^{|I|}|A_I|=\sum_{k=0}^n(-1)^k\sum_{I\in{[n]\choose k}}|A_I|</math>. | |
| | |
| The next observation is that
| |
| :<math>\sum_{I\in{[n]\choose k}}|A_I|=r_k(n-k)!</math>,
| |
| because we can count both sides by first placing <math>k</math> non-attacking rooks on <math>B</math> and placing <math>n-k</math> additional non-attacking rooks on <math>[n]\times [n]</math> in <math>(n-k)!</math> ways.
| |
| | |
| Therefore,
| |
| :<math>N_0=\sum_{k=0}^n(-1)^kr_k(n-k)!</math>.
| |
| }}
| |
| | |
| ====Derangement problem====
| |
| We use the above general method to solve the derange problem again.
| |
| | |
| Take <math>B=\{(1,1),(2,2),\ldots,(n,n)\}</math> as the chess board. A derangement <math>\pi</math> is a placement of <math>n</math> non-attacking rooks such that none of them is in <math>B</math>.
| |
| {{Chess diagram small
| |
| |
| |
| |
| |
| |=
| |
| 8 |xx|__|__|__|__|__|__|__|=
| |
| 7 |__|xx|__|__|__|__|__|__|=
| |
| 6 |__|__|xx|__|__|__|__|__|=
| |
| 5 |__|__|__|xx|__|__|__|__|=
| |
| 4 |__|__|__|__|xx|__|__|__|=
| |
| 3 |__|__|__|__|__|xx|__|__|=
| |
| 2 |__|__|__|__|__|__|xx|__|=
| |
| 1 |__|__|__|__|__|__|__|xx|=
| |
| a b c d e f g h
| |
| |
| |
| }}
| |
| Clearly, the number of ways of placing <math>k</math> non-attacking rooks on <math>B</math> is <math>r_k={n\choose k}</math>. We want to count <math>N_0</math>, which gives the number of ways of placing <math>n</math> non-attacking rooks such that none of these rooks lie in <math>B</math>.
| |
| | |
| By the above theorem
| |
| :<math>
| |
| N_0=\sum_{k=0}^n(-1)^kr_k(n-k)!=\sum_{k=0}^n(-1)^k{n\choose k}(n-k)!=\sum_{k=0}^n(-1)^k\frac{n!}{k!}=n!\sum_{k=0}^n(-1)^k\frac{1}{k!}\approx\frac{n!}{e}.
| |
| </math>
| |
| | |
| ====Problème des ménages====
| |
| Suppose that in a banquet, we want to seat <math>n</math> couples at a circular table, satisfying the following constraints:
| |
| * Men and women are in alternate places.
| |
| * No one sits next to his/her spouse.
| |
| | |
| In how many ways can this be done?
| |
| | |
| (For convenience, we assume that every seat at the table marked differently so that rotating the seats clockwise or anti-clockwise will end up with a '''different''' solution.)
| |
| | |
| First, let the <math>n</math> ladies find their seats. They may either sit at the odd numbered seats or even numbered seats, in either case, there are <math>n!</math> different orders. Thus, there are <math>2(n!)</math> ways to seat the <math>n</math> ladies.
| |
| | |
| After sitting the wives, we label the remaining <math>n</math> places clockwise as <math>0,1,\ldots, n-1</math>. And a seating of the <math>n</math> husbands is given by a permutation <math>\pi</math> of <math>[n]</math> defined as follows. Let <math>\pi(i)</math> be the seat of the husband of he lady sitting at the <math>i</math>-th place.
| |
| | |
| It is easy to see that <math>\pi</math> satisfies that <math>\pi(i)\neq i</math> and <math>\pi(i)\not\equiv i+1\pmod n</math>, and every permutation <math>\pi</math> with these properties gives a feasible seating of the <math>n</math> husbands. Thus, we only need to count the number of permutations <math>\pi</math> such that <math>\pi(i)\not\equiv i, i+1\pmod n</math>.
| |
| | |
| Take <math>B=\{(0,0),(1,1),\ldots,(n-1,n-1), (0,1),(1,2),\ldots,(n-2,n-1),(n-1,0)\}</math> as the chess board. A permutation <math>\pi</math> which defines a way of seating the husbands, is a placement of <math>n</math> non-attacking rooks such that none of them is in <math>B</math>.
| |
| {{Chess diagram small
| |
| |
| |
| |
| |
| |=
| |
| 8 |xx|xx|__|__|__|__|__|__|=
| |
| 7 |__|xx|xx|__|__|__|__|__|=
| |
| 6 |__|__|xx|xx|__|__|__|__|=
| |
| 5 |__|__|__|xx|xx|__|__|__|=
| |
| 4 |__|__|__|__|xx|xx|__|__|=
| |
| 3 |__|__|__|__|__|xx|xx|__|=
| |
| 2 |__|__|__|__|__|__|xx|xx|=
| |
| 1 |xx|__|__|__|__|__|__|xx|=
| |
| a b c d e f g h
| |
| |
| |
| }}
| |
| We need to compute <math>r_k</math>, the number of ways of placing <math>k</math> non-attacking rooks on <math>B</math>. For our choice of <math>B</math>, <math>r_k</math> is the number of ways of choosing <math>k</math> points, no two consecutive, from a collection of <math>2n</math> points arranged in a circle.
| |
| | |
| We first see how to do this in a ''line''.
| |
| {{Theorem|Lemma|
| |
| :The number of ways of choosing <math>k</math> ''non-consecutive'' objects from a collection of <math>m</math> objects arranged in a ''line'', is <math>{m-k+1\choose k}</math>.
| |
| }}
| |
| {{Proof|
| |
| We draw a line of <math>m-k</math> black points, and then insert <math>k</math> red points into the <math>m-k+1</math> spaces between the black points (including the beginning and end).
| |
| ::<math>
| |
| \begin{align}
| |
| &\sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \, \sqcup \\
| |
| &\qquad\qquad\qquad\quad\Downarrow\\
| |
| &\sqcup \, \bullet \,\, {\color{Red}\bullet} \, \bullet \,\, {\color{Red}\bullet} \, \bullet \, \sqcup \, \bullet \,\, {\color{Red}\bullet}\, \, \bullet \, \sqcup \, \bullet \, \sqcup \, \bullet \,\, {\color{Red}\bullet}
| |
| \end{align}
| |
| </math>
| |
| This gives us a line of <math>m</math> points, and the red points specifies the chosen objects, which are non-consecutive. The mapping is 1-1 correspondence.
| |
| There are <math>{m-k+1\choose k}</math> ways of placing <math>k</math> red points into <math>m-k+1</math> spaces.
| |
| }}
| |
| | |
| The problem of choosing non-consecutive objects in a circle can be reduced to the case that the objects are in a line.
| |
| | |
| {{Theorem|Lemma|
| |
| :The number of ways of choosing <math>k</math> ''non-consecutive'' objects from a collection of <math>m</math> objects arranged in a ''circle'', is <math>\frac{m}{m-k}{m-k\choose k}</math>.
| |
| }}
| |
| {{Proof|
| |
| Let <math>f(m,k)</math> be the desired number; and let <math>g(m,k)</math> be the number of ways of choosing <math>k</math> non-consecutive points from <math>m</math> points arranged in a circle, next coloring the <math>k</math> points red, and then coloring one of the uncolored point blue.
| |
| | |
| Clearly, <math>g(m,k)=(m-k)f(m,k)</math>.
| |
| | |
| But we can also compute <math>g(m,k)</math> as follows:
| |
| * Choose one of the <math>m</math> points and color it blue. This gives us <math>m</math> ways.
| |
| * Cut the circle to make a line of <math>m-1</math> points by removing the blue point.
| |
| * Choose <math>k</math> non-consecutive points from the line of <math>m-1</math> points and color them red. This gives <math>{m-k\choose k}</math> ways due to the previous lemma.
| |
| | |
| Thus, <math>g(m,k)=m{m-k\choose k}</math>. Therefore we have the desired number <math>f(m,k)=\frac{m}{m-k}{m-k\choose k}</math>.
| |
| }}
| |
| | |
| By the above lemma, we have that <math>r_k=\frac{2n}{2n-k}{2n-k\choose k}</math>. Then apply the theorem of counting permutations with restricted positions,
| |
| :<math>
| |
| N_0=\sum_{k=0}^n(-1)^kr_k(n-k)!=\sum_{k=0}^n(-1)^k\frac{2n}{2n-k}{2n-k\choose k}(n-k)!.
| |
| </math>
| |
| | |
| This gives the number of ways of seating the <math>n</math> husbands ''after the ladies are seated''. Recall that there are <math>2n!</math> ways of seating the <math>n</math> ladies. Thus, the total number of ways of seating <math>n</math> couples as required by problème des ménages is
| |
| :<math>
| |
| 2n!\sum_{k=0}^n(-1)^k\frac{2n}{2n-k}{2n-k\choose k}(n-k)!.
| |
| </math>
| |
| | |
| === The Euler totient function ===
| |
| Two integers <math>m, n</math> are said to be '''relatively prime''' if their greatest common diviser <math>\mathrm{gcd}(m,n)=1</math>. For a positive integer <math>n</math>, let <math>\phi(n)</math> be the number of positive integers from <math>\{1,2,\ldots,n\}</math> that are relative prime to <math>n</math>. This function, called the Euler <math>\phi</math> function or '''the Euler totient function''', is fundamental in number theory.
| |
| | |
| We now derive a formula for this function by using the principle of inclusion-exclusion.
| |
| {{Theorem|Theorem (The Euler totient function)|
| |
| Suppose <math>n</math> is divisible by precisely <math>r</math> different primes, denoted <math>p_1,\ldots,p_r</math>. Then
| |
| :<math>\phi(n)=n\prod_{i=1}^r\left(1-\frac{1}{p_i}\right)</math>.
| |
| }}
| |
| {{Proof|
| |
| Let <math>U=\{1,2,\ldots,n\}</math> be the universe. The number of positive integers from <math>U</math> which is divisible by some <math>p_{i_1},p_{i_2},\ldots,p_{i_s}\in\{p_1,\ldots,p_r\}</math>, is <math>\frac{n}{p_{i_1}p_{i_2}\cdots p_{i_s}}</math>.
| |
| | |
| <math>\phi(n)</math> is the number of integers from <math>U</math> which is not divisible by any <math>p_1,\ldots,p_r</math>.
| |
| By principle of inclusion-exclusion,
| |
| :<math>
| |
| \begin{align}
| |
| \phi(n)
| |
| &=n+\sum_{k=1}^r(-1)^k\sum_{1\le i_1<i_2<\cdots <i_k\le n}\frac{n}{p_{i_1}p_{i_2}\cdots p_{i_k}}\\
| |
| &=n-\sum_{1\le i\le n}\frac{n}{p_i}+\sum_{1\le i<j\le n}\frac{n}{p_i p_j}-\sum_{1\le i<j<k\le n}\frac{n}{p_{i} p_{j} p_{k}}+\cdots + (-1)^r\frac{n}{p_{1}p_{2}\cdots p_{r}}\\
| |
| &=n\left(1-\sum_{1\le i\le n}\frac{1}{p_i}+\sum_{1\le i<j\le n}\frac{1}{p_i p_j}-\sum_{1\le i<j<k\le n}\frac{1}{p_{i} p_{j} p_{k}}+\cdots + (-1)^r\frac{1}{p_{1}p_{2}\cdots p_{r}}\right)\\
| |
| &=n\prod_{i=1}^r\left(1-\frac{1}{p_i}\right).
| |
| \end{align}
| |
| </math>
| |
| }}
| |
| | |
| == Reference ==
| |
| * ''Stanley,'' Enumerative Combinatorics, Volume 1, Chapter 2.
| |
| * ''van Lin and Wilson'', A course in combinatorics, Chapter 10, 25.
| |