1
$\begingroup$

Let $A=\{x_1,x_2,....x_{50}\}$ and $B=\{y_1,y_2,....y_{20}\}$ be two sets of real numbers. What is the total number of functions $f:A\rightarrow B$ such that f is onto and $f(x_1)\le f(x_2)\le f(x_3)\le...f(x_{50})$ is

(a) $(^{49}_{19})$ (b) $(^{49}_{20})$(c) $(^{50}_{19})$(d) $(^{50}_{20})$

$\endgroup$

2 Answers 2

2
$\begingroup$

The problem is equivalent to asking how many functions $f$ there are from $A=\{1,\ldots,50\}$ to $B=\{1,\ldots,20\}$ such that $f$ is onto and non-decreasing. Suppose that $f$ is such a function. If we know how many elements of $A$ are sent to each member of $B$, then we know what $f$ is. For instance, if $3$ elements of $A$ are sent to $1$ and $5$ to $2$, we know that $$f(1)=f(2)=f(3)=1\,,$$ $$f(4)=f(5)=f(6)=f(7)=f(8)=2\,,$$ and $$f(9)=3\,.$$ For $k=1,\ldots,20$ let $n_k$ be the number of elements of $A$ sent to $k$ by $f$; then we know that $n_k\ge 1$ for each $k\in B$, since $f$ is onto, and of course we know that

$$n_1+n_2+\ldots+n_{20}=50\,.\tag{1}$$

Conversely, each solution to $(1)$ in positive integers gives us a non-decreasing function from $A$ onto $B$. Thus, our problem amounts to counting the solutions to $(1)$ in positive integers. This is a standard stars and bars problem; the answer is $\binom{50-1}{20-1}=\binom{49}{19}$, and the reasoning is explained quite well in the proof of Theorem $1$ at the link.

$\endgroup$
1
$\begingroup$

This is a "stars and bars" problem.

We have to allocate 50 input elements into 20 bins, or output elements, such that every output element has at least one input.

That leaves 30 stars that we are free to allocate. There is one bar that separates each bin giving us 19 bars.

${49\choose 19}$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .