MathDB
Miklos Schweitzer 1975_2

Source:

December 30, 2008
functioncombinatorics proposedcombinatorics

Problem Statement

Let An \mathcal{A}_n denote the set of all mappings f:{1,2,…,n}→{1,2,…,n} f: \{1,2,\ldots ,n \} \rightarrow \{1,2,\ldots, n \} such that f−1(i):={k ⁣:f(k)=i }≠∅ f^{-1}(i) :=\{ k \colon f(k)=i\ \} \neq \varnothing implies f−1(j)≠∅,j∈{1,2,…,i}. f^{-1}(j) \neq \varnothing, j \in \{1,2,\ldots, i \} . Prove ∣An∣=∑k=0∞kn2k+1. |\mathcal{A}_n| = \sum_{k=0}^{\infty} \frac{k^n}{2^{k+1}}.
L. Lovasz
Back to ProblemsView on AoPS