PUMaC 2015 · 组合（A 组） · 第 3 题

PUMaC 2015 — Combinatorics (Division A) — Problem 3

[ 4 ] Consider a random permutation of the set { 1 , 2 , . . . , 2015 } . In other words, for each 1 ≤ i ≤ 2015, i is sent to the element a where a ∈ { 1 , 2 , . . . , 2015 } and if i 6 = j , then a 6 = a . i i i j What is the expected number of ordered pairs ( a , a ) with i − j > 155 and a − a > 266? i j i j

解析

[ 4 ] Consider a random permutation of the set { 1 , 2 , . . . , 2015 } . In other words, for each 1 ≤ i ≤ 2015, i is sent to the element a where a ∈ { 1 , 2 , . . . , 2015 } and if i 6 = j , then a 6 = a . i i i j What is the expected number of ordered pairs ( a , a ) with i − j > 155 and a − a > 266? i j i j Solution: First, observe that the total number of ordered pairs a , a satisfying i − j > 155 i j ( ) 2015 − 155 is equal to (2015 − 156) + (2015 − 157) + . . . + 1 = = 1728870, where we count by 2 casework on j = 1 , 2 , . . . , 1859. Since the permutation is random, the probability that any arbitrary ordered pair of elements a , a satisfy a − a > n for some n is the same for any i, j . Furthermore, this probability is i j i j equal to the number of ordered pairs x, y satisfying x − y > n and the total number of ordered pairs ( x, y ), as ( a , a ) is equally likely to be any ordered pair x, y (the former counted similarly i j as above). Thus, when n = 266 the probability is: ( ) 2015 − 266 759 2 p = = 2015 · 2014 2015 1 By linearity of expectation, we have that the expected total number of ordered pairs a , a i j satisfying i − j > 155 that also satisfy a − a > 266 is: i j 759 E = 1728870 · = 651222 2015 Authors: Roy Zhao, Bill Huang