2
$\begingroup$

I need some assistance with the following problem.

Problem: How many lattice paths from $(0,0)$ to $(n,n)$ with steps up and to the right are there when two paths are considered equal if one can be moved on top of the other by a rotation or a reflection?

Attempts:

1) Using Burnside's Lemma

Burnside's Lemma: Let $G$ be a permutation group acting on a set $S$. Then the number of orbits of $S$ under the action of $G$ is equal to $$ \frac{1}{|G|}\sum_{g\in G}|F_g| $$ with $F_g=\{i\in S|g(i)=i\}$. (Introduction to Enumerative Combinatorics, Bóna, pg. 424)

Description of attempt:

I have tried to compare this problem to the following problem.

We color the sides of a square either red or blue. We consider two coloring equivalent if there is symmetry (rotation or reflection) that takes one coloring into the other. How many nonequivalent colorings are there?

In this problem, one uses $G=D_4$ (square, not 2-gon) and examines $F_g\,\forall g\in D_4$. The solution comes up with $$ \sum_{g\in G}|F_g|=48\Rightarrow\frac{1}{|G|}\sum_{g\in G}=6 $$ In the problem I'm trying to solve, for the $n=2$ case, there are 6 paths from $(0,0)$ to $(2,2)$. They are $(0,0)-(0,2)-(2,2)$, $(0,0)-(0,1)-(2,1)-(2,2)$, $(0,0)-(0,1)-(1,1)-(1,2)-(2,2)$, $(0,0)-(2,0)-(2,2)$, $(0,0)-(1,0)-(1,2)-(2,2)$, and $(0,0)-(1,0)-(1,1)-(2,1)-(2,2)$. Examining $F_g$ for all elements in $G=D_4$, I get that $id$ fixes 6 paths, $r^2$ (180$^\circ$) fixes 2 paths, and the \ diagonal ($x+y=0$) fixes 4 paths. $r$ (90$^\circ$) and $r^3$ (270$^\circ$) don't fix anything. Also, if you use the reflections across the horizontal and vertical lines, you get paths that use left or down. Thus, $$ \sum_{g\in G}|F_g|=12 $$ However, $8\nmid 12$.

What am I doing wrong here?

2) Not using Burnside's Lemma :]

Let's look at the $n=2$ case again. If reflect half of the paths listed above across the $x=y$ diagonal, I get the other half. Thus, we really only need to examine half the paths. For the $n=2$ case, it turns out that there are 3 fundamentally different paths. Hooray! For the $n=3$ case, there are $$ {2n\choose n}={6\choose 3}=20 $$ paths from $(0,0)$ to $(3,3)$. From the argument above, we only need to examine 10 of them. It turns out that there are 7 fundamentally different paths. However, for a general $n$, how do I determine which paths are fundamentally different out of half the paths?

Above are two methods I have tried. It's possible that I'm overlooking something silly. I'm not asking for a solution. I just want a point in the right direction.

Thank you!

$\endgroup$
1
  • $\begingroup$ Every reflection is a unique path, so it's only rotations we really need to look at. Rotations are symmetric around the point $\left(\frac{n}{2}, \frac{n}{2}\right)$, meaning we can identify two identical parts of the path $\endgroup$ – Joseph Camacho Dec 10 '19 at 21:08
0
$\begingroup$

This is a very well-posed question.

The problem in your attempt to apply Burnside's lemma is that you're not actually considering a group action. You apply some of the elements of $D_4$ to the paths, find that this takes you outside the set of paths composed of up and right steps, but don't add these new paths to the set being acted on. Thus you aren't actually considering a set on which the group $D_4$ acts.

There are two possible remedies: Expand the set or shrink the group. Shrinking the group leads to fewer complications and less counting effort, so let's do that: The vertical and horizontal reflections and the rotations through odd multiples of $\frac\pi2$ don't leave any paths invariant, so let's ditch them. That leaves $D_2$, with $|D_2|=4$, and now your total of $12$ fixed paths yields the correct count of $3$ orbits.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.