Average Number of Matches. Torsten Sillke, Frankfurt, 1996 -------------------------- last update: 2001-04-01 This note is a collection of references for the matching problem. I tried to classify the different approaches in finding the moments and/or distribution. Several variation of matching problems considered here are discussed in [Bar58], [DaB62]. A classical collection of probability problems which contain this question is [Mos65]. Historial references can be found in [Tak80]. Problem 1: The following are equivalent versions of the matching Problem: (a) From a shuffled deck, cards are laid out on the table one at a time, from left to right, and then another deck is laid out so that each of its cards is beneath a card of the first deck. What is the average number of matches of the card above the and the card below in repetitions if this experiment? (b) A typist types letters and envelopes to n persions. The letters are randomly put into the envelopes. On the average, how many letters are put into their own envelopes? (c) Select a permutation from 1..n equal distributed. What is the expected number of its fixpoints? Problem 2: group A finite Group G acts on a finite set X transitivly. (In other words, for any x, y in X, there is a g in G with g(x) = y.) The average number of fixed pointes (over all elements of the group) is 1. Solution 1: the moments The average number of matches is one (if n >= 1). More general we can calculate the higher moments. Let X be the random variable of the number of fixpoints. (1) E((X) ) = 1 for k<=n otherwise 0. k (2) E( X^k ) = Bell_numbers(k) for k<=n. (3) Cumulant (X) = 1 for k<=n, and Cumulant (X) = 0. k n+1 Proof of (1): ------------- 1. Distribution Method: [GKP89 Chap. 8.3], [Knu68 Chap. 1.3.3] Determine the probability generating function for the number of fixpoints F_n(z). Then show: F'_n(z) = F_{n-1}(z). (k) E((X) ) = F (1) = F (1) = 1 for k<=n otherwise 0. k n n-k 2. Generating function method: [Whi92] Let M(n,j) be the number of exactly j matches for n elements then M(n,j) = (j+1)/(n+1) * M(n+1,j+1) which is easily combinatorial interpreted. From M(n,j)/n! = (j+1)*M(n+1,j+1)/(n+1)! follows d/dz F_{n+1}(z) = F_{n}(z). 3. Expectation Method: [Torsten Sillke, 1990] Typically expectation and variance will be calculated by this method. See [GKP89] or [Wil85]. Now let us calculate the factorial moments or binomial moments direct. Let Xi be the random variable which is one, if 'i' is a fixpoint of the random permutation and otherwise zero. Then we have: X = X1 + X2 + X3 + ... + Xn. The Corallary (A) from the appendix gives. E((X) ) = E((X1 + X2 + ... + Xn) ) k k = k! * E(SymmetricFunction({X1,X2,...,Xn}, k)) = k! * Binomial(n,k) * E(X1*X2*X3*...*Xk) for k<=n otherwise 0. = 1 for k<=n otherwise 0. This follows from E(X1*X2*X3*...*Xk) = Prob(X1=X2=X3=...=Xk=1) = (n-k)! / n! (combinatorial reasoning) = 1 / (n) (probability reasoning) k Proof (1) --> (2) and (3) ------------------------- Generating Functions: [GKP89] PF(z) : the probability generating function. FM(z) : exponential factorial-moment generating function. M (z) : exponential moment generating function. C (z) : exponential cumulant generating function. Relations between PF, FM, M, C: FM(z) = PF(z+1), M(z) = PF(exp z), C(z) = ln(M(z)) The exponential factorial-moment generation funktion FM_n of permutations of n elements is: FM_n(z) = exp_n(z) with exp_n(z) = SUM_{0<=k<=n} z^k / k! the truncated exponential function. FM_oo(z) = exp(z) as FM(z) = PF(z+1) we have PF_n(z) = FM_n(z-1) = exp_n(z-1) PF_oo(z) = FM_oo(z-1) = exp(z-1) M_n(z) = FM_n(exp(z)-1) = exp_n(exp(z)-1) M_oo(z) = FM_oo(exp(z)-1) = exp(exp(z)-1) C_n(z) = ln(FM_n(exp(z)-1)) = ln(exp_n(exp(z)-1)) C_oo(z) = ln(FM_oo(exp(z)-1)) = exp(z) - 1 If the Bell and Stirling2nd numbers are known (and their generating functions) we can give the k-th moments. E( X^k ) = #{ set partitions of {1..k} in upto n parts } = Stirling2nd(k,0) + Stirling2nd(k,1) + ... + Stirling2nd(k,n). special values are E( X^k ) = Bell_number(k) for k <= n E( X^k ) = Bell_number(k) - 1 for k = n+1 E( X^k ) = Bell_number(k) - 1 - Binomial(k,2) for k = n+2 The first n cumulants (semi-invariants) can be computed by a trick given in [GKP89, Chap 8.3]. For the kth cumulant depends only on the first k factorial moments, we can use the limit distribution has the same cumulants for k<=n. If we know that Cumulant_k = FactorialMoment_k + polynom(FactorialMoment_1, ..., FactorialMoment_k-1) we can calculate one term further. As FactorialMoment_n+1 is one too large in the limit distribution Cumulant_n+1 is one too large. Cumulant (X) = 1 for k<=n k Cumulant (X) = 0 for k=n+1 k References: (annotated) ----------- Bar58: David E. Barton; The Matching Distributions: Poisson Limiting Forms and Derived Methods of Approximation, J. Royal Statist. Soc., (B) 20:1 (1958) 73-92 MR 20 # 7327 (variations and extensions of the matching problem) BeW91: E. A. Bender, S. G. Williamson; Foundations of Applied Combinatorics, Addison Wessley, Reading (1991) Exc. 2.2.4: Derangement Approximation (Independence Heuristic) Exp. 4.11: Derangements (Sieving Method, semifactorial notation) Exp. 8.1: The Number of Derangements (Recursions, Distribution-Free) Exp. 11.8: Derangements (Generating Function -> Recursion) Exp. 12.4: Counting Derangements (Determine the Generating Function) ClS93: R. J. Clarke, M. Sved; Derangements and Bell numbers, Mathematics Magazine 66:5 (1993) 299-303, MR 94k:05016 (Moments of the number of non-fixpoints for random matchings) Com74: Louis Comtet; Advanced Combinatorics, Reidel Publishing Company, Dordrecht (1974) Chap. 4.2: The 'Probleme des Rencontres'. (Sieving Method, Inversion Method, antifactorial notation, Generating Function -> 2 Recursions) Exc. 4.4: Other properties of the number d(n) of derangements. (Difference-Representation, differential equation of the GF, exp(-t(1-u))/(1-t) is GF of permutaions with k-fixpoints) Exc. 3.11: Characteristic numbers for a random variable. (Let X be a Poisson RV with parameter l, then E(X^n) = Sum_k S(n,k) l^k) DaB62: Florence N. David, David E. Barton; Combinatorial Chance, Griffin, London (1962) (contains two chapters on derangement and matching problems. Gives several relations for these models.) Eng73: Arthur Engel; Wahrscheinlichkeitsrechnung und Statistik, Band 1 Klett Studienb\"ucher, Stuttgart, 1973 Chap 3: Kombinatorik; 3.2.2 Beispiel 5: Fixpunkfreie Permutationen (derangments: D(n) = (n-1)*(D(n-1) + D(n-2)) with interpretaion) Chap 14: Anzahl der Fixpunkte einer Permutation (Mean and Variance (Expectation Method) Limit distribution Poison(1)) Fel50: William Feller; An Introduction to Probability Theory and Its Applications, Volume I, Wiley International Edition, New York (1968), 3rd Ed. Chap. IV: Combinations of Events (The Inclusion-Exclusion-Principle is attributed to Frechet (Fre40)) Chap. IV.1 Example b: Matches (coincidences or rencontre) (Probability of at least one match (Inclusion-Exclusion) (Orig: Montmort 1708)) Chap. IV.4: Application to Matching and Guessing (Distribution by Inclusion-Exclusion-Principle) Fre40: M. Frechet; Les probabilites associees a un systeme d'evenements compatibles et dependants, Actualites scientifiques et industrielles, nos. 859 and 942, Paris (1940 and 1943) (The general Inclusion-Exclusion-Principle) Fry28: T. C. Frey; Probability and Its Engeneering Uses, Van Nostrand, New York, 1928, (41-77, Matching Problems) GKP89: Ronald L. Graham, Donald E. Knuth, Oren Pataschnik; Concrete Mathematics, Addison Wessley, Reading (1994) 2nd Ed. Chap. 5.3.3: Inversion (Determines the distribution from a linear system of equations, and solves it by an inversion formular.) Chap. 8.2: Mean and Variance (Expectation Method) Chap. 8.3: Probability Generating Functions (Distribution Method) GrS92: G. R. Grimmett, D. R. Stirzaker; Probalility and Random Processes, Oxford Univ. Press, New York (1992), 2nd. Edition Chap. 3.4: Indicators and matching (3. Matching problem) Chap. 5.2: Some applications, Matching revisited & Matching and occupation (Expand Binomial-Moments of a sum of indicator variables, but don't apply it to the matching problem.) Knu68: Donald E. Knuth; The Art of Computer Programming Vol. 1, Fundamental Algorithms, Addison Wessley, Reading (1973) 2nd Ed. Chap. 1.2.10: Analysis of an Algorithm Chap. 1.3.3: Applications to Permutations (- An unusal correspondence. - expected number of k-cycles by direct counting. - distribution of the number of fixpoints of a random permutation. Determines the distribution from a linear system of equations. - distribution -> GF and F'_{n+1}(z) = F_{n}(z). - counting derangments by the principle of inclusion and exclusion. - history: inclusion and exclusion -> Moivre 'Doctrine of Chance' 1718.) Kre88: Ulrich Krengel; Einf"uhrung in die Wahrscheinlichkeitstheorie und Statistik, Vieweg Verlag, Braunschweig (1990), 2te Auflage, Chap. 3.4 Das Rechnen mit Indikatorfunktionen (Proofs the general inclusion-exclusion formula with indicator function. Then determines the match-distribution (Koinzidenz-Verteilung).) Lin97: John Linnell; A Pattern in Permutation, Crux Mathematicorum 23:3 (1997) 158-160 (the moments of the number of fixpoints are the Bell numbers.) MM95.1454: Names drawn from a hat, Mathematics Magazine 68:4 (Oct. 1995) 308-309 Solution to Excercise 1454 (solution to Exc. 75 of Silverman (Sil71).) Mos65: Frederick Mosteller; Fifty Challenging Problems in Probability with Solutions, Addison Wessley, Reading (1965) (reprint: Dover Publ.) Exc. 45: Average Number of Matches (Expectation Method) Exc. 46: Probabilities of Matches (Determines the distribution from a linear system of equations) Net01: E. Netto; Lehrbuch der Combinatorik, 1901. Chap 40: Absolute (relative) Euler'sche Permutationen (D(n) = (n-1)*(D(n-1) + D(n-2)) by combinatorial reasoning (Euler's method). derives for this the recursion: D(n) = n*D(n-1) + (-1)^n.) Old38: E. G. Olds; A moment generating function which is useful in solving certain matching problems, Bull. American Math. Soc. 44 (1938) 407-413 (tea testing problem, permanent, problem of (Fry28)) Sil71: David L. Silverman; Your Move, Mc Graw-Hill, New York (1971) (german: 100 unterhaltsame Denkspiele : Spielend denken lernen, Moderne Verlagsgesellschaft, 1984) Exc. 75: Renkontre (Expected number of rounds (see MM95.1454)) Ste64: Hugo Steinhaus; One Hundred Problems in Elementary Mathematics, Pergamon, Oxford, 1964, MR 28 # 1110 Two Hundred Problems in Elementary Mathematics (german: 100 Aufgaben, 1968) (german: 100 neue Aufgaben, 1973) Problem 90 (2nd Vol): Recontre (the expected number of matches is 1, expectation method) Wei88: P. Weisenhorn; Von den Rencontre-Zahlen zu den Bell-Zahlen, MNU 1988 Nr 6, 363-365 Whi92: P. Whittle; Probability via Expectation, Springer Verlag, Berlin (1992), 3rd Edition Sect 4.6: Matching and other Combinatorial Problems (generating function method: let M(n,j) be the number of exactly j matches for n elements then M(n,j) = (j+1)/(n+1) * M(n+1,j+1) which is easy combinatorial interpreted. From M(n,j)/n! = (j+1)*M(n+1,j+1)/(n+1)! follows d/dz F_{n+1}(z) = F_{n}(z).) Wil85: Herbert S. Wilf; Some examples of combinatorial averaging, American Math. Monthly 92:4 (1985) 250-261 MR 87b:05014 Sect 2: The fixed points of permutations (Mean and Variance, Expectation Method) (MR: This paper was the text of an invited presentation to the annual meeting of the MAA held in Louisville, Ky., 1984. It includes a wide variety of problems whose solution is accomplished with the methods of combinatorial averaging. [..]) Wil90: Herbert S. Wilf; generatingfunctionology, Academic Press, 1994, 2nd Edition downloadable at http://www.cis.upenn.edu/~wilf/ Chap: 2 Exerciese 27 Chap: 4.2 A generatingfunctionological view of the sieve method Example 1. The fixed points of permutations - - - - - - - - - - - - - - - - - - - - - - - - BHJ92: A. D. Barbour, L. Holst, S. Janson; Poisson Approximations, Clarendon Press, Oxford 1992 (pp 77-80, matching problems) BeS95: M. Bernstein, N. J. A. Sloane; Some Canonical Sequences of Integers, Linear Algebra and its Applications, 226-228 (1995) 57-72 URL: www.research.att.com/~njas/doc/eigen.ps MR 96i:05004 (MR: If you take an infinite sequence, consider it as a column vector and multiply it on the left by an infinite lower triangular matrix you get another column vector which represents the transformed sequence. This ubiquitous technique has been used to do everything from acceleration of convergence to proving combinatorial identities. In this offbeat, entertaining paper the authors define an eigensequence as one that transforms into something similar to itself, say shifted one place or with every other term deleted. One can start with a known matrix such as Pascal's triangle or the Stirling number triangles and find the various eigensequences. Conversely, one can define a new type of eigensequence and then try to find the transforming matrix. Many of the examples included in this paper come from combinatorial enumeration problems or are new.) Bot79: Otto Botsch; In der Werkstatt der Hirnverzwirner, Aulis Verlag Deubner & Co KG, K"oln, 1979 (problem 33: grosses Missgeschick mit Briefen. Combinatorial interpretation of the recurences) BBS90: A. Brandt, M. Brandt, H. Sulanke; A Representation of a Discrete Distribution by its Binomial Moments, J. Appl. Prob. 27 (1990) 208-214 (Let alpha be the radius of convergence of the Probability-GF. Ch. Jordan's inversion formular is valid for alpha > 2. A general formular is derived for alpha > 1.) Eul51: L. Euler; Calcul de la probabilite dans le jeu de rencontre. Euler Project: www.wcsu.ctstateu.edu/~sandifer/rencontre.htm Eul79: L. Euler; Solutio quaestionis curiosae ex doctrina combinationum. (Mem. Acad. Sci. St. Petersbourg 3 (1809/10(1811)) 57-64.) = Opera Omnia (1) 7 (1923) 435-440. (This was presented to the Acad. on 18 Oct 1779.) - Shows D(n) = (n-1) [D(n-1) + D(n-2)] and D(n) = nD(n-1) + (-1)^n. FlO90: P. Flajolet, A. O. Odlyzko; Random mapping statistics, Advances in Cryptology, EUROCRYPT 89, Lecture Notes in Comput. Sci. 434 (1990) 329-354 Zbl 747.05006 http://www.research.att.com/~amo/doc/crypto.html KnS96: F. F. Knudsen, I. Skau; On the asymptotic solution of the card-matching problem, Mathematics Magazine 69:3 (1996) 190-197 MR 97f:15013 (given two packs of cards. One with n*k cards, k of each kind and the other with n*l cards, l of each kind. Thm: The limit (n->oo) distribution of the number of matches is Poisson with parameter lambda = min(k,l).) The current proof follows from some easy inequalities and the principle of inclusion-exclusion. ) Kol86: V. F. Kolchin; Random Mappings, Optimization Software Inc. New York, 1986 (See (San98) but proof by complex analysis) Lea85: S. Leader; The Inclusion-Exclusion Probability Formulas by Taylor's Theorem, American Math. Monthly 92 (1985) 343-345 Mic96: R. Michel; Aspekte der Stirlingschen Zahlen zweiter Art, Math. Semesterberichte 43 (1996) 81-92 (The Poisson-approximation of the matching problem, n/(n+2)*2^n/(n+1)! <= sup_{k in N_0} | P_n(k)-Poisson_1(X=k) | <= 2^n/(n+1)! ) Pen91: S. O. Penrice; Derangements, permanents and Chrismas presents, American Math. Monthly 98 (1991) 617-620 MR 92g:05014 (given n*k objects, k of each kind, asymthotic probability for no match is exp(-k) using some "hard" inequalities for the permanent of a doubly stochastic matrix. (but see (KnS96))) Pit97: J. Pitman; Some Probabilistic Aspects of Set Partitions, American Math. Monthly 104:3 (Mar. 1997) 201-209 MR 97j:05009 (Bell and Stirling numbers, Moments of the Poisson Distribution (factorial and others), the matching problem, 58 references. MR: This review paper examines some properties of set partitions with emphasis on a statistical viewpoint. The 58-item bibliography will be of interest to researchers. A sample of topics: proofs of Dobinski's formula and some variants, equality of Bell numbers with moments of the Poisson distribution, derivation of the 2-variable generating function for Stirling numbers $S(n,k)$, and how to generate a set partition at random.) mailto:pitman@stat.berkeley.edu Rem83: J. B. Remmel; A note on a recursion for the number of derangements, European Journal of Combinatorics 4:4 (1983) 371-374, MR 85i:05024 (Derangements, combinatorial interpretation of D(n) = n*D(n-1) + (-1)^n using a q-analog formular. MR: The author gives a combinatorial proof of the recursion $D\sb {n+1} =(n+1)D\sb n+(-1)\sp {n+1}$ for derangement numbers, and for its $q$-analogue. The proof uses a representation of derangement cycle structures due to A. M. Garsia and the author [same journal 1 (1980), no. 1, 47--59; MR 81g:05011].) RBC74: W. W. Rouse Ball, H. S. M. Coxeter; Mathematical Recreations and Essays; Univ. of Toronto Press, (1974) Section: Derangements, p46-47 (combinatorial interpretation D(n) = (n-1)*(D(n-1) + D(n-2)).) San98: G. R. Sanchis: Swapping Hats: A Generalization of Montmort's Problem Mathematics Magazine 71:1 (1998) 53-57 (Let P_m(N) be the probability that m is the minimal cycle length of the cycles of a random permutation of 1..N. Thm: The limit (N->oo) of P_m(N) is exp(- H(m)) with H(m) the harmonic series. The proof is elementary by inclusion exclusion. (A complex analysis proof can be found in (Kol86). ) Str97: H. K. Strick; Pressemeldung(2), Erg"anzungen zum Rencontre-Problem, Praxis der Mathematik 39:3 (Juni 1997) 101-103 (Ist Astrologie schlechter als raten?) Tak67: L. Takacs; On the Method of Inclusion and Exclusion, Journal of the American Statistical Association 62 (1967) 102-113 Tak80: L. Takacs; The problem of coincidences, Arch. Hist. Exact Sci. 21:3 (1980), 229-244. MR 82c:01025 (MR: This paper deals with the origin, history and various appearances of the problem of coincidences (matches, rencontres) in the theory of probability. The contributions of Montmort, Johann and Nikolaus Bernoulli, DeMoivre, Euler, and Catalan are discussed.) RPA: http://xraysgi.ims.uconn.edu/rpa-output/probability/derangement.p http://xraysgi.ims.uconn.edu/rpa-output/probability/derangement.p Appendix: --------- Counting Derangements: The 'Probleme des Rencontres' ---------------------------------------------------- Let D(n) the number of fix-point-free permutations of 1..n. The notation of semifactorials [GKP89] and antifactorials [Com74] are equal. These numbers satisfy the following recursions: (1D) D(n) = n*D(n-1) + (-1)^n (2D) D(n) = (n-1)*(D(n-1) + D(n-2)) It is easy to find a direct combinatorial proof of (2D) see [RBC74], but (1D) is much harder. [BeW91, Exp. 11.8] say: >> If you can find it an your own, your professor might give you an "A" in this course! << [Con74, Chap. 4.2] only says: >> combinatorial proofs are also easy to find! << [Rem83] gives a combinatorial interpretation of (1D). (3D) D(n) = n! * exp_n(-1) (4D) Sum_{n>=0} D(n) t^n/n! = exp(-t)/(1-t) Counting Arrangements: [Com74, p 75 Exc. 9] ------------------------------------------- The total number of arrangements of a set with n elements. (The number of permutations of all subsets.) This number P(n) = Sum_{k=0..n} (n)_k satisfies (1P) P(n) = n*P(n) + 1 (for n>=1) P(0) := 1 (2P) P(n) = n! * exp_n(1). Hence P(n) equals the integer closest to e*n!. Moreover we have as GF: (3P) Sum_{n>=0} P(n) t^n/n! = exp(t)/(1-t). Difference Fring - generates relatives of the factorials -------------------------------------------------------- The factorials F(n) and the semifactorials D(n) as well as the arrangements P(n) and the factorials F(n) are related by a difference fring. D(n) = n! * exp_n(-1) F(n) = n! P(n) = n! * exp_n(1). Note the similarity between D(n) and P(n). 1 1 2 6 24 120 0 1 4 18 96 1 3 14 78 2 11 64 9 53 44 1 2 5 16 65 326 1 3 11 49 261 2 8 38 212 6 30 174 24 144 120 More general we have the series: (1R) R_k(n) = n*R_k(n) + k^n (for n>=1) R_k(0) := 1 (2R) R_k(n) = n! * exp_n(k) (3R) Sum_{n>=0} R_k(n) t^n/n! = exp(k*t)/(1-t) With exp_n(z) = SUM_{0<=k<=n} z^k / k! the truncated exponential function. This difference scheme is called the EULER transformation and its inverse the BINOMIAL transformation in [BeS95]. If b_0 b_1 b_2 ... is the original sequence, with exponential generating function B(x), the difference fring a_0 a_1 a_2 ... has g.f. A(x) = exp(-x) B(x). If b_0 b_1 b_2 ... is the original sequence, with ordinary generating function B(x), the difference fring a_0 a_1 a_2 ... has g.f. A(x) = B(x/(1+x))/(1+x). Multinomial Falling Factorials Theorem: --------------------------------------- The following formular is attributed to M. Frechet [DaB62, p70]: === \ (X1 + X2 + ... + Xn) = > Multinomial(k;a1,a2,...,an) (X1) (X2) ... (Xn) k / a1 a2 an === (a1, a2, ..., an) a1+a2+ ...+an = k this is equivalent (divide by k!) to === \ Binomial(X1+X2+...+Xn,k) = > Binomial(X1,a1) Binomial(X2,a2) ... Binomial(Xn,an) / === (a1, a2, ..., an) a1+a2+ ...+an = k Proof: by induction case n=1: Identity case n=2: The Vandermonde-Convolution === \ Binomial(X1+X2,k) = > Binomial(X1,i) Binomial(X2,k-i) / === i case: n-1 -> n === \ Binomial(X1+X2+...+Xn,k) = > Binomial(X1+X2+...+X(n-1),i) Binomial(Xn,k-i) / === i === \ = > Binomial(X1,a1) Binomial(X2,a2) ... Binomial(Xn,an) / === (a1, a2, ..., an) a1+a2+ ...+an = k qed. Corallary (A): -------------- If all Xi are zero or one (that means Xi*(Xi-1) = 0) then: === \ (X1 + X2 + ... + Xn) = > Multinomial(a) (X1) (X2) ... (Xn) k / a1 a2 an === (a1, a2, ..., an) a1+a2+ ...+an = k = k! * SymmetricFunction({X1,X2,...,Xn}, k) Where the SymmetricFunction is defined as: SymmetricFunction({X1,X2,...,Xn}, k) n-k = [z ] (z+X1)*(z+X2)*(z+X3)*...*(z+Xn) === \ (B) = > X X ... X / a1 a2 ak === 1<=a1=2. n Prob(Z_n = 0) = (1 - 1/n) This is allways too small (the exact value is exp_n(-1)). The relative error is of first order as: n 2 -2 ( 1 + x/n ) = exp(x) ( 1 - x / 2n ) + O(n ) Possion distribution: --------------------- PF(z) : the probability generating function. FM(z) : exponential factorial-moment generating function. M (z) : exponential moment generating function. C (z) : exponential cumulant generating function. PF(z) = exp( lambda(z-1) ) FM(z) = exp( lambda z ) M (z) = exp( lambda (exp(z) - 1) ) C (z) = lambda (exp(z) - 1) (0) Prob(X=k) = lambda ^ k / k! * exp(-lambda) for k >= 0. (1) E((X) ) = lambda ^ k k (2) E( X^k ) = Bell_polynimial(lambda) (3) Cumulant (X) = lambda k See for example [Knu68, Chap. 1.2.10 Exercise 16] or [Pit97]. A bound for the maximal difference between the matching distribution and the the Poisson distribution gives [Mic96]. Expected number of k-cycles: ---------------------------- Instead of counting fixpoints one can count the number of k-cycles. X_i,k,n = [i is member of a k-cycle of an n-permutation] Y_k,n = # elements i which are member of a k-cycle. Z_k,n = # k-cycles. Y_k,n = X_1,k,n + X_2,k,n + ... + Y_n,k,n. Z_k,n = Y_k,n / k. Now we can calculate the expectations. Prob(X_i,k,n = 1) = E(X_i,k,n) = 1/n * [k<=n] The Foata-Sch\"utzenberger Transformation (the cycle <-> block correspondence) gives a calculation-free proof, that all cycle-length are equal likely to contain number n. [(Knu68, p176 (2nd Ed)] calls this transformation: "An unusual correspondencs".) E(Y_k,n) = [k<=n] // Knuth's characteristic function notation. The expected number of k-cycles is: E(Z_k,n) = 1/k * [k<=n] This has been done in a more combinatorial manner in [Knu68, p 177 (2nd Ed)]. Therefore the expected number of cycles of a n-permutation is E(#cycles) = 1 + 1/2 + 1/3 + ... + 1/n = ln(n) + O(1). This derivation is generating function free. Via the cycle-block correspondence we get E(#left-right-maxima) = E(#cycles). Renkontre (Expected number of rounds): -------------------------------------- Silverman [Sil71, problem 75] considers the problem: Put n letters at random into n envelopes. Pull out all mismatched ones again. This is one round. Then put the remaining letters at random into the remaining envelopes. Repeat the process until all letters are matched. What is the average number of rounds? Let W_n be the waiting time until all letters are matched. Silverman says: >> As the expected number of fixpoints in each round is one, the expected number of rounds is n. << The result is correct, but I don't see the principle it uses. One can derive the result W_n = n as follows: Let p_k,n be the probability that a random permutaion on n points has exactly k fixpoints. We know, that the expected number of fixpoints is one. 1 = SUM k * p_k,n (expected number of fixpoints) Induction begin n=0: W_0 = 0 Induction n-1 -> n: W_n = 1 + Sum p_k,n * W_(n-k) We know W_k = k for k < n. Assume W_n = n one gets n = Sum k * p_k,n + Sum p_k,n * (n-k) = n * Sum p_k,n = n Therefore the recurrence is correct for n. The same problem was solved in two ways in [MM95.1454]. Expected first match: --------------------- >What is the prob that the first fixed point of a randomly chosen >permutation of 1, 2, ... , N is k? > >[For clarity, X is the set {1, 2, ..., N}. f is a randomly chosen >bijection on X. What is the prob. that k is the smallest value for which >f(k)=k?] Let f(n,k) be the number of permutations of {1,....n} with first fixed point k. Then the answer to the question is clearly f(n,k)/n!. It remains to evaluate f(n,k). I get: k === \ t+1 f(n,k) = > (-1) C(k-1,t-1) (n-t)! (A) / === t = 1 This follows pretty easily from the observations that f(n,1) = (n-1)! (*) f(n,k) = f(n,k-1) - f(n-1,k-1) (**) To prove (**), observe that to construct a permutation of n elements in which k is the first fixed point, you essentially have to permute the n-1 remaining elements in such a way that the first fixed point is not among the first k-1 elements. This gives k-1 === \ f(n,k) = (n-1)! - > f(n-1,t) / === t = 1 from which (*) follows. Steven E. Landsburg landsbur@troi.cc.rochester.edu Another way of proving (A) is to use the inclusion-exclusion principle. If F_j denotes the permutations in S_n with j as a fixed point, then f(n,k) is the cardinality of K_k - F_1 - F_2 - ... - F_{k-1}. This set consists of the elements of F_k notin the union of the F_j intersect F_k for j < k. Using the inclusion-exclusion principle to count these gives the above formula. Robin Chapman -- http://www.mathematik.uni-bielefeld.de/~sillke/ mailto:Torsten.Sillke@uni-bielefeld.de