Euler's Partition Theorem

[Swammerdami]

I've admired Ipetrich's posts developing areas of math; and decided to try my hand. Wish me luck! The first two posts in the thread are background; the third is a proof via generating functions. The 4th post will be the proof by constructing a bijection but I'll delay it, hoping TFT'ers might rediscover it themselves!

I've chosen Euler's Partition Theorem to review, but won't even begin its discussion until the 2nd post. First we need to review Generating Functions.

(①+②+③+④+⑤+⑥) describes the roll of a die; and (①+②+③+④+⑤+⑥)² describes the roll of two dice; expand this as you would an ordinary such an expression and get 36 terms including ①①, ①②, ②①, etc.
Similarly (①+②+③+④+⑤+⑥)³ describes the toss of three dice.

Now make the substitutions ① = z; ② = z²; ③ = z³; ... ⑫ = z¹². The roll of two dice becomes

(①+②+③+④+⑤+⑥)²
. . . . = (z+z²+z³+z⁴+z⁵+z⁶)²
. . . . = (1·z² + 2·z³ + 3·z⁴ + 4·z⁵ + 5·z⁶ + 6·z⁷ + 5·z⁸ + 4·z⁹ + 3·z¹⁰ + 2·z¹¹ + 1·z¹²)
. . . . = (1·② + 2·③ + 3·④ + 4·⑤ + 5·⑥ + 6·⑦ + 5·⑧ + 4·⑨ + 3·⑩ + 2·⑪ + 1·⑫)

That final formula will be very familiar to those who have studied the arithmetic of games like Craps or Backgammon.

Generating expressions are manipulated like ordinary algebra expressions, but the variables (② etc. and z in our example) aren't proxies for numbers: they're just symbols.

A generating function is a device somewhat similar to a bag. Instead of carrying many little objects detachedly, which could be embarrassing, we put them all in a bag, and then we have only one object to carry, the bag.

A generating function is a clothesline on which we hang up a sequence of numbers for display.

Generating functions were first used by Abraham DeMoivre and Johann Lambert but it was the great Leonhard Euler who made them into almost an art form, and used them to build many splendid proofs. The famous relationship between prime numbers and Riemann's zeta function began with a splendid identity of generating functions discovered by Euler.

 

[Swammerdami]

In 1999 two mathematicians presented their list of "The Hundred Greatest Theorems" at a math conference. Their ranking is based on the following criteria: "the place the theorem holds in the literature, the quality of the proof, and the unexpectedness of the result." Of the 100 theorems, 7 were first proved by Leonhard Euler (and several of his most famous results aren't even listed). He is rightfully called the most prolific mathematician ever. (Euclid is credited with 8 theorems on the list but some of those were not his own work. Cauchy is in 3rd place with 4; Cantor, Leibniz, Lagrange, Gauss have 3 each.)

The theorems are ranked by "greatness." Most of the top twelve will be very familiar:

1. The Irrationality of the Square Root of 2 Pythagoras and his school 500 B.C.
2. Fundamental Theorem of Algebra Karl Frederich Gauss 1799
3. The Denumerability of the Rational Numbers Georg Cantor 1867
4. Pythagorean Theorem Pythagoras and his school 500 B.C.
5. Prime Number Theorem Jacques Hadamard and Charles-Jean de la Vallee Poussin (separately) 1896
6. Godel's Incompleteness Theorem Kurt Godel 1931
7. Law of Quadratic Reciprocity Karl Frederich Gauss 1801
8. The Impossibility of Trisecting the Angle and Doubling the Cube Pierre Wantzel 1837
9. The Area of a Circle Archimedes 225 B.C.
10. Eulers Generalization of Fermats Little Theorem (Fermats Little Theorem) Leonhard Euler ( Pierre de Fermat ) 1760 (1640)
11. The Infinitude of Primes Euclid 300 B.C.
12. The Independence of the Parallel Postulate Karl Frederich Gauss , Janos Bolyai , Nikolai Lobachevsky , G.F. Bernhard Riemann collectively 1870-1880

Some of the proofs are rather easy, some are very hard, but several fall into an intermediate area where amateur mathematicians may experience great delight. Among the delightful group is #45, Euler's Partition Theorem.

As the name implies, the theorem is about Partitions. We are interested in the number of partitions of a given size. There is one partition of 1 (1), two partitions of 2 (2 and 1+1), three partitions of 3 (3 and 2+1 and 1+1+1), five partitions of 4 (4 and 3+1 and 2+2 and 2+1+1 and 1+1+1+1) and so on. We can hang these counts on a clothesline by writing

\(\mathcal{P} = 1 + z + 2z^2 + 3z^3 + 5z^4 + \cdots \)
(It is convenient to say there is one partition of 0.)

Of the five partitions of 4, exactly two are partitions into distinct parts (4 and 3+1), and exactly two are partitions into only odd parts (3+1 and 1+1+1+1). Two = two!

Similarly there are exactly eight ways to partition 9 with no two parts equal:
9; 8+1; 7+2; 6+3; 6+2+1; 5+4; 5+3+1; 4+3+2
and eight ways to partition 9 into odd parts:
9; 7+1+1; 5+3+1; 5+1+1+1+1; 3+3+3; 3+3+1+1+1; 3+1+1+1+1+1+1; 1+1+1+1+1+1+1+1+1
Eight = eight! Coincidence? NO. Euler's Partition Theorem states

\(\mathcal{D} = \mathcal{O}\)
There are always exactly as many partitions of n into distinct parts as there are partitions of n into odd parts.

\(\mathcal{D} = \sum_{n=0}^{\infty} d_n z^n = 1 + z + z^{2} + 2z^{3} + 2z^{4} + 3z^{5} + 4z^{6} + 5z^{7} + 6z^{8} + 8z^{9} + 10z^{10} + 12z^{11} + \cdots\)
where d_n is the number of partitions of n into distinct parts.

\(\mathcal{O} = \sum_{n=0}^{\infty} o_n z^n = 1 + z + z^{2} + 2z^{3} + 2z^{4} + 3z^{5} + 4z^{6} + 5z^{7} + 6z^{8} + 8z^{9} + 10z^{10} + 12z^{11} + \cdots\)
where o_n is the number of partitions of n into odd parts.

There are two very elegant ways to prove this theorem. We can construct the generating functions for \(\mathcal{D}\) and \(\mathcal{O}\) and use algebraic manipulations to prove them equal. Or we can construct a bijection between the two sets. (If you successfully fit your hand into a glove you can demonstrate, by looking for unassigned fingers, that hand and glove have equal numbers of fingers!)

The proof by generating functions is of course due to Euler. The proof via elegant bijection I'm less certain of. (That's one reason I'm posting this thread at all. Can someone tell who first discovered such a bijection?) I think it was also Euler who discovered the bijection, but Google doesn't show me that explicitly. James Glaisher shows up, but his was a generalization of the Theorem; and J.J. Sylvester mentioned the bijection the year before Glaisher published.

Try to discover the elegant bijection yourselves! Hint: It's as simple as you could reasonably expect.

 

[Swammerdami]

Proof of Euler's Partition Theorem using generating functions

All the partitions whose parts are all 1 (i.e. 1, 1+1, 1+1+1, 1+1+1+1, ...) are generated by
\((1 + z + z^2 + z^3 + z^4 + \cdots)\).
Similarly, all the partitions with only 3 for parts are generated by
\((1 + z^3 + z^6 + z^9 + z^{12} + \cdots)\)
and the partitions with parts all 1 or 3 are generated by
\((1 + z + z^2 + z^3 + \cdots)(1 + z^3 + z^6 + z^9 + \cdots)\)
Repeat ad infinitum to get all the partitions into odd parts. Note that we need the 1 (the unique "partition" of 0) for this multiplication to work as desired.

The geometric-sum identity
\((1 + z + z^2 + z^3 + z^4 + \cdots) = \frac{1}{1 - z}\)
can be applied, even though our z's are symbols, not numbers. Thus
\(\mathcal{O} = (\frac{1}{1 - z}) (\frac{1}{1 - z^3}) (\frac{1}{1 - z^5}) (\frac{1}{1 - z^7}) \cdots\)
or
\(\mathcal{O} = \prod_{n=1}^{\infty}\frac{1}{1 - z^{(2n-1)}} \)
This expression has only odd powers of z in the denominator. We can fix that by multiplying by ((1-z^2/(1-z^2) and various other forms of the "harmless" multiplier, 1:
\(\mathcal{O} = \frac{1}{1 - z} \cdot \frac{1 - z^2}{1 - z^2}\cdot \frac{1}{1 - z^3} \cdot \frac{1 - z^4}{1 - z^4} \cdot \frac{1}{1 - z^5} \cdot \frac{1 - z^6}{1 - z^6} \cdot \cdots = \prod_{n=1}^{\infty} \frac{1 - z^{2n}}{1 - z^n} \)

So we have a concise expression for partitions into odd parts. Let's do distinct parts.

\((1 + z)\) admits either zero or one part of 1; \((1 + z^2)\) admits zero or one part of 2; and so on. Thus all partitions with no part duplicated are generated by
\(\mathcal{D} = \prod_{n=1}^{\infty} (1 + z^n) \)

Now recall the difference-of-two squares formula \((1 + x) = \frac{1 - x^2}{1 - x}\) and rewrite to get
\(\mathcal{D} = \prod_{n=1}^{\infty} \frac{1 - z^{2n}}{1 - z^n} \)

Presto! As if by magic: \(\mathcal{D} = \mathcal{O}\). Q.E.D.


That didn't take me so long after all.
I'll defer the proof by constructing a bijection for a day or two hoping TFT'ers will have the thrill of discovering it themselves.

 

[lpetrich]

Great job. I liked the LaTeX formatting. But I'm stumped about that bijection.

Here is the generating function for partitions in general:
\(\mathcal{O} = \prod_{n=1}^{\infty} \frac{1}{1 - z^n} \)

Here is an application of partitions: permutations. Every permutation can be decomposed into a set of cyclic permutations, and the lengths of those cycles add up to the total length of the permutation. Thus, how many sets of cycle lengths is the number of partitions of the total length.

Permutations may be divided up into even and odd permutations, depending on whether they are the product of an even or an odd number of interchange permutations.

Here are some permutation puzzles.

• How many permutations are there with each length?
• How many permutations are there for each set of cycle lengths?
• Any nice generator functions for those counts?
• How many even and odd permutations are there in the set of all permutations of some number of symbols?
• How can one tell whether or not a permutation is even or odd from its cycle lengths?
• What is the minimum number of interchange permutations needed to make some permutation?

 

[Swammerdami]

Here are some of Ipetrich's questions with my non-answers.

* How many permutations are there for each set of cycle lengths?
There is a straightforward but somewhat cumbersome recursive formula for this.

* Any nice generator functions for those counts?
Probably. I lack the time and talent to hunt for them now; and Googling for an answer would seem like cheating!

* How can one tell whether or not a permutation is even or odd from its cycle lengths?
It's odd if it has an odd number of even cycles.

If you don't like odd permutations, you can swap any element with itself to get an even number of exchanges! (This might be useful when exploring spaces of orthogonal transforms, to get rid of the mirror forms with negative determinants.)


There are many great brain-teasers involving permutations. Speaking of Leonhard Euler, there is the question of the Misaddressed Envelopes: If 100 addressed letters are stuffed into 100 addressed envelopes at random, what is the chance that NONE of the letters is correctly placed? (This is Problem #6 in 100 Great Problems of Elementary Mathematics by Heinrich Dörrie — a must-have book for mathematicians at all levels. I'd intended to plug that book by linking to the page with Problem #6, but Google Books has changed its interface and I no longer know how to link to Page 19. "Classic Google Books" works better, of course, than "New Google Books" but still prevents the by-page link AFAICT.)

Here's another great brain-teaser: Difficult (mind-boggling), but the hint that permutations are relevant should help.

There are 100 prisoners, and the warden has lined up photos of all the prisoners (i.e. 100 photos) face down in on a table in a room. Each prisoner in turn goes into the room and must turn over 50 photos in succession, then leave the room. Photos are returned to the original position, face down, before the next prisoner begins his turn. If EVERY prisoner can find his own photo they can all go free, while if just ONE fails they are ALL executed! Prisoners can agree a strategy up front, but there's no communication once the game begins (there is no secret communication between the prisoners, so the results of any prisoner's attempts are not known to any other prisoners...) What is the best strategy for the prisoners, and what chance does this give for their survival?

Each prisoner has a 1/2 chance of failing, and so it seems at first that as more prisoners have a go the chances of them ALL succeeding would be dropping something like exponentially. And with 100 prisoners having to face the trial, surely whatever strategy they use, the chances of EVERYBODY succeeding must be vanishingly small! Well ... ?

 

[lpetrich]

How many permutations are there with each length?

For length n, there are n! permutations.

How many permutations are there for each set of cycle lengths?

For cycle lengths {m1, m2, ...} - m1 cycles of length 1, m2 of length 2, ... - it is

\( N(\{m\}) = n! / \prod_k k^{m_k} (m_k)! \)

where the total number

\( n = \sum_k k m_k \)

Any nice generator functions for those counts?

\( \exp \left( \sum_k \frac{t_k}{k} \right) = \sum N(\{m\}) \frac{(t_1)^{m_1} (t_2)^{m_2} \cdots}{n!} \)

How many even and odd permutations are there in the set of all permutations of some number of symbols?

Even and odd permutations are products of even and odd numbers of interchanges. Calling the set of even ones E and odd ones O, let us compare their sizes. Multiplying every member of E by some odd permutation gives a subset of O, and multiplying every member of O by some odd permutation gives a subset of E. The set sizes thus satisfy inequalities |E| >= |O| and |O| >= |E|, thus giving |E| = |O|.

Since the numbers of even and odd permutations are equal, they must therefore be 1/2 of the total number, n! for length n.

The only exception is for length 1. There is one even permutation and no odd permutations.

How can one tell whether or not a permutation is even or odd from its cycle lengths?

Let us start with cyclic permutations. A cycle of length k can be formed by multiplying (k-1) interchange permutations. Thus, every odd-length cycle is an even permutation and every even-length cycle is an odd one.

Thus, whether a permutation is even or odd is whether the number of even-length permutations is even or odd.

What is the minimum number of interchange permutations needed to make some permutation?

This number is

\( p = \sum_k m_k (k-1) = \sum_k m_k k - \sum_k m_k = n - m \)

for length n and number of cycles m.

 

[lpetrich]

There are many great brain-teasers involving permutations. Speaking of Leonhard Euler, there is the question of the Misaddressed Envelopes: If 100 addressed letters are stuffed into 100 addressed envelopes at random, what is the chance that NONE of the letters is correctly placed? (This is Problem #6 in 100 Great Problems of Elementary Mathematics by Heinrich Dörrie — a must-have book for mathematicians at all levels. I'd intended to plug that book by linking to the page with Problem #6, but Google Books has changed its interface and I no longer know how to link to Page 19. "Classic Google Books" works better, of course, than "New Google Books" but still prevents the by-page link AFAICT.)

For that, we need to find out how many permutations with length 100 that have no 1-cycles. I will solve that problem for length n.

Getting back to the generating function, set
\(t_k = t^k\)

That gives us
\( \frac{1}{1-t} = \sum_n \frac{N(n)}{n!} \)

where N is the total number of permutations with length n. Now set t1 = 0 while leaving the other t's unchanged. This gives us
\( \frac{e^{-t}}{1-t} = \sum_n \frac{N'(n)}{n!} \)

for N' permutations having no 1-cycles. The total number of such permutations is thus
\( N'(n) = n! \sum_{k=0}^n \frac{(-1)^k}{k!} \sim \frac{n!}{e} \)

Thus, N' ~ N/e in the limit of large n.

Thus, in that problem, there is a 37% chance that none of the letters is correctly placed, and for n larger than 5, that fraction is less than 1% off.

 

[Swammerdami]

As Google Books becomes increasingly annoying and useless, it is good to know that Archive.Org is taking up the slackl

Here is a link to Problem 6 in the must-buy book by Heinrich Dörrie.

I suppose the company which once had the motto "Don't Be Evil" justifies its nastiness on the grounds that the work might be copyrighted. But they paid no royalties when they illegally copied it many years ago. Anyway Herr Dörrie, if not his translater, died in 1955 so I don't think he'll mind if you take a peek before buying.

 

[lpetrich]

The first problem in that book was considered a very difficult problem in antiquity. But with present-day computer-algebra software, it is almost trivial.

Archimedes's Bovine Problem

The sun god had a herd of cattle consisting of bulls and cows, one part of which was white, a second black, a third spotted, and a fourth brown.

Among the bulls, the number of white ones was one half plus one third the number of the black greater than the brown ; the number of the black, one quarter plus one fifth the number of the spotted greater than the brown ; the number of the spotted, one sixth and one seventh the number of the white greater than the brown.

Among the cows, the number of white ones was one third plus one quarter of the total black cattle ; the number of the black, one quarter plus one fifth the total of the spotted cattle ; the number of the spotted, one fifth plus one sixth the total of the brown cattle; the number of the brown, one sixth plus one seventh the total of the white cattle.

What was the composition of the herd?

In Mathematica notation, the problem may be stated:

{wb == (1/2 + 1/3)*bb + rb, bb == (1/4 + 1/5)*sb + rb, sb == (1/6 + 1/7)*wb + rb, wc == (1/3 + 1/4)*(bb + bc), bc == (1/4 + 1/5)*(sb + sc), sc == (1/5 + 1/6)*(rb + rc), rc == (1/6 + 1/7)*(wb + wc)}

where w, b, s, r for white, black, spotted, and brown, and b, c for bull, cow.

This is 7 linear equations with 8 variables, and outside of degenerate cases, the solution will have one parameter. The numbers of colors and sexes of bovine are all proportional to some number, though to be physically meaningful, those numbers must be nonnegative integers. Negative integers would be OK for debts, however.

Solving the first three equations for the number of brown bulls gives us

wb = 742/297*rb, bb = 178/99*rb, sb = 1580/891*rb

Since all these numbers must be integers, the number of brown bulls must be proportional to 891, giving us

wb = 2,226*n, bb = 1,602*n, sb = 1,580*n, rb = 891*n

with a total of 6,299*n

The full solution is

wb = 10,366,482*n, bb = 7,460,514*n, sb = 7,358,060*n, rb = 4,149,387*n, wc = 7,206,360*n, bc = 4,893,246*n, sc = 3,515,820*n, bc = 5,439,213*n

with a total of 50,389,082*n

 

[Swammerdami]

The 100 Great Elementary Problems in Dörrie's book are similar to the 100 Greatest Theorems mentioned earlier in the thread, in one way: Some are too easy; some are much too hard (e is transcendental anyone?); but many are just right. Some are of great importance and/or historical interest.

In this thread, we are left with two unsolved puzzles:
(1) A method for the 100 prisoners to maximize their chance of finding all 100 photos.
(2) An elegant bijection from D_n (partitions of n into distinct parts) to O_n (n's partitions into odd parts).
I won't spoiler either problem now, but will practice my LaTeX with a few remarks about bijections.

A bijection is a function \(f: D \rightarrow \rightarrow E\) which is one-to-one and onto. This means
f must be

• a proper function, i.e.
  \(\forall x \in D, f(x) \in E\)
• injective, i.e.
  \(\forall x, x' \in E, f(x) = f(x') \Rightarrow x = x'\)
• surjective, i.e.
  \(\forall y \in E, \exists x, f(x) = y\)

When D and E are finite, a bijection exists if and only if D and E have the same size (cardinality). Any injection f will be a bijection, with its reversed expression being \(f^{-1}: E \rightarrow \rightarrow D\). The craft is to find an elegant such bijection, e.g. as in the solution to the problem posed.

(If D and E are infinite, the existence of injections in both directions guarantees there is a bijection, but neither injection need be a bijection. From the two injections a bijection can be constructed using the Cantor-König constructive version of CSB. The guarantee is made by the very famous and important Schröder-Bernstein (CSB) Theorem, #25 on afore-mentioned list of Greatest Theorems.)

To prove that a function is injective and surjective may be slightly tedious, but there is a faster, simpler way! Given a function f, and a clear-cut well-behaved inverse function f^-1, f must be a bijection. The target function in this thread, mapping distinct partitions to odd partitions, is quite simple, and its inverse f^-1 is readily found.


No more hints on that; all below is just commentary on the infinite case of the Schröder-Bernstein Theorem mentioned earlier.

First, the theorem's very name is confused. Dedekind and Cantor each proved it before either Bernstein or Schröder did; and Schröder's proof wasn't even correct. Bernstein does deserve good credit: His was the first proof not to use the Axiom of Choice. (This was in the days before AC was well recognized.)

Find a bijection from the positive rationals Q to the counting numbers N.
\(p/q \rightarrow 2^p3^q\) (p,q in lowest terms) is one injection, and \(m \rightarrow m/1\) an injection the other way, but their König composite is grotesque. Find a more elegant and straightforward bijection between rationals and integers. (As an example of some of the Hundred Greatest Theorems being too easy, this one is #3 !)

(We're missing some LaTeX symbols here, e.g. hookrightarrow. [I used rightarrow rightarrow ] Is there a list of what we have?)

 

[Swammerdami]

My hope is that this thread can be appreciated by non-mathematicians. For most of us, originally finding Euler's proof of his Partition Theorem using polynomial generating functions would be a huge coup, but once written down, the proof is easily understood and appreciated, right?

And the remaining puzzles don't even require the use of polynomial generating functions, let alone exponential generating functions. The thread wasn't originally about permutations, but let's present another puzzle on that topic.

In this thread, we are left with two unsolved puzzles:
(1) A method for the 100 prisoners to maximize their chance of finding all 100 photos. (Assume the warden has shuffled the photos randomly.)
(2) An elegant bijection from D_n (partitions of n into distinct parts) to O_n (n's partitions into odd parts).

The original thread puzzle, #2, has nothing to do with permutations, but here are some puzzles, easier than #1, to get some practice with very simple permutation counting (no generating functions needed).

(3) An airplane has 100 seats, each assigned to one of 100 passengers. One passenger — call him Donald — is a sociopath who insists on boarding first and takes seat #1 without even looking at his ticket. The other 99 passengers board one-by-one in a random order, and each takes his/her assigned seat if possible, but if it is occupied they pick a random unoccupied seat. What is the probability that the final passenger to board will find his originally-assigned seat available?

(4) How many permutations of an n-sized set are there?

(5) How many permutations of an n-sized set have an n-cycle?

(6) How many permutations of a 100-sized set have a cycle of length 57 exactly?

(7) After a proper shuffle, each possible permutation is equally likely.

#7 can be taken as a fact, rather than a conjecture requiring proof. With #4 - #7 as background, you should be able to solve #3.

#1 has a very surprising solution which baffles most skilled puzzle solvers, but becomes easier with the hint that permutations are involved, along with an Aha! on #6.


I hope someone (other than Ipetrich ) tries their hand at these puzzles!

 

[Swammerdami]

Proof of Euler's Partition Theorem by constructing a bijection

A partition of n into distinct parts can be mapped to a partition of n into odd parts by replacing each part (2^km) with 2^k copies of m, where m is odd.

The inverse of that function is simple. A partition will have w copies of each part of particular size m, where w has a unique binary representation, w = 2^k_1 + 2^k_2 + ... + 2^k_3 . Map each such cluster of same-sized parts to one part of size 2^k_1·m, a part of size 2^k_2·m, a part of size 2^k_3·m, and so on.

 

[Swammerdami]

I do want to mention one more point about Euler's Partition Theorem. One way to phrase that Theorem is

The two sets
(a) the set of partitions of n into parts all congruent to 1 or -1 modulo 2, and
(b) the set of partitions of n into parts differing from each other by at least 1
have the same size.​

This is almost identical — only two numbers change — to the following Theorem, one of the Rogers-Ramanujan Identities

The two sets
(a) the set of partitions of n into parts all congruent to 1 or -1 modulo 5, and
(b) the set of partitions of n into parts differing from each other by at least 2
have the same size.​

A generating function for the latter (b) is more difficult to find than other examples. Proving the latter theorem algebraically is difficult. In 1980 a bijection was presented (with much fanfare) to prove this Rogers-Ramanujan identity combinatorially, but the bijection is much more cumbersome than the bijection we saw for Euler's Partition Theorem.

 

[lpetrich]

(3) An airplane has 100 seats, each assigned to one of 100 passengers. One passenger — call him Donald — is a sociopath who insists on boarding first and takes seat #1 without even looking at his ticket. The other 99 passengers board one-by-one in a random order, and each takes his/her assigned seat if possible, but if it is occupied they pick a random unoccupied seat. What is the probability that the final passenger to board will find his originally-assigned seat available?

That's

(4) How many permutations of an n-sized set are there?

n!

(5) How many permutations of an n-sized set have an n-cycle?

From the formula for number of permutations, n!/n

This is from the permutation having only one cycle, the length-n one. This has a simple interpretation. One can start from anywhere in the cycle, and the n possible starting points means that one must divide the naive total number by n.

(6) How many permutations of a 100-sized set have a cycle of length 57 exactly?

This can be handled with the generator function. The alternative to that cycle's presence is its absence, and we can count up how many permutations lack it. That is straightforward with the generator function. With no length-m cycles and with all the others optionally present, I find

\( \frac{\exp\left(-t^m/m\right)}{1 - t} \)

This gives a number

\( N(\text{no m}) = n! \sum_{k=0}^{\text{floor}(n/m)} \frac{(-1)^k}{m^k k!} \)

For n/2 < m <= n, this number becomes n!*(1 - 1/m).

Thus, the number of permutations with one cycle with that length is n!/m

In this problem, the number is 100!/57.

 

[Swammerdami]

(6) How many permutations of a 100-sized set have a cycle of length 57 exactly?

This can be handled with the generator function. The alternative to that cycle's presence is its absence, and we can count up how many permutations lack it. That is straightforward with the generator function. With no length-m cycles and with all the others optionally present, I find

\( \frac{\exp\left(-t^m/m\right)}{1 - t} \)

This gives a number

\( N(\text{no m}) = n! \sum_{k=0}^{\text{floor}(n/m)} \frac{(-1)^k}{m^k k!} \)

For n/2 < m <= n, this number becomes n!*(1 - 1/m).

Thus, the number of permutations with one cycle with that length is n!/m

In this problem, the number is 100!/57.

Another way to see this: Since 57 is more than half of 100 we can have at most one 57-cycle. The probability of such is

C(100,57) * 56! * 43! / 100!​

where Choose(100, 57) is the number of ways to pick 57 elements for the 57-cycle; 56! is the number of distinct cycles once the 57 are chosen; 43! is the number of ways to permute the leftovers; and 100! is the total number of permutations of 100 elements. Recall C(100,57) = 100! / (57! 43!); make this substitution and simplify to find that the probability of a 57-cycle is 56!/57! = 1/57.

Therefore, with 100 elements the probability of any cycle of size 51 or greater is
1/51 + 1/52 + 1/53 + 1/54 + ... + 1/99 + 1/100 = .68817

We can estimate that number without adding up the terms. It is the sum of the first 100 reciprocals minus the sum of the first 50 reciprocals. Recall this formula

1 + 1/2 + 1/3 + 1/4 + 1/5 + ... + 1/k ~= ln(k) + 0.577216​

This formula is also due to Leonhard Euler, with 0.577216... Euler's Constant (not to be confused with Euler's Number 2.71828...)
So in the limit, the chance that a permutation of 2k elements has a cycle greater than size k is about ln(2k) + 0.577216 - ln(k) - 0.577216, which is simply ln(2). Ln(2) is .69314, which differs from .68817 because 2k=100 is small enough to see deviation from the asymptote. But using either number tells us there is about a 31% chance (1 - .68817) that a 100-permutation will contain no cycle greater than 50.

Now go back to the puzzle at the bottom of #5, and look again.