MathDB

64

Part of 1990 IMO Longlists

Problems(1)

Number of functions that have path - ILL 1990 POL2

Source:

9/18/2010
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.
functioncombinatorics unsolvedcombinatorics