PUMaC 2022 · 组合（A 组） · 第 8 题
PUMaC 2022 — Combinatorics (Division A) — Problem 8
题目详情
- A permutation π : { 1 , 2 , . . . , N } → { 1 , 2 , . . . , N } is very odd if the smallest positive integer k k k such that π ( a ) = a for all 1 ≤ a ≤ N is odd, where π denotes π composed with itself k times. Let X = 1, and for i ≥ 1, let X be the fraction of all permutations of { 1 , 2 , . . . , i } that 0 i are very odd. Let S denote the set of all ordered 4-tuples ( A, B, C, D ) of nonnegative integers such that A + B + C + D = 2023. Find the last three digits of the integer X 2023 X X X X . A B C D ( A,B,C,D ) ∈S Name: Team: Write answers in table below: Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 2
解析
- A permutation π : { 1 , 2 , . . . , N } → { 1 , 2 , . . . , N } is very odd if the smallest positive integer k k k such that π ( a ) = a for all 1 ≤ a ≤ N is odd, where π denotes π composed with itself k times. Let X = 1, and for i ≥ 1, let X be the fraction of all permutations of { 1 , 2 , . . . , i } that 0 i are very odd. Let S denote the set of all ordered 4-tuples ( A, B, C, D ) of nonnegative integers such that A + B + C + D = 2023. Find the last three digits of the integer X 2023 X X X X . A B C D ( A,B,C,D ) ∈S Proposed by Daniel Carter Answer: 116 A permutation is very odd if and only if its cycle decomposition consists only of odd cycles. Letting c be the number of cycles of length k , the number of very odd permutations for a k ∞ P given n is therefore equal the sum over all solutions to the equation n = (2 i − 1) c of the 2 i − 1 i =1 number of ways there are to create a permutation with those cycle lengths. Given any fixed c , there are k c − 1 k Y 1 n − ik 1 n ! = · c k c ! k c ! ( n − kc )!( k !) k k k i =0 ways to choose the numbers in c cycles of length k where the cycles are indistinguishable, and k ( k − 1)! ways to order each cycle given the k numbers in a cycle, for a total of c k (( k − 1)!) n ! n ! · = c c k k c ! ( n − kc )!( k !) ( n − kc )! c ! k k k k k ways to form the c cycles of length k Now, we can repeat the process on c using the new k k +2 ′ n = n − kc . Multiplying this over all k , the product k n ! ( n − k )! ( n − 3 k )! 1 3 · · . . . ( n − k )! ( n − 3 k )! ( n − 5 k )! 1 3 5 n ! n ! telescopes to = n !, which gives that there are ways to create a permuta- ∞ Q 0! c 2 i − 1 c !(2 i − 1) 2 i − 1 i =1 tion with c cycles of length 2 i − 1 for all i ∈ N . Therefore, the generating function of the 2 i − 1 sequence X is given by n ! ∞ ∞ ∞ ∞ 2 n +1 3 5 X Y X Y 1 t t t n m (2 n +1) X t = t = exp = exp( t + + + . . . ) n m m !(2 n + 1) 2 n + 1 3 5 n =0 n =0 m =0 n =0 Let S denote the set of all ordered 4-tuples of nonnegative integers satisfying a + b + c + d = n . n P Consider the sequence Y = X X X X . Our answer is 2023 Y . But the n a b c d 2023 ( a,b,c,d ) ∈S n generating function of Y is the fourth power of the generating function of X , so since the n n ∞ P n +1 n ( − 1) x generating function of log(1 + x ) is , we have n n =1 ∞ 2 3 5 X 4 t 4 t 1 + t n Y t = exp(4 t + + + . . . ) = exp(2 log(1 + t ) − 2 log(1 − t )) = n 3 5 1 − t n =0 2 2 4 4 4 t = − 1 = 1 − + = 1 + 2 1 − t 1 − t (1 − t ) 1 − t 5 ∞ P 1 n Since the generating function for is t , the generating function for this is equal to 1 − t n =0 ∞ P n 2023 2 1 + 4 nt . The coefficient of t is Y = 4 · 2023, so our answer is 4 · 2023 , the last 2023 n =1 three digits of which are 116. 6