OMC221(C)

　$X_n=\{1,1,2,2,\dots,n,n\}$ とする．$f$ の定義をその部分集合に拡張する．ここで，$f(\emptyset)=1$ とする．このとき，$n=2,3,\dots$ について，$X_{n-1}$ の部分集合 $V$ と $\{n,n\}$ の部分集合の和集合について，以下が成立する： $$\begin{aligned} f(V\cup \emptyset)&=f(V),\\ f(V\cup \{n\})&= \begin{cases} f(V)&(Vの要素数が奇数)\\ nf(V)&(Vの要素数が偶数) \end{cases},\\ f(V\cup \{n,n\})&=nf(V). \end{aligned}$$ 　よって，$X_n$ の部分集合 $V$ のうち，要素数が偶数であるものの $f(V)$ の総和を $a_n$，要素数が奇数であるものの $f(V)$ の総和を $b_n$ とすると，$a_1=2, ~ b_1=1$ および $n=2,3,\dots$ について以下が成立する： $$a_n=(1+n)a_{n-1}+b_{n-1}, \quad b_n=na_{n-1}+(1+n)b_{n-1}.$$ よって，求めるものは $a_{5}+b_{5}-1=1729+3430-1=\mathbf{5158}$ である．