First let me present Burnside's lemma.
Burnside's lemma Let $X$ be a finite set and $G$ a finite group acting on $X$,
$$ G\times X\to X,\;\; (g,x)\mapsto g\cdot x. $$
Denote by $G\backslash X$ be the space of orbits of this action. For each $g\in G$ we denote by $X^g$ the set of points in $X$ fixed by $g$
$$X^g:=\lbrace x\in X;\;\;g\cdot x=x\rbrace. $$
Then
$$ |G\backslash X|=\frac{1}{|G|} \sum_{g\in G} |X^g|, $$
where $|A|$ denotes the cardinality of a set $A$.
Proof. Look at the set $\newcommand{\bZ}{\mathbb{Z}}$ $\newcommand{\eF}{\mathscr{F}}$
$$ \eF = \bigl\lbrace (g,x)\in G\times X;\;\;g\cdot x= x\bigr\rbrace. $$
It defines a tautological double "fibration"
$$ G\stackrel{\ell}{\longleftarrow} \eF \stackrel{r}{\longrightarrow} X, $$
where the maps $\ell$ and $r$ are induced by the canonical projections $G\leftarrow G\times X$ and $G\times X\to X$. We deduce
$$ \sum_{g\in G}|\ell^{-1}(g)|=|\eF|=\sum_{x\in X} |r^{-1}(x)|. $$
Observe that the fiber $\ell^{-1}(g)$ can be identified with the set $X^g$ so that
\begin{equation}
\sum_{g\in G}|X^g|=\sum_{x\in X} |r^{-1}(x)|. \tag{1} \label{1}
\end{equation}
For any $x\in X$ the fiber $r^{-1}(x)$ can be identified with the stabilizer $G_x$ of $x$,
$$ G_x=\bigl\lbrace g\in G;\;\; g\cdot x =x\bigr\rbrace. $$
If $x, y$ are in the same orbit of $G$ then $|G_x|=|G_y|$. Indeed, if $y=g\cdot x$ then $G_y=gG_xG^{-1}$.
The function $x\mapsto |r^{-1}(x)|$ is thus constant along the orbits of $G$ on $X$. Thus the contribution of a single orbit $G\cdot x_0$ to the sum $\sum_x|r^{-1}(x)|$ is $|G_{x_0}|\cdot |G\cdot x_0|=|G|$. This shows that
$$ \sum_{x\in X} |r^{-1}(x)|= |G|\times \mbox{the number of orbits} =|G|\times |G\backslash X|. $$
The desired conclusion now follows from (\ref{1}). $\Box$
I can now discuss the problem that prompted this post. It is about certain planar lattice walks. The allowable steps of this walk belong to the collection $\newcommand{\eS}{\mathscr{S}}$ $\newcommand{\be}{\boldsymbol{e}}$ $\newcommand{\bR}{\mathbb{R}}$ $\newcommand{\bs}{\boldsymbol{s}}$
$$\eS=\lbrace \pm\be_1,\pm\be_2\rbrace\subset \bR^2,\;\;\be_1=(1,0),\;\;\be_2=(0,1). $$
A walk of length $n$ is then an ordered collection of steps
$$\vec{\bs}= (\bs_1,\dotsc, \bs_n)\in\eS^n. $$
The above walk is called admissible if
$$ \bs_j+\bs_{j-1}\neq 0,\;\;\forall j=2,\dotsc, n. \tag{2}\label{2} $$
We denote by $\newcommand{\eA}{\mathscr{A}}$ $\eA_n$ the set of admissible walks of length $n$. Since $\bs_1$ can be chosen in four different ways, while each of the following steps can be chosen in three different ways so as to preserve (\ref{2}) we deduce
$$ |\eA_n|= 4\cdot 3^{n-1}. \tag{3}\label{3} $$
There is however a symmetry in the story, i.e., a group acting on $\eA_n$. $\newcommand{\eO}{\mathscr{\eO}}$ Denote by $G_0$ the subgroup of $O(2)$ generated by the reflections $R_0, R_1, R_2$ where
$$R_0\be_1=\be_2,\;\;R_0\be_2=\be_1, $$
$$R_1\be_1=\be_1,\;\;R_1\be_2=-\be_2, $$
$$R_2\be_1=-\be_1,\;\;R_2\be_2=-\be_2. $$
This group has order $8$ and can be identified with the Weyl group of $O(4)$.
The group $G_0$ acts on $\bR^2$ and $\eS\subset \bR^2$ is a $G_0$-invariant subset. In particular, $G_0$ acts on the set $\eS^n$ of walks of length $n$, and $\eA_n\subset \eS^n$ is $G_0$-invariant. Observe that if $g\in G_0$ then
$$\eS^g= \begin{cases} \eS, & g=1\\
\{\pm \be_1\} & g=R_1,\\
\{\pm \be_2\}, & g=R_2\\
\emptyset, & g\neq 1,R_1,R_2.
\end{cases} \tag{4} \label{4} $$
There exists another involution $R_3$ that acts on $\eS^n$. More precisely
$$R_3(\bs_1,\dotsc,\bs_n)=(\bs_n,\dotsc,\bs_1). $$
Clearly $R_3\eA_n\subset\eA_n$. We denote by $G$ the subgroup of the group of permutations of $\eA_n$ generated by $G_0$ and $R_3$. Since obviously $R_3$ commutes with all of the reflections $R_0,R_1, R_2$ we deduce that $G\cong G_0\times (\bZ/2). $
We would like to compute the number of orbits of the action of $G$ on $\eA_n$. We denote by $p_n$ this number. The final answer is contained in the equalities (\ref{odd}) and (\ref{even}) below which show different behaviors depending on whether $n$ is odd or even. Here are the details.
For any $\gamma\in G$ we denote by $\eA_n(\gamma)$ the set of admissible paths of length $n$ fixed by $\gamma$ and we set $p_n(\gamma):=|\eA_n(\gamma)|$. From Burnside's lemma we deduce
$$ p_n=\frac{1}{16} \sum_{\gamma\in G} p_n(\gamma).\tag{5}\label{5} $$
We need to compute the numbers $p_n(g)$. We distinguish two cases.
A. $\gamma\in G_0$. If $\gamma=1$, then
$$p_n(1)= |\eA_n|. $$
Suppose that $\gamma\neq 1$. Then $\vec{\bs}\in\eA_n(\gamma)\subset \eS^n$ iff
$$ \gamma\bs_j=\bs_j,\;\;\forall j=1,\dotsc, n. $$
According to (\ref{4}) the only nontrivial elements of $G_0$ that have fixed points when acting on $\eS$ are $R_1$, $R_2$. The only admissible paths of length $1$ that are $R_j$-invariant, $j=1,2$ are
$$(\be_j,\dotsc,\be_j),\;\;(-\be_j,\dotsc,-\be_j). $$ Hence, if $\gamma\in G_0$, then
$$ p_n(\gamma)=\begin{cases}
|\eA_n|, & \gamma=1\\
2, & \gamma=R_1,R_2,\\
0, & \mbox{otherwise}.
\end{cases} \tag{6}\label{6} $$
B. $\gamma=(g,R_3)$, $g\in G_0$.
Hence $\newcommand{\Llra}{\Longleftrightarrow}$
$$ \vec{\bs}\in \eA_n(g, R_3)\Llra R_3\vec{\bs}=g\vec{\bs}. $$
If $h\in G_0$, $\vec{\bs}\in\eA_n(g,R_3)$ and $\newcommand{\si}{\boldsymbol{\sigma}}$ we set $\vec{\si} = h\vec{\bs}$, then
$$ R_3\vec{\si}= R_3 h \vec{\bs}= h R_3 \vec{\bs}= hg \vec{\bs}= hgh^{-1} \vec{\si}. $$
This shows that
$$|\eA_n(g,R_3)|=|\eA_n(hgh^{-1}, R_3)|,\;\;\forall g,h\in G_0.\tag{7}\label{7} $$
This shows that the map $G_0\ni g\mapsto |\eA_n(g, R_3)|$ is constant on the conjugacy classes of $G_0$. Let us describe these conjugacy classes. It helps to observe that the morphism $\det :O(2)\to\{\pm 1\}$ induces a morphism
$$ \det :G_0\to\{\pm 1\} $$
and this morphism is constant on the conjugacy classes. There exist two conjugacy classes of determinant $-1$
$$ C(R_1)=\{ R_1, R_2=-R_1\},\;\; C(R_0)=\{R_0, -R_0\}.$$
The other conjugacy classes are
$$ C_1=\{1\},\;\; C_{-1}= \{-1\}, \;\; C=\{ J, -J\}, $$
where $J= RR_1$ is the counterclockwise rotation by $\pi/2$. Thus we need to compute the five numbers
$$p_n(\pm 1,R_3), \; p_n(R_1,R_3), \; p_n(R_0,\; R_3), \; p_n(J, R_3). $$
We discuss them separately. Set $m:=\lfloor (n+1)/2\rfloor$
$\eA_n(1,R_3).$ A walk $\vec{\bs}\in \eA_n(1,R_3)$ is determined by the initial segment of length $m$ which could be an arbitrary walk in $\eA_m$.
For $n$ even, $n=2m$, a walk $\vec{\bs}\in \eA_n(1,R_3)$ if and only if it has the form
$$\vec{\bs}=(\bs_1,\dotsc, \bs_{m-1},\bs_m,\bs_{m},\bs_{m-1},\dotsc, \bs_1),\;\;(\bs_1,\dotsc,\bs_m)\in\eA_m. $$
For $n$ odd, $n=2m-1$, a walk $\vec{\bs}\in \eA_n(1,R_3)$ if and only if it has the form
$$ \vec{\bs}=(\bs_1,\dotsc, \bs_{m-1},\bs_m,\bs_{m-1},\dotsc, \bs_1),\;\;(\bs_1,\dotsc,\bs_m)\in\eA_m. $$.
Hence
$$ p_n(1, R_3)= |\eA_m|= 4\cdot 3^{\lfloor(n+1)/2\rfloor -1}. \tag{8}\label{8} $$
$\eA_n(-1,R_3).$ Such a path is again determined by the initial segment of length $m$.
For $n$ even, $n=2m$, if $\vec{\bs}\in \eA_n(-1,R_3)$, then
$$\vec{\bs}=(\bs_1,\dotsc, \bs_{m-1},\bs_m,-\bs_{m},-\bs_{m-1},\dotsc, -\bs_1),\;\;(\bs_1,\dotsc,\bs_m)\in\eA_m. $$
Clearly such a path is not admissible. Hence $\eA_m(-1, R_3)=\emptyset$ if $n$ is even.
If $n$ is odd, $n=2m-1$, and $\vec{\bs}\in\eA_n(-1,R_3)$, then $\bs_m=-\bs_m$. Not possible!.
Hence
$$ p_n(-1,R_3)=0,\;\;\forall n. \tag{9}\label{9} $$
$\eA_n(R_1,R_3). $ A path $\vec{\bs}=(\bs_1,\dotsc,\bs_n)\in\eA_n(R_1, R_3)$ is determined by initial segment of length $m$.
For $n$ even, $n=2m$, if $\vec{\bs}\in \eA_n(-1,R_3)$, then
$$ \vec{\bs}=(\bs_1,\dotsc, \bs_{m-1},\bs_m,R_1\bs_{m},R_1\bs_{m-1},\dotsc, R_1\bs_1),\;\;(\bs_1,\dotsc,\bs_m)\in\eA_m. $$
Such a path is admissible if and only if $\bs_m+R_1\bs_m\neq 0$, i.e., $\bs_m=\pm\be_1$. The number of admissible paths $(\bs_1,\dotsc,\bs_m)$ which end with $\bs_m=\pm\be_1$ is $2\cdot 3^{m-1}$.
For $n$ odd, $n=2m-1$, if $\vec{\bs}\in \eA_n(-1,R_3)$, then
$$\vec{\bs}=(\bs_1,\dotsc,\bs_{m-1}\,\bs_m, R_1\bs_{m-1},\dotsc, R_1\bs_1),\;\;\bs_m=R_1\bs_m.$$
We deduce
$$ p_n(R_1,R_3) =2\cdot 3^{m-1},\;\;m=\lfloor(n+1)/2\rfloor. \tag{10}\label{10} $$
$\eA_n(R_0,R_3). $ Arguing as above we deduce that if $(\bs_1,\dotsc,\bs_n)\in\eA(R_0,R_3)$ and $n$ is odd, then $R_0\bs_m=\bs_m$ which is impossible because $R_0$ does not have fixed points on $\eS$.
For $n$ even, $n=2m$, $\vec{\bs}=(\bs_1,\dotsc,\bs_n)\in \eA_n(R_0,R_3)$ if and only if
$$\vec{\bs}=(\bs_1,\dotsc,\bs_{m-1}\bs_m,R_0\bs_m, R_0\bs_{m-1},\dotsc, R_0\bs_1),\;\; (\bs_1,\dotsc,\bs_m,R_0\bs_m)\in \eA_m. $$
Whatever $\bs_m\in\eS$, we have $\bs_m+R_0\bs_m\neq 0$. We deduce
$$ p_n(R_0, R_3)=\begin{cases}
0, & n=2m-1\\
4\cdot 3^{m-1}, & n=2m.
\end{cases} \tag{11}\label{11} $$
$\eA_n(J,R_3). $ We observe that
$$(\bs_1,\dotsc,\bs_n)\in\eA_n(J, R_3)\Llra (J\bs_n,\dotsc, J\bs_1)=(\bs_1,\dotsc,\bs_n). $$
This implies $J^2\bs_n=\bs_n$ which is obviously impossible. Hence
$$ p_n(J, R_3) =0,\;\;\forall n. \tag{12}\label{12} $$
Using (\ref{5}) and (\ref{6}) we deduce
$$ p_n=\frac{1}{16}\Bigl( 4\cdot 3^{n-1}+4 +p_n(1,R_3)+ p_n(-1,R_3)+ 2p_n(R_1,R_3) +2p_n(R_0,R_3) +2p_n(J)\Bigr) $$
$$= \frac{1}{16}\Bigl( 4\cdot 3^{n-1}+4 +p_n(1,R_3)+ 2p_n(R_1,R_3) +2p_n(R_0,R_3) \Bigr). $$
Using (\ref{8}), (\ref{9}), (\ref{10}), (\ref{11}), (\ref{12}) in the above equality we deduce the following.
If $n=2m-1$, then
$$ p_n= \frac{1}{16}\Bigl( 4\cdot 3^{n-1} + 4 + 8\cdot 3^{m-1}\Bigr) = \frac{1}{4}\bigl(\,3^{n-1}+2\cdot 3^{m-1}+1\bigr).\tag{$\ast$}\label{odd}$$
If $n=2m$, then
$$ p_n= \frac{1}{16}\Bigl( 4\cdot 3^{n-1} + 4 + 16\cdot 3^{m-1}\Bigr) = \frac{1}{4}\bigl(\,3^{n-1}+4\cdot 3^{m-1}+1\bigr). \tag{$\ast\ast$}\label{even}$$
No comments:
Post a Comment