# The Distribution of the Size of the Union of Cycles for Two Types of  Random Permutations

Authors: Tamás Lengyel
Journal: International Journal of Combinatorics
 (2010)

---

## Abstract

We discuss some problems and permutation statistics involving two different types of random permutations. Under the usual model of random permutations, we prove that the shifted coverage of the elements of{1, 2, …, k} of a random permutation over {1, 2, …, n}; that is, the size of the union of the cycles containing these elements, excluding these elements themselves, follows a negative hypergeometric distribution. This fact gives a probabilistic model for the coverage via the canonical cycle representation. For a different random model, we determine some random permutation statistics regarding the problem of the
lost boarding pass and its variations.


---

## Body

## 1. Introduction

Permutation statistics play an important role in exploring structural properties of random phenomena from a statistical point of view and often do in the context of the analysis of algorithmic applications. We select a permutationπ=(π(1),π(2)…,π(n)) of {1,2…,n} at random with π(i) denoting the element to which i gets mapped in the permutation. Sometimes, the mapping is also denoted by i→π(i). Each permutation can be uniquely expressed as the product of disjoint cycles. A cycle is an ordered subset of the permutation whose elements cyclically trade places with one another; for example, the permutation 3241 is the product of the (134) 3-cycle and the (2) 1-cycle. Here, the notation (134) means that starting from the original ordering 1234, the first element is mapped into the third, the third into the fourth, and the fourth into the first, while the second stays unchanged.Letπi denote the set of elements in the cycle that contains element i of a random permutation π of {1,2,…,n}; that is, πi={i,π(i),π(π(i)),…}. We also use the notation πS for the (set) union of cycles containing all of the elements in S⊆{1,2,…,n} (thus, in fact, πi is a shortcut for π{i}). Sometimes, we write πi in its cycle form (i,π(i),π(π(i)),…) when we want to emphasize the actual cyclical order in the cycle and not only its membership.In the standard model, all permutations are assumed to be equally likely among the permitted permutations. If all then! permutations are permitted, then one of the most useful tools in analyzing these permutations is a correspondence known as the canonical cycle representation (although often an alternative version is referred to as canonical cycle form): in the cycle product form of the permutation, write each cycle such that it ends with its least element and order these cycles so that these last elements of the cycles are in increasing order. This correspondence does not seem to match any real life situation. (Had we ordered the cycles in decreasing order or in increasing order but according to their largest elements, then this process models how new records are achieved.) Note that one might benefit from the canonical cycle representation even if the permutations are not equally likely (cf. proof of Theorem 3.9).Except for Corollary2.7, membership problems are well known for the standard model (cf. [1], Section 3). We prove that the size of the union of the cycles containing any k prescribed elements excluding these elements themselves follows a negative hypergeometric distribution. For completeness, we also included the well-known results and their short standard proofs in Section 2.Note that in the second random permutation model, the cycle structure is simple with one nontrivial cycle. The distribution of its size is determined in Remark3.4 and Theorem 3.6. The number of valid permutations for a generalized version is given in Theorem 3.9.Theorems2.3, 2.4, 3.5, 3.6, 3.9, and Corollary 2.7, as well as the distributional observation given in identity (3.5) and its consequences in the second solution of the lost boarding pass problem seem to be new. We also provide a straightforward proof of Theorem 3.2. Identity (3.3) also appeared in [2].We note that [3] contains a great selection of results regarding random permutation statistics by using tools of analytic combinatorics mainly applied to bivariate generating functions.Apparently, the second model has the flavor of a statistical resampling method whose purpose is to exchange labels on data points when performing significance tests.


## 2. The Union of Cycles with Given Membership and Its Cardinality

Now, we discuss membership issues by using the canonical cycle form.Theorem 2.1.
We have thatP(k∈π1)=P(2∈π1)=1/2 with 2≤k≤n.Proof.
Without loss of generality, we answer the question for2∈π1. We use the canonical cycle form defined in Section 1: P(2∈π1) is related to the position of 2 relative to that of 1. In fact, 2 belongs to the cycle π1 of element 1 exactly if 2 comes before 1 whose probability is 1/2.The previous question onP(2∈π1) has an equivalent form P(π1=π2). We can generalize this to k cycles about shared membership.Theorem 2.2.
Fork≥2, we have that
(2.1)mk=P(π1=π2=⋯=πk)=1k,
and the probability remains the same for any k distinct indices.Proof.
Similarly to the proof of Theorem2.1, the elements 2,3,…, and k belong to the cycle of element 1 exactly if 2,3,…, and k each comes before 1; that is, mk is the probability that in a random permutation 1 is the last of these numbers which is 1/k. The probability is not affected by the choice of the indices by symmetry.Now we find, in probabilistic terms, how much of{1,2,…,n} is covered by taking the union of the cycles that include any given k elements, for example, 1,2…,k.Theorem 2.3.
For allm,1≤k≤m≤n, we get that
(2.2)Pk(m,n)=P(|π{1,2,…,k}(n)|=m)=km(n-kn-m)(nn-m)=(m-1k-1)(nk).With some calculations, we get the expected size and the variance of the size of the coverage inTheorem 2.4.
We have that(2.3)E|π{1,2,…,k}(n)|=kk+1(n+1),var(|π{1,2,…,k}(n)|)=k(n-k)(n+1)(k+1)2(k+2).
For any fixed k,1≤k≤n, as n→∞, we get that
(2.4)var(|π{1,2,…,k}(n)|)~k(k+1)2(k+2)n2.Remark 2.5.
The casek=1 with P1(m,n)=1/n,1≤m≤n is trivial since 1 can go to n equally likely positions in the canonical representation. With the indicator variables Xi=1,i=1,2,…,n, exactly if i is in the cycle π1, we have X1=1, since 1∈π1 and P(i∈π1)=1/2 if 2≤i≤n by Theorem 2.1, and hence E|π1|=(n+1)/2. Note that the Xis are not independent since mj≠m2j-1, for j≥3, by Theorem 2.2. Indeed, as we have just mentioned |π1|=1+∑i=2nXi has uniform distribution rather than binomial.Remark 2.6.
Another interesting special case deals withm=n, that is, determining the probability Pk(n,n)=k/n,1≤k≤n that the combined cycles covering k preselected elements cover the whole set {1,2,…,n}. Surprisingly, the most likely number N of elements covered is n for k≥2 as we will see it in (2.5) of the proof below.Proof of Theorem2.3.
We use the canonical cycle form again: we can characterize all permutations with the required property. We start with the case in whichm=n (cf. Remark 2.6). The k elements cover the whole set {1,2,…,n} exactly if the last element of the permutation in the correspondence is not greater than k which has a chance of k/n.
In the general case, if the union consists ofm elements, then the probability of this happening is k/m by the previous case, and the remaining n-m positions can be filled (nn-m)(n-m)! ways, out of which (n-kn-m)(n-m)! will have the smallest k elements in the union, and this completes the proof of the first part of the identity (2.2).
In order to prove the second part of the theorem, we note that, fork≥2, the distribution of the random variable |π{1,2,…,k}(n)| is, perhaps somewhat surprisingly, tail heavy on the right; that is, Pk(m,n)=P(|π{1,2,…,k}(n)|=m) is getting larger as m is getting closer to n. We observe that
(2.5)Pk(m+1,n)Pk(m,n)=mm+1-k,k≤m≤n-1.
For k=1, we get that the ratio is 1, and the coverage follows the uniform distribution over {1,2,…,n}. For k≥2, the ratio exceeds 1. It is easy to see that
(2.6)P2(m,n)=2(m-1)n(n-1),k≤m≤n
is a linear function in m, and in general, Pk(m,n) as a function of m over the integers {k,k+1,…,n} is a polynomial of degree k-1 by (2.5). More precisely, it follows by (2.5) and Pk(k,n)=k!(n-k)!/n!=1/(nk) that
(2.7)Pk(m,n)=(m-1k-1)(nk),k≤m≤n.
(This fact also guarantees that the sequence Pk(m,n),m=k,k+1,…,n, is strictly concave up for k≥3.)It follows that the distribution of the shifted coverage|π{1,2,…,k}(n)|-k belongs to the family of negative hypergeometric distributions. This observation gives a probabilistic model for the coverage via the canonical cycle representation of permutations.Corollary 2.7.
For the shifted coverage, one has that|π{1,2,…,k}(n)|-k~ NegativeHypergeometric[k,n-k;k].Now, we present an alternative direct proof of the corollary without using (2.7).Proof of Corollary2.7.
We havek black and n-k white balls. We select balls without replacement until all black balls have been selected, and, at this point, let Yk denote the number of white balls selected. Clearly, Yk~ NegativeHypergeometric[k,n-k;k]; that is, P(Yk=x)=(x+k-1k-1)/(nk),0≤x≤n-k. With m=x+k, we get that P(Yk=m-k)=P(Yk+k=m)=(m-1k-1)/(nk),k≤m≤n, for the distribution of the total number of selected balls (including the k black ones). Note that this probability remains the same if we distinguish the balls of the same color; for example, individually label the black and white balls in two separate groups, since it introduces an extra factor k!(n-k)! in both the numerator and denominator. We can find a correspondence between the k black and n-k white balls, and the sets Sk={1,2,…,k} and {1,2,…,n}∖Sk, respectively. First, we index the black balls from 1 to k and the white balls from k+1 to n. We set π(1) to be the index of the first ball. We also record the color of the ball in every step. If the index is different from 1, then we go on and pick the next ball whose index is to be assigned to π(2)(1)=π(π(1)). We keep picking elements until π(j)(1)=1 for some j. Let s=s1 be the smallest index in Sk not in π1=(π(1),π(2)(1),…,π(j)(1)=1). If such an s exists, then we set π(s) to be the index of the next ball and keep continuing until the cycle πs is completed. We set s=s2 to be the smallest index in Sk not in π1∪πs1. If such an s exists, then we set π(s) to be the index of the next ball and keep continuing until πs is completed, and so forth. The process goes on until no such s exists. Note that the coverage of π{1,2,…,k}(n) consists of k black balls and |π{1,2,…,k}(n)|-k white balls.
Fork=1, |π1(n)|-1 is the number of elements of the first cycle π1 in the canonical cycle representation before 1 is included; that is, it is the number of white balls before the only black ball is selected. For a general k, |π{1,2,…,k}(n)|-k counts the white balls before the set {1,2,…,k} is completely included.


## 3. Some New Results Regarding the Lost Boarding Pass

Now, we discuss a popular problem and some of its variations involving random permutations of a different type. We answer questions similar to those addressed in Section2 and derive some other properties regarding certain generalizations.The problem of the lost boarding pass (see [4, page 35]). One hundred people line up to board an airplane, but the first has lost their boarding pass and takes a random seat instead. Each subsequent passenger takes their assigned seat if available, otherwise a random unoccupied seat. What is the probability that the last passenger to board finds their seat occupied?We assume that the passengers and the seats are ordered and theith passenger takes the seat π(i),1≤i≤n. In our original standard model of random permutations, each passenger would randomly pick their seat while here the ith passenger's assigned seat is i but then the first one picks their seat at random, out of necessity. The other passengers make random choices only if their seats are occupied. In a more general context, if r stands for the number of passengers who have lost their boarding passes, then the original model corresponds to r=n, while here r=1 with the understanding that the first passenger lost their pass. Remarks 3.3 and 3.7 below make it clear that it is irrelevant which of the first n-1 passengers lost their pass. Of course, if only the last passenger lost their boarding pass, then even they will be properly seated. On the other hand, for larger r, the actual r-element set L of passengers without boarding passes does matter. Note that if the last passenger finds their seat occupied, then they end up at a seat assigned to one of the passengers in L. In summary, this model can be viewed as a generalization of the original one with r<n. We focus on the case with L={1}, and thus r=1.Remark 3.1.
By (2.1), we would get that P(π1=πn)=P(π1=π2)=m2=1/2. However, it turns out that the random permutation model used for establishing (2.1) does not work here. In fact, P(i∈π1) changes with i, for example, P(2∈π1)=1/n and P(3∈π1)=1/(n-1)as we will see below in the solution (when we calculate qk). The structure of the cycles is also different from the above random model, and the resulting permutation is far from being typical: it has a long cycle π1 (of asymptotic average length logn, cf. Remark 3.4), and otherwise, only one-element cycles (fixed points). It is easy to see that there are 2n-1 such permutations for n≥1, since we have (n-1|π1|-1) ways to construct the nontrivial cycle with size |π1|=1,2,…,n. In a similar fashion, half of these permutations have the last passenger finding their seat occupied. Note, however, that the permutations occur with very different probabilities depending on not only the size of π1 but its membership according to Theorem 3.5 (notwithstanding, it also gives the answer 0.50 to the problem of the lost boarding pass by the fact that (3.3) has a last factor of one exactly if the last passenger finds their seat already occupied, and thus, making P(n∈π1)=P(n∉π1)=1/2).We find the answer by presenting two approaches. There are other solutions using recurrence relations or other techniques. The “definitive" solution is given in [4, pages 36-37] although it is of no help with respect to distributional concerns. (Winkler's solution requires no calculations and is based on conditionalizing with two competing targets. It also shows that references to the actual permutation can be completely dropped.) Regarding the case L={1,2,…,r}, we also mention an interesting result by Misra [2] and determine the number of valid permutations.The first approach is based on finding the probabilityqk that passenger k finds their seat occupied. We note that the cycle of 1 is quite special: it looks like π1=(a1=1,a2,…,al) with l=|π1|, a1=1<a2<a3<⋯<al, ai+1=π(ai),i=1,2,…,l-1, and π(al)=1; thus, the elements of the only nontrivial cycle are in a monotone increasing order. (We note that by assuming that a little argument erupts whenever a passenger with a boarding pass finds their seat occupied, then the first passenger can figure out their original seat assignment since their seat is taken by the last upset person. The distribution of the waiting time T for obtaining this information is implicitly discussed in the second solution since P(T=l)=on-l,2≤l≤n, and the probability that none of the n passengers get upset is on.) One might ask about the chances that the second, the third, and so forth, passengers will find their own seats occupied rather than simply the last one. With qk=P(passengerkfindstheirownseatoccupied)=P(k∈π1), we get that q1=0, q2=P(passenger1takestheseatofpassenger2)=1/n, and qn=P(a|π1|=n). With the notation i→j meaning that passenger i takes the seat of passenger j: q3=P((1→3)∪(1→2→3))=(1/n)+1/n(1/n-1)=1/n-1 and (3.1)q4=P((1→4)∪(1→2→4)∪(1→2→3→4)∪((1→3→4)∩(2→2)))=1n+1n1n-1+1n1n-11n-2+1n11n-2=1n-2.
In a similar way, q5=1/(n-3). More complicated calculations lead to qk=1/(n-k+2). Indeed, in general, we encounter exactly the various terms in the expansion of qk=(1/n)∏i=1k-2(1+(1/n-i))=1/(n-k+2) by properly conditionalizing with respect to all seat selections leading to k∈π1. We have just provedTheorem 3.2.
(3.2)qk=P(passengerkfindstheirownseatoccupied)=1n-k+2,2≤k≤n.In particular, we getqn=1/2, which provides the solution to the problem.Remark 3.3.
We note thatqk depends on the actual set L of passengers who lost their boarding passes if r=|L|>1. The above derivation assumes that r=1 and the first passenger lost their pass. However, it is easy to see that if it is the jth rather than the first passenger who is without a boarding pass, then we can simply ignore the first j-1 passengers since they are properly seated. With this reduction in the size of the actual problem, the original answer qk=1/(n-k+2) is preserved in Theorem 3.2 for every j+1≤k≤n, since we simply shift both n and k by j-1 to the left. Clearly, q1=q2=⋯=qj-1=qj=0. In contrast, if r>1, then things get more complicated. In general, we consider the condition CL which represents the event that exactly the passengers in L lost their boarding passes. In this case, the calculation of the conditional probability that the kth passenger finds their seat occupied may depend on the choice of L. For example, if r=n-1≥1, then the corresponding conditional probability qk(L)=P(passengerkfindstheirownseatoccupied∣CL) for the last passenger with k=n is 1-1/n or 1-1/(n-1)depending on whether L={1,2,…,n-1}, that is, the first n-1, or L={2,3,…,n}, that is, the last n-1 passengers lost their boarding passes. Of course, n∈L makes no sense since the last passenger has no choice and takes the only empty seat left; therefore, we assume that n∉L. Another example with a small r: if r=|L|=2, then q3({1,a})=2/n,q3({2,b})=1/(n-1),q3({c,d})=0 with a>1,b>2,c≥3,d>c, and n≥3. On might speculate that qk(L) depends only on an ordered subset of L.Remark 3.4.
Now, we can find the average number of people who pick their seats at random. The average is the harmonic numberHn. In fact, we set the indicator variables Xk=1,k=1,2,…,n exactly if k is in the cycle π1. We get that |π1|=1+∑k=2nXk since X1=1, and thus, E|π1|=1+E(∑k=2nXk)=1+∑k=2nqk=Hn~logn.We can also derive the following theorem on the probability of membership and shared membership, similar to Theorems2.1 and 2.2 of the original standard random permutation model.Theorem 3.5.
We have thatP(π1=πk)=P(k∈π1)=1/(n-k+2) with 2≤k≤n. Also, for the full nontrivial cycle, with arbitrary 1<a2<a3<⋯<al≤n, we get that
(3.3)P(π1=(a1=1,a2,…,al))=1∏i=1l(n-ai+1).
It is a trivial lower bound on P(π1=πa2=⋯=πal), as we might skip some indices of the cycle and l can be less than |π1|, and an equality if ai=i,2≤i≤l=|π1|, that is, P(π1=π2=⋯=π|π1|)=1/n(n-1)⋯(n-|π1|+1).
In general, for1<i1<i2<⋯<ij≤n with j≥2, we have
(3.4)P(π1=π2=⋯=πij)=P(π1=πi1=πi2=⋯=πij)=1∏t=1j(n-ii+2),
and thus, the probability depends on the choice of indices.Proof.
The proof is based on the way random selections are made. Identity (3.4) follows by the repeated applications of Theorem 3.2. Indeed, P(π1=πi1=πi2=⋯=πij)=P(π1=πi1)P(π1=πi2-i1+1=πi3-i1+1=⋯=πij-i1+1),ij-i1+1≤n-i1+1, since we can recast the problem as if the nontrivial cycle started with the i1th passenger rather than the first one.As a consequence of Remark3.4 and Theorem 3.5, now we can determine the exact distribution of |π1| since the construction of π1 corresponds to that of consecutive records (cf. [5]).Theorem 3.6.
For the distribution of the size of the nontrivial cycle, one gets thatP(|π1|=j)=s(n,j)/n!,1≤j≤n, with s(n,j) being the unsigned Stirling number of the first kind indicating the number of permutations over an n-element set with exactly j cycles.Proof.
We observe that the variablesXi introduced in Remark 3.4 are independent random variables according to (3.4). The proof can be finished by the usual argument used for proving that the positions of the records form an independent sequence of random variables (cf. [6]). Note that for the usual records, position j is that of a record with probability 1/j. But here, for the Xis, the order of the indices is reversed between 2 and n. We add that the standard proof that the distribution of the number of records and cycles is the same uses the alternative canonical cycle representation mentioned in the introduction.The second approach is based on calculating the probabilityok that exactly the last k passengers will get their own seats. We can rephrase Remark 3.4 by saying that the number of people getting their own seats is n-Hn on the average. A portion of this number is formed by people with consecutive indices immediately following the largest index m=a|π1| in π1. This is the point after which people take their own seats one-by-one and follow the proper seating from then on. In fact, if m=n-k, then exactly the last k passengers (without any gap) will get their own seats. Depending on k, we get that(3.5)ok=P(exactlythelastkpassengerswillgettheirownseats)=P(atleastthelastkpassengerswillgettheirownseats)-P(atleastthelastk+1passengerswillgettheirownseats)=1k+1-1k+2=1(k+1)(k+2),k=0,1,…,n-2.
The reason for P(atleastthelastkpassengerswillgettheirownseats)=1/(k+1) is that it suffices to focus on π1. As this cycle develops, at any stage of the selection, the current passenger faces two competing targets: the seat assigned to the first passenger and the set of seats assigned to the last k passengers. The cycle is either finished by the first choice with probability 1/(k+1) or it will move to a seat assigned to one of the last k passengers with probability k/(k+1). We note that a similar argument shows up in the proof in [4] with k=1; however, here, we are interested in the complete distribution ok,0≤k≤n.We have thato0=P(n∈π1)=1/2 by (3.5) which solves the problem, in agreement with the above result.We note that clearly,on=P(π1=(1))=1/n and o0≠(n-1)!/n!=1/n, for not just the permutation of the single cycle but all permutations which include 1 and n in the same cycle π1 should be accounted for. Of course, the case with k=n-1 is impossible; thus, on-1=0. It is worth mentioning that the question regarding another permutation statistic, the maximum element of a cycle is answered by ok: P(max{j∣j∈π1}=k)=P(a|π1|=k)=on-k for k=2,…n and P(max{j∣j∈π1}=1)=P(a|π1|=1)=on=1/n.The expected number of passengers properly seated beyond themth passenger defined above is Hn-1+1/n. In fact,(3.6)∑k=0nkok=n1n+∑k=1n-2k(k+1)(k+2)=1+∑k=1n-2(k+1(k+1)(k+2)-1(k+1)(k+2))=1+(Hn-1-12)-(12-1n)=Hn-1+1n.
Thus, on the average, there are Hn~logn passengers who are seated at random, and there are asymptotically n-2logn passengers who happened to take their seats before the procedure settles to proper seating with asymptotically logn people involved in it.Remark 3.7.
Note that the answer does not depend onn. Also, we can start anywhere: it is irrelevant which of the first n-1 passengers lost their boarding pass; the answer is simply P(n∈πi)=1/2,i<n, if the ith passenger lost their pass.With a proof based on equivalences due to exchanging pairs of seats and (3.3), Misra [2] obtained the following result.Theorem 3.8 (see [2, Theorem 4.1]).
The probability that the last passenger finds their seat when the firstr passengers seat themselves at random is 1/(r+1), that is,
(3.7)1-qn({1,2,…,r})=1r+1,0≤r≤n-1.In other words, we can create the ultimate chaos by letting ther passengers without their boarding passes enter the plane first; thus, L={1,2,…,r} and qn(L)=1-(1/(r+1)) which agrees with our answers based on Theorem 3.2 if r=1 and the ones in Remark 3.3.Of course, in real life, these passengers should enter last, since this way they will have a better chance to guess their seats correctly. In fact, this group of people will never know what was their original seat assignment. They might not even care about it and simply choose one of the remaining empty seats as it was theirs in the first place; thus, all of them are happily seated at the end. Not to mention that this way the passengers with boarding passes will not be aggravated by finding their seats occupied.We note that this kind of seating arrangement seem to be easier to analyze. For instance, an even better explanation comes for the permutation count2n-1, mentioned in Remark 3.1, from applying the canonical cycle representation: for i>1, there are two ways to put i, either before or after 1, corresponding to the options i∈π1 and i∉π1, respectively; otherwise, the orders are determined. In a similar fashion, relative to the position of 1 and 2, we find that there are 2·3n-2,n≥2, valid permutations if L={1,2}. In general, we getTheorem 3.9.
ForL={1,2,…,r}, the number of valid permutations is r!(r+1)n-r if n≥r.Proof.
The proof uses the canonical cycle representation. Any ordering of the elements ofL uniquely determines the ordering of the other n-r elements once their relative positions with respect to L are chosen. In fact, for each number i∉L,2≤i≤n, there are r+1 segments relative to the r elements of L to hold i. The segments ending with the elements of L correspond to the cycles, and thus, within the segments, the order of these numbers is set by the nature of the seat selections.Note that this argument does not directly apply to a setL with a gap. For example, if 2∉L, then the cycle (1x2…),x≥3; hence, the ordering x,2,…,1 in the first segment cannot occur.



---

*Source: 751861-2010-10-24.xml*