Permutation cycle type puzzle

Posted by: JBL | August 5, 2015

Permutation cycle type puzzle

Suppose that $w$ is a permutation with 8 cycles, all of whose lengths divide 12. If $w^2$ has 13 cycles, $w^3$ has 16, $w^4$ has 15, $w^6$ has 25, and $w^{12}$ has 27, what is the cycle type of w?
What can we say if we drop the guarantee that all cycle lengths divide 12?

Posted in Combinatorics | Tags: cycle type, cycles, permutations, puzzles

Responses

Hm, say there are A 1s, B 2s, C 3s, D 4s, E 6s, F 12s.

A+B+C+D+E+F = 8
A+2B+C+2D+2E+2F = 13
A+B+3C+D+3E+3F = 16
A+2B+C+4D+2E+4F = 15
A+2B+3C+2D+6E+6F = 25
A+2B+3C+4E+6E+12F = 27

This has a unique solution (1,1,2,2,3,-1). What did I do wrong?

I bet row-reducing this matrix amounts to computing the standard Mobius function…
By: Allen Knutson on August 6, 2015
at 5:12 AM
Just arithmetic, probably: your proposed solution doesn’t satisfy the last equation.

I had thought it was going to be just the usual Moebius function (or a simple twist), but it seems a little bit more complicated. I believe you would get mu if I gave you data on number of fixed points instead of number of cycles.
By: JBL on August 6, 2015
at 9:07 AM
Oh, I understand your last comment now. Yes, that’s exactly what’s going on; the matrix in question is the product of the zeta matrix for divisibility relation, a diagonal matrix, and the transpose of the zeta matrix, so when you row-reduce you’re exactly doing some Möbius inversion
By: JBL on August 7, 2015
at 8:17 PM

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out / Change )

You are commenting using your Twitter account. ( Log Out / Change )

You are commenting using your Facebook account. ( Log Out / Change )

Cancel

Connecting to %s

Concrete Nonsense