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

英文解析

25. [ 15 ] How many functions f : { 1 , 2 , 3 , 4 , 5 } → { 1 , 2 , 3 , 4 , 5 } have the property that f ( { 1 , 2 , 3 } ) andf ( 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 } ,
    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 3
    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 possiblevalue for each element of { 1 , 2 , 3 } , 4 ways to assign { 4 } with a value from { 1 , 2 , 3 , 5 } , and 5 ways toassign 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.
    See the sections “Linear homogeneous recurrence relations with constant coefficients” and “Theorem” at http://en.2
    wikipedia.org/wiki/Recurrence_relation .
    See http://mathworld.wolfram.com/Vietas formulas.html .3
    Guts Round