PUMaC 2011 · 组合（B 组） · 第 4 题

PUMaC 2011 — Combinatorics (Division B) — Problem 4

[ 4 ] A function f : { 1 , 2 , . . . , n } → { 1 , . . . , m } is multiplication-preserving if f ( i ) f ( j ) = f ( ij ) for all 1 ≤ i ≤ j ≤ ij ≤ n , and injective if f ( i ) = f ( j ) only when i = j . For n = 9 , m = 88, the number of injective, multiplication-preserving functions is N . Find the sum of the prime factors of N , including multiplicity. (For example, if N = 12, the answer would be 2 + 2 + 3 = 7.)

解析

Since f (1) = f (1), then f (1) = 1. We have that f (2) = f (8) ≤ 88 , f (3) = f (9) ≤ 88, so f (2) ≤ 4 , f (3) ≤ 9. If f (2) = 2 and 3, there are respectively 5 and 6 possible values of f (3), which fixes the value of each of f (2) , f (3) , f (4) , f (6) , f (8) , f (9). Then f (5) , f (7) can be any of the 81 · 80 remaining values. If f (2) = 4 then f (3) 6 = 1 , 2 , 4 , 8 still, so f (3) can have 5 possible 8 4 values, and it follows that the total number of such functions is (5 + 6 + 5) · 81 · 80 = 2 · 3 · 5 , and the answer is 8 · 2 + 4 · 3 + 1 · 5 = 33 .