MathDB
Number of functions that have path - ILL 1990 POL2

Source:

September 18, 2010
functioncombinatorics unsolvedcombinatorics

Problem Statement

Given an mm-element set MM and a kk-element subset K⊂MK \subset M. We call a function f:K→Mf: K \to M has "path", if there exists an element x0∈Kx_0 \in K such that f(x0)=x0f(x_0) = x_0, or there exists a chain x0,x1,…,xj=x0∈Kx_0, x_1, \ldots, x_j = x_0 \in K such that xi=f(xi−1)_xi = f(x_{i-1}) for i=1,2,…,ji = 1, 2, \ldots, j. Find the number of functions f:K→Mf: K \to M which have path.
Back to ProblemsView on AoPS