Results 1 to 5 of 5

Math Help - 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
    18,616
    Thanks
    1579
    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 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 }.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    820
    Thanks
    31
    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}<br />
n! & : m = n \\<br />
\frac {n ((n + 1)!)} 2 & : m = n + 1 \\<br />
\frac {n (3 n + 1) ((n + 2)!)} {24} & : m = n + 2<br />
\end{cases}<br />

    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<br />


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

  5. #5
    Super Member Matt Westwood's Avatar
    Joined
    Jul 2008
    From
    Reading, UK
    Posts
    820
    Thanks
    31
    Quote Originally Posted by Plato View Post
    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 ...
    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: January 29th 2011, 10:12 AM
  2. program problem about primality test
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 11th 2010, 11:02 PM
  3. Fixing The Program (Program Correctness)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 21st 2009, 02:17 PM
  4. Program Correctness Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 18th 2009, 06:07 PM
  5. Simple program for quizing basic math skills
    Posted in the Math Software Forum
    Replies: 0
    Last Post: July 25th 2008, 09:52 PM

Search Tags


/mathhelpforum @mathhelpforum