Knotting

By: Gijs Bellaard and Sander Spoelstra
Created: 9 September 2019
Last modified: 25 January 2022

During the introduction week people were playing the "knotting" game. It works as follows: a group of people stands in a circle with their hands out in front of them. Everyone closes their eyes and grabs two random hands. Once everyone has found two hands they all open their eyes and the game starts. The goal of the game is to unknot (by climbing over/under each other) the mess that has been created. It is paramount that linked hands do not let go of each other during the unknotting.

Two genius mathematicians happened to be spectators of such a game when, not unlike when the apple that fell upon Sir Isaac Newton's head, they were struck by a mathematical question: "what is the probability that a game of knotting consists of one big chain?". They were inspired to this question upon seeing that the people in a game of knotting ended up in a number of smaller chains. A large meal of brain juice, in the form of beer, guided them on the mathematical path to the solution of this question.

The game may be described in mathematical terms as follows: for a group of \(n\) people let every person choose one person that has not yet been chosen. This way everybody uses one hand to choose and the other hand to be chosen. This lets us represent every game by a permutation. For example, suppose we play the game with four people: Alice, Bob, Chloe and Dave. Chloe grabs Dave, Dave grabs Alice and Alice grabs Chloe. Bob grabs himself, because he likes that. This corresponds with the following permutation (in cycle notation): \[\textrm{(Chloe, Dave, Alice)(Bob)}\]

Using this model, our original question can be rephrased as: "what is the probability that a permutation of \(n\) people consists of exactly one cycle?". Basic, obvious and trivial probability theory that is left as an exercise to the reader, tells us that this probability \(p\) is equal to: \[ p=\frac{\#n\textrm{-permutations of exactly one cycle}}{\#n\textrm{-permutations}}. \]

We all know that the total number of \(n\)-permutations is equal to \(n!=n\cdot(n-1)\cdot(n-2)\cdots1\). This leaves us with the question of how many of these \(n\)-permutations consist of exactly one cycle. Take any random arrangement of \(n\) people in a circle. This circle can be cut up at any of the \(n\) links between people to acquire a row of \(n\) people. Therefore, there are \(n\) distinct rows that correspond with the same circle. Moreover, there are in total \(n!\) distinct rows. We can conclude that there are \(\frac{n!}{n}=(n-1)!\) ways to arrange \(n\) people in a circle. Substituting this in our formula for \(p\) yields: \[p=\frac{(n-1)!}{n!}=\frac{1}{n}.\] So, in game of knotting of \(n\) people there is a \(\frac{1}{n}\) probability that the game ends up as one big chain.

However, it occurred to the prodigies that it's really boring if somebody grabs their own hands (just like Bob did in the example), which is often resolved in real life examples. Therefore, they would like to find a new probability, which excludes the permutations were somebody grabs their own hands. Such permutations (with no fixed points) are known as derangements. The two top-tier intellects realized that this would change the probability significantly. After all, for all \(n\) elements in a permutation, there is a \(\frac{1}{n}\) probability that it maps to itself. As a result, every permutation is expected to have one fixed point. Therefore, a new formula for \(p\) arose: \[ p=\frac{\#n\textrm{-permutations of exactly one cycle}}{\#n\textrm{-derangements}}. \]

This yields the new question: "what is the number of \(n\)-derangements?". Let \(a_n\) denote the number of derangements of \(n\) people. Suppose that there are \(n\) people numbered \(1,2,\dots,n\). Let person 1 grab the hand of any person \(i\) other than himself. There are \(n-1\) possibilities for such a choice. Next, we let person \(i\) choose the next person. We distinguish two cases:

Person \(i\) grabs the hand of somebody other than person 1. Then \(i\) can choose between all remaining persons except for himself, so this reduces the problem to finding \(a_{n-1}\).
Person \(i\) does grab the hand of person 1. This takes both persons out of the pool of remaining players, so this reduces the problem to finding \(a_{n-2}\).

This yields the following recurrence relation: \[ a_n=(n-1)(a_{n-1}+a_{n-2}) \] which can be rewritten as \[ a_n-na_{n-1}=-(a_{n-1}-(n-1)a_{n-2}). \] Now define \(f_n=a_n-na_{n-1}\). Then we can rewrite the previous equation as: \[ f_n=-f_{n-1}. \] Using \(f_2=a_2-2a_1=1\), we find \(f_n=(-1)^n\). Plugging this back into the definition of \(f_n\) we get the recurrence relation: \[ a_n=na_{n-1}+(-1)^n. \] Straightforward recursive substitution (which may be proven by induction) yields the solution \[ a_n = n!\sum_{i=0}^{n}{\frac{(-1)^i}{i!}} \] Interestingly, we recognize this as \(n!\) times the partial sum of the power series of \(e^x\) at \(x=-1\). Due to this power series converging extremely fast we may write \(a_n\) as: \[a_n = \left[\frac{n!}{e}\right]\]

This concludes the intellectual odyssey of the two virtuosi with the answer that the probability that a game of knotting with \(n\) people is one big chain is equal to: \[p=\frac{(n-1)!}{\left[\frac{n!}{e}\right]} \approx \frac{e}{n}.\]