Saltar al contenido principal

# 6.3: Contar

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$

( \newcommand{\kernel}{\mathrm{null}\,}\) $$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\id}{\mathrm{id}}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\kernel}{\mathrm{null}\,}$$

$$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$

$$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$

$$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

$$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$$

$$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$$

$$\newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vectorC}[1]{\textbf{#1}}$$

$$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$$

$$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$$

$$\newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}}$$

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\avec}{\mathbf a}$$ $$\newcommand{\bvec}{\mathbf b}$$ $$\newcommand{\cvec}{\mathbf c}$$ $$\newcommand{\dvec}{\mathbf d}$$ $$\newcommand{\dtil}{\widetilde{\mathbf d}}$$ $$\newcommand{\evec}{\mathbf e}$$ $$\newcommand{\fvec}{\mathbf f}$$ $$\newcommand{\nvec}{\mathbf n}$$ $$\newcommand{\pvec}{\mathbf p}$$ $$\newcommand{\qvec}{\mathbf q}$$ $$\newcommand{\svec}{\mathbf s}$$ $$\newcommand{\tvec}{\mathbf t}$$ $$\newcommand{\uvec}{\mathbf u}$$ $$\newcommand{\vvec}{\mathbf v}$$ $$\newcommand{\wvec}{\mathbf w}$$ $$\newcommand{\xvec}{\mathbf x}$$ $$\newcommand{\yvec}{\mathbf y}$$ $$\newcommand{\zvec}{\mathbf z}$$ $$\newcommand{\rvec}{\mathbf r}$$ $$\newcommand{\mvec}{\mathbf m}$$ $$\newcommand{\zerovec}{\mathbf 0}$$ $$\newcommand{\onevec}{\mathbf 1}$$ $$\newcommand{\real}{\mathbb R}$$ $$\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$$ $$\newcommand{\laspan}[1]{\text{Span}\{#1\}}$$ $$\newcommand{\bcal}{\cal B}$$ $$\newcommand{\ccal}{\cal C}$$ $$\newcommand{\scal}{\cal S}$$ $$\newcommand{\wcal}{\cal W}$$ $$\newcommand{\ecal}{\cal E}$$ $$\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$$ $$\newcommand{\gray}[1]{\color{gray}{#1}}$$ $$\newcommand{\lgray}[1]{\color{lightgray}{#1}}$$ $$\newcommand{\rank}{\operatorname{rank}}$$ $$\newcommand{\row}{\text{Row}}$$ $$\newcommand{\col}{\text{Col}}$$ $$\renewcommand{\row}{\text{Row}}$$ $$\newcommand{\nul}{\text{Nul}}$$ $$\newcommand{\var}{\text{Var}}$$ $$\newcommand{\corr}{\text{corr}}$$ $$\newcommand{\len}[1]{\left|#1\right|}$$ $$\newcommand{\bbar}{\overline{\bvec}}$$ $$\newcommand{\bhat}{\widehat{\bvec}}$$ $$\newcommand{\bperp}{\bvec^\perp}$$ $$\newcommand{\xhat}{\widehat{\xvec}}$$ $$\newcommand{\vhat}{\widehat{\vvec}}$$ $$\newcommand{\uhat}{\widehat{\uvec}}$$ $$\newcommand{\what}{\widehat{\wvec}}$$ $$\newcommand{\Sighat}{\widehat{\Sigma}}$$ $$\newcommand{\lt}{<}$$ $$\newcommand{\gt}{>}$$ $$\newcommand{\amp}{&}$$ $$\definecolor{fillinmathshade}{gray}{0.9}$$

Vimos anteriormente que el tamaño de una órbita es igual a$$|G|/\mathord |G_s|$$. We can use this to figure out how many orbits there are in a $$G$$-set in all. This is a very useful thing to count: It's useful for counting things 'up to symmetry.' We'll denote the orbits of $$S$$ by $$S/\mathord G$$, and thus the number of orbits is $$|S/\mathord G|$$. The notation should be read '$$S$$-mod-$$G$$'; it's useful when two things are 'the same' in $$S$$ if they are related by an application of an element of $$G$$.

Por ejemplo, supongamos que queríamos contar todas las formas de pintar los lados de un cubo con tres colores. Naturalmente pensaríamos que dos formas de pintar son las mismas si pudiéramos rotar el cubo para alinear los colores de la misma manera. Luego el grupo$$G$$ might be symmetries of the cube, and the set $$S$$ would be all ways of painting the cube in fixed position: What we're really trying to count is $$|S/\mathord G|$$.

Let$$S^g$$ denote the set $$\{s\in S \mid g\cdot s=s\}$$. This is like the stabilizer in reverse: we're collecting up all of the elements of the set $$S$$ that are fixed by $$g$$.

Teorema 6.2.0:

(Lema de Burnside) El número de órbitas en un$$G$$-set $$S$$ is $$|S/\mathord G| = \frac{1}{|G|} \sum_{g\in G} |S^g|$$.

(Tenga en cuenta que hay amplia evidencia de que Burnside en realidad no inventó el lema de Burnside; incluimos el nombre porque es por lo que todos lo conocen).

Prueba 6.2.1:

Let$$G\cdot s$$ denote the orbit of $$s$$ under $$G$$. First notice that the sum of the size of the fixed sets $$S^g$$ is equal to the sum of the size of the stabilizer groups $$G_s$$: Both are counting the number of pairs $$(g,s)$$ such that $$g\cdot s=s$$. Then:

$$\sum_{g\in G} |S^g| = \sum_{s\in S} |G_s|$$ $$= \sum_{s\in S} |G|/\mathord |G\cdot s|$$ $$= |G| \sum_{s\in S} \frac{1}{|G\cdot s|}$$ $$= |G| \sum_{S/\mathord G} 1$$ $$= |G| |S/\mathord G|$$

Luego dividiendo ambos lados por$$|G|$$ gives the desired result.

Probemos un ejemplo. Mencionamos anteriormente la cuestión del número de formas de colorear un cubo con tres colores. Vamos a probarlo. Hay una pregunta inicial de qué grupo de simetrías nos interesa: ¿Permitimos reflejos del cubo o solo rotaciones? Como no podemos reflejar naturalmente las cosas en el espacio tridimensional, nos quedaremos con el grupo de rotación del cubo. (Esta elección, por cierto, tiene consecuencias en la química. Y aquí hay una excelente pieza de Radiolab sobre el tema.)

El grupo de rotación tiene$$24$$ elements: From a base-position of the cube, you can rotate a marked face to any other face (there are six choices), and from there four rotations are available, making $$24$$ symmetries in all. Every rotation in 3-dimensional space has an axis of rotation. So each rotational symmetry will have an axis of rotation; we can identify the symmetries by their axis and amount of rotation. We classify these symmetries into five classes, and determine the number of fixed points for each class.

Hay

Template:ContribDenton

This page titled 6.3: Contar is shared under a not declared license and was authored, remixed, and/or curated by Tom Denton.