Results 1 to 5 of 5

Thread: basic set structures program problem

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    2

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member alunw's Avatar
    Joined
    May 2009
    Posts
    188
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,743
    Thanks
    2814
    Awards
    1
    Quote Originally Posted by toki View Post
    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 $\displaystyle N = \left| S \right| \geqslant \left| T \right| = K$,
    then the number of surjections (onto functions) from $\displaystyle S \to T$ is given by
    $\displaystyle Surj(N,K) = \sum\limits_{j = 0}^K {\left( { - 1} \right)^k \binom{K}{j} \left( {K - j} \right)^N }. $
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    1,281
    Thanks
    197
    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 $\displaystyle S$ to $\displaystyle T$, where $\displaystyle | S| = m, |T| = n$ is:

    $\displaystyle \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 $\displaystyle m = n$ then any mapping $\displaystyle \phi: S \to T$ is a bijection.

    Let $\displaystyle m = n + 1$.

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

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

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

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

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

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

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


    Now let $\displaystyle m = n + 2$.

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


    Taking these two in turn:

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

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

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

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

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

    That counts both twice.

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

    So the total number of mappings in this category is:

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



    The total number of such surjections is therefore:

    $\displaystyle \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 $\displaystyle m - n$ is arbitrary, is harder, but we can identity the following rule:

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

    $\displaystyle \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 $\displaystyle S$ into $\displaystyle | 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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    1,281
    Thanks
    197
    Quote Originally Posted by Plato View Post
    Suppose that $\displaystyle N = \left| S \right| \geqslant \left| T \right| = K$,
    then the number of surjections (onto functions) from $\displaystyle S \to T$ is given by
    $\displaystyle 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 ...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Problem solving algebraic structures task
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: Jan 29th 2011, 10:12 AM
  2. program problem about primality test
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jan 11th 2010, 11:02 PM
  3. Fixing The Program (Program Correctness)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Mar 21st 2009, 02:17 PM
  4. Program Correctness Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Mar 18th 2009, 06:07 PM
  5. Simple program for quizing basic math skills
    Posted in the Math Software Forum
    Replies: 0
    Last Post: Jul 25th 2008, 09:52 PM

Search Tags


/mathhelpforum @mathhelpforum