# Thread: basic set structures program problem

1. ## basic set structures program problem

we are asked to solve a problem in discrete mathematics and we must complete it within 2 days.. can you help me with it? The problem is:

Using a computational program you have written do the exercise...

Calculate the number of onto functions from a set S to a set T, where S and T are finite sets of various sizes. Can you determine a formula for the number of such functions?

and also can u suggest a program I can use to simulate this problem? i'm thinking of visual basic or C++ but cant start because I cant simply find a formula to fit for the problem..

We are also asked to solve two more problems, and I found them easy and finished them but I cant seem to understand this one.. hope you can help me.. thank you

2. Clearly if |S| < |T| there are no onto functions at all. And if |S| = |T| there are |S|! onto functions.
In the remaining cases I think I'd do this by subtracting from the total number of functions from S to T the number of functions that aren't onto. For example suppose |T| = 3. Lets denote the number of onto functions from a set of size m onto a set of size n by F(m,n)
Then there are 3^|S| functions in total, and the functions that aren't onto take either 1 or 2 values from T. There are 3 choose 1 = 3 subsets of size 1 of T so there are 3*F(|S|,1) functions that take 1 value. Similarly there are 3 choose 2 = 3 subsets of size 2 of T, so that there are 3*F(|S|,2) functions that take exactly 2 values from T. So you could build up a recursive calculation of the number of onto functions from |S| to |T| in this hard case.
It's likely that the numbers you get are some well-known combinatorial function of two numbers such as something to do with the Catalan numbers , so that there might be some closed form formula, but I don't know.

3. Originally Posted by toki
Calculate the number of onto functions from a set S to a set T, where S and T are finite sets of various sizes. Can you determine a formula for the number of such functions?
Suppose that $N = \left| S \right| \geqslant \left| T \right| = K$,
then the number of surjections (onto functions) from $S \to T$ is given by
$Surj(N,K) = \sum\limits_{j = 0}^K {\left( { - 1} \right)^k \binom{K}{j} \left( {K - j} \right)^N }.$

4. It's not easy. Here's the analysis that I did for when I did this some time ago for two special cases:

The number of surjections from $S$ to $T$, where $| S| = m, |T| = n$ is:

$\begin{cases}
n! & : m = n \\
\frac {n ((n + 1)!)} 2 & : m = n + 1 \\
\frac {n (3 n + 1) ((n + 2)!)} {24} & : m = n + 2
\end{cases}
$

Proof:

If $m = n$ then any mapping $\phi: S \to T$ is a bijection.

Let $m = n + 1$.

There will necessarily be one (and only one) instance where two elements of $S$ map to one element of $T$.

There are $\binom m 2 = \binom {n + 1} 2$ ways of choosing $2$ elements out of $S$.

For each of these pairs, there are $n$ possible elements in $T$ to which they can be mapped.

Thus there are $\binom {n + 1} 2 n$ ways to map two elements to one.

Of the remaining $n - 1$ elements of $S$ and $T$, there are $(n - 1)!$ remaining mappings, as they are bijections.

Thus the total number of surjections from $S$ to $T$ where $|S| = n + 1, |T| = n$ is:

$\binom {n + 1} 2 n (n - 1)! = \frac {n (n + 1) n (n - 1)!} 2 = \frac {n (n + 1)!} 2
$

Now let $m = n + 2$.

Either:
1. There will be three elements of $S$ mapping to one element of $T$;
Or:
2. There will be two instances of two elements of $S$ mapping to one element of $T$.

Taking these two in turn:

1. Three elements of $S$ mapping to one element of $T$:

In the first case, there are $\binom {n + 2} 3$ ways of picking those three elements, and for each of these there are $n$ possible images of those three, and for each of those there are $(n - 1)!$ left over bijections.

Thus there are $\binom {n + 2} 3 n (n - 1)!$ mappings involving three elements of $S$ mapping to one element of $T$.

2. Two instances of two elements of $S$ mapping to one element of $T$:

There are $\binom {n + 2} 2 n$ ways of doing the first, and, having chosen them, another $\binom n 2 (n - 1)$ ways of doing the second.

That counts both twice.

The remaining $n - 2$ elements contribute towards $(n - 2)!$ bijections.

So the total number of mappings in this category is:

$(\binom {n + 2} 2 n) (\binom n 2 (n - 1)) \frac 1 2 (n-2)!$

The total number of such surjections is therefore:

$\frac {n (3 n + 1) ((n + 2)!)} {24}$

(after some tedious algebra that I can't be bothered to repeat here).

The general question, where $m - n$ is arbitrary, is harder, but we can identity the following rule:

The number of ways you can map $m - n + 1$ elements to 1 is:

$\binom m {m - n + 1} n (n - 1)! = \binom m {m - n + 1} n!$

The problem now becomes one of determining how many ways one can divide a set $S$ into $| T|$ partitions, and what the nature of those partitions are.

NOTE: None of this has been checked by anyone so it may be totally wrong. It was the result of an inexpensive way to pass the evening holed up in a hotel on a business trip a few years go.

5. Originally Posted by Plato
Suppose that $N = \left| S \right| \geqslant \left| T \right| = K$,
then the number of surjections (onto functions) from $S \to T$ is given by
$Surj(N,K) = \sum\limits_{j = 0}^K {\left( { - 1} \right)^k \binom{K}{j} \left( {K - j} \right)^N }.$
Okay Plato, that's the solution - where can I go to find a proof? I have an intellectual interest in this ...