What is the number of mappings?

Question

It is given that there are two sets of real numbers $A = \{a_1, a_2, ..., a_{100}\}$ and $B= \{b_1, b_2, ..., b_{50}\}.$ If there is a mapping $f$ from $A$ to $B$ such that every element in $B$ has an inverse image and $f(a_1)\leq f(a_2) \leq ...\leq f(a_{100})$ Then, what is the number of such mappings?

I have started tackling the problem by supposing that $b_1<b_2<...<b_{50}$ and dividing elements $a_1, a_2, ..., a_{100}$ in $A$ into $50$ nonempty groups according to their order. Now the problem is... How do I compute the number of mappings defined as $f: A\rightarrow B$ given the observations above?

Answer 1

EDIT:My idea is to do an order-preserving partition of the set {$1,2,..,100$} into 50 parts, e.g., (1,2,3), (4,5,6,7,..10),..., (98, 99,100). Then every number in the i-th part would map to $a_i$. I think this takes care of all maps.

This is a matter of balls-in-boxes , i.e., of finding the number of solutions to $x_1+x_2+.....+x_{50}=100; x_i \geq 0$, i.e.,it is a matter of counting the number of ordered partitions of the se $a_1, a_2,...,a_{100}$ into $50$ parts, and then $x_1$ is the number of preimages of $b_1$, and $x_i$ is the number of preimages of $b_i$. So, using the fact that the number of solutions to $$x_1+x_2+....+x_k=n $$ is $(n+k-1)C(k-1)$ , the number of solutions is $$(49+100-1)C(99)=148C99 $$.

Answer 2

To come up with such a function $f$, you need to decide, for each element $b_i \in B$, the number $n_i$ of elements of $A$ which are going to map to it. Once these numbers have been chosen, there is only one way to make the function $f$ because of the condition $f(a_1)\leq f(a_2) \leq ...\leq f(a_{100})$. So, how many ways are there to choose the numbers $n_i$? Well...

• Since each element of $B$ needs to have a nonempty preimage, you have the constraint $n_i \geq 1$.
• Since every element of $A$ must map somewhere, you have the constraint $\sum_{i=1}^{50} n_i = 100$.

Counting the solutions to a constrained integer equation of this type is a a pretty common problem. Similar questions have been asked before on this website, for instance here.

Answer 3

HINT:
Suppose $f(a_1)=b_{51},$ then there is only $1$ such mapping.
Suppose $f(a_1)=b_{50},$ then there are $\dbinom{50}{1}=50$ such mappings.
Suppose $f(a_1)=b_{49},$ then there are $\dbinom{51}{2}=1275$ such mappings.

Can you see a pattern!