How many one-to-one functions are there from a set with 5 elements to a set with 4 elements

$\begingroup$

Consider functions from a set with $5$ elements to a set with $3$ elements.
(a) How many functions are there?
(b) How many are one-to-one?
(c) How many are onto?

a) Each element mapped to $3$ images.
$3 \cdot 3 \cdot 3 \cdot 3 \cdot 3$

b) $0$

c) How do I do this?

Edit: I tried doing this way.

EDIT: There can be a set of cardinality {3,1,1} or {2,2,1}.

For {3,1,1}: 5C3 * 2C1 * 1C1 * 3!

For {2,2,1}: 5C2 * 3C2 * 1C1 * 3!

And i realized my 3! is wrong. Should be * 3 only. Why is that so?

asked Apr 28, 2016 at 8:47

RStyleRStyle

6071 gold badge5 silver badges14 bronze badges

$\endgroup$

5

$\begingroup$

You correctly found that there are $3^5$ functions from a set with five elements to a set with three elements. However, this counts functions with fewer than three elements in the range. We must exclude those functions. To do so, we can use the Inclusion-Exclusion Principle.

There are $\binom{3}{1}$ ways of excluding one element in the codomain from the range and $2^5$ functions from a set with five elements to the remaining two elements in the codomain.

There are $\binom{3}{2}$ ways of excluding two elements in the codomain from the range and $1^5$ functions from a set with five elements to the remaining element in the codomain.

By the Inclusion-Exclusion Principle, the number of surjective (onto) functions from a set with five elements to a set with three elements is

$$3^5 - \binom{3}{1}2^5 + \binom{3}{2}1^5$$

answered Apr 28, 2016 at 9:11

N. F. TaussigN. F. Taussig

68.2k13 gold badges52 silver badges70 bronze badges

$\endgroup$

2

$\begingroup$

Hint on c)

The "onto"-function will induce a partition of its domain (as any function) and this partition (actually the fibres of the function) will - because it is onto - have exactly $3$ elements. So to be found is in the first place how many such partitions exist. A fixed partition gives room for $3\times2\times1=6$ functions.

So you end up with: $$6\times\text{number of partitions on }\{1,2,3,4,5\}\text{ that have exactly }3\text{ elements}$$

Also have a look here (especially the counting of partitions).

A general formula for the number of onto-functions $\{1,\dots,n\}\to\{1,\dots,k\}$ is: $$k!S(n,k)$$where $S(n,k)$ stands for the Stirling number of the second kind.

answered Apr 28, 2016 at 8:55

drhabdrhab

143k9 gold badges70 silver badges191 bronze badges

$\endgroup$

1

How many one

How many one

How many onto functions are there from a set with 5 elements to a set with 3 elements?

How many one