- #1

fresh_42

Mentor

- 15,351

- 13,383

Hint: e.g. consider chains of ##p## coloured pearls where ##a## is the number of colours.

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Constructive Proofs
- Thread starter fresh_42
- Start date

- #1

fresh_42

Mentor

- 15,351

- 13,383

Hint: e.g. consider chains of ##p## coloured pearls where ##a## is the number of colours.

- #2

- 334

- 44

$$N = \frac{1}{\vert G\vert} \sum_{k, 0 \le k \le p-1} F(\tau^k)$$

where ##N## is the number of orbits and ##F(\tau^k)## is the number of chains fixed by ##\tau^k##. Observe,

##F(1) = a^p## and for ##k > 0## we have ##F(\tau^k) = a## (since ##p## is prime we counted the number of mono color chains). Hence,

$$N = \frac1p(a^p + (p-1)a)$$

Rearranging and subtracting ##pa## on both sides gives

$$pN - pa = a^p - a$$

which implies ##p \vert (a^p - a)##. []

Edit: i'm sorry I just read the guidelines that maybe this post was for high school? I just learned Burnside's lemma and thought this would be a good way to practice, but feel free to delete what I wrote if i should not have posted.

- #3

fresh_42

Mentor

- 15,351

- 13,383

For all high schoolers who want to try:

Distinguish unicoloured chains and those with at least two colours. Then count the possibilities to get a new, different sorting by a shift and group them.

Side effect: If you will have done so, you automatically get an insight on how Burnside's Lemma works.

Share:

- Replies
- 2

- Views
- 256

- Replies
- 4

- Views
- 122

- Replies
- 1

- Views
- 214