The number of permutations of [n] of odd order (or equivalently, the number with all cycle lengths odd) is given by (n-1)2(n-3)2...12 if n is even, and n(n-2)2(n-4)2...12 if n is odd. The sequence begins 1, 1, 1, 3, 9, 45, 225, 1575, ..., which is A000246 in Sloane's encyclopedia.
How fast does this grow? Well, it's not hard to show (from Stirling's formula) that if a(n) is the number of permutations of [n], then a(n)/n! is asymptotic to (2/πn)1/2. Since there are n! permutations of [n], that's the asymptotic probability that a randomly chosen permutation is of odd order. Alternatively, a(n) is asymptotic to 2(n/e)n. So log a(n) ~ log 2 + n(log n - 1).
And you can quickly "graph" log a(n) by just looking at the table of the first 100 values. The length of a(n), when written in base 10, is proportional to log n (precisely, it's log n / log 10). So the length of a(n) when written in decimal should grow a bit faster than linearly.
Indeed, if you zoom out from that table, that's exactly what you see -- the table's not quite a triangle, but it's close. Of course this trick isn't really so useful -- how often is one going to have a sequence that we can compute exactly but don't have any idea how large the logarithm is? -- but I think it's kind of cute.
10 May 2008
Subscribe to:
Post Comments (Atom)
1 comment:
This is obviously wrong. If n is odd, there is no "2" in n,n-2,n-4,... :-/
Post a Comment