HMMT 二月 2010 · 冲刺赛 · 第 25 题

HMMT February 2010 — Guts Round — Problem 25

[ 15 ] How many functions f : { 1 , 2 , 3 , 4 , 5 } → { 1 , 2 , 3 , 4 , 5 } have the property that f ( { 1 , 2 , 3 } ) and f ( f ( { 1 , 2 , 3 } )) are disjoint?

解析

[ 15 ] How many functions f : { 1 , 2 , 3 , 4 , 5 } → { 1 , 2 , 3 , 4 , 5 } have the property that f ( { 1 , 2 , 3 } ) and f ( f ( { 1 , 2 , 3 } )) are disjoint? Answer: 94 Let f ( { 1 , 2 , 3 } ) be A . Then A ∩ f ( A ) = ∅ , so A must be a subset of { 4 , 5 } . If B = { 4 , 5 } , 3 there are 2 − 2 ways to assign each element in { 1 , 2 , 3 } to a value in { 4 , 5 } , and 9 ways to assign each element of { 4 , 5 } to a value in { 1 , 2 , 3 } , for a total of 54 choices of f . If A = { 4 } , there is 1 possible value for each element of { 1 , 2 , 3 } , 4 ways to assign { 4 } with a value from { 1 , 2 , 3 , 5 } , and 5 ways to assign a value to { 5 } . Similarly, if A = { 5 } , there are 4 · 5 = 20 choices for f . In total, there are 54 + 20 · 2 = 94 possible functions. 2 See the sections “Linear homogeneous recurrence relations with constant coefficients” and “Theorem” at http://en. wikipedia.org/wiki/Recurrence_relation . 3 See http://mathworld.wolfram.com/VietasFormulas.html . Guts Round