Page 1 of 2 12 LastLast
Results 1 to 15 of 17

Math Help - Combinatorics.

  1. #1
    Member
    Joined
    Feb 2009
    Posts
    138

    Combinatorics.

    Hi:
    S= {1, 2, ..., n}, T= {f: S-->S| i < j implies if <= jf}. How many elements does T have? It's been two days I have been working on this problem and still I don't find the solution. May be somebody gives me a little help. Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by ENRIQUESTEFANINI View Post
    Hi:
    S= {1, 2, ..., n}, T= {f: S-->S| i < j implies if <= jf}. How many elements does T have? It's been two days I have been working on this problem and still I don't find the solution. May be somebody gives me a little help. Thanks.
    Does if mean f(i) and likewise for jf? Then isn't |T| = 1 with only the identity function? We are saying we want all permutations that are order-preserving..

    EDIT: Oh sorry that's only if f is onto. Okay let me think about it.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Feb 2009
    Posts
    138
    Yes. if, jf are f(i), f(j) respectively. Thanks for your reply.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by ENRIQUESTEFANINI View Post
    Yes. if, jf are f(i), f(j) respectively. Thanks for your reply.
    I recommend looking at small values of n to get a handle. I think the combinatorial solution is fairly tricky. If all you need to do is generate numbers, then I think an easier option is to find a recursion (you can define a helper function like g(n,k) to suit your needs.) The combinatorial formula and explanation can be found by entering the first few terms in OEIS.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Feb 2009
    Posts
    138
    To generate the numbers is not what I want. Neither is to haave the formula. But, yes, the reasoning which takes me to the formula.

    The problem is given as an example in a text book. Reading further on I have just discovered the author provides the answer, although he does not explain how one reaches to it. It is:

    \sum_{k=1}^{n-1}\left(\begin{array}{c}{n-1}&{k-1}\end{array}\right)\left(\begin{array}{c}n&k\end{  array}\right) - 1

    Now my curiosity is greater than before: why has the formula this form? If I start from a function like g(n,k), and if I call u (u(n)) the funcion that gives me |T| when |S| = n, may be I could construct u. That is, I must find g(n,n) for all n. Regards and best wishes.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by ENRIQUESTEFANINI View Post
    To generate the numbers is not what I want. Neither is to haave the formula. But, yes, the reasoning which takes me to the formula.

    The problem is given as an example in a text book. Reading further on I have just discovered the author provides the answer, although he does not explain how one reaches to it. It is:

    \sum_{k=1}^{n-1}\left(\begin{array}{c}{n-1}&{k-1}\end{array}\right)\left(\begin{array}{c}n&k\end{  array}\right) - 1

    Now my curiosity is greater than before: why has the formula this form? If I start from a function like g(n,k), and if I call u (u(n)) the funcion that gives me |T| when |S| = n, may be I could construct u. That is, I must find g(n,n) for all n. Regards and best wishes.
    That formula does not produce correct values so maybe there is a typo somewhere. Formula:

    \displaystyle |T_n| = \sum_{k=0}^{n-1}\binom{n+k-1}{k} = \binom{2n-1}{n}

    Explanation quoted from A001700:

    "To show for example that C(2n+1, n+1) is the number of monotone maps from 1..n+1 to 1..n+1, notice that we can describe such a map by a nondecreasing sequence of length n+1 with entries from 1 to n+1. The number k of increases in this sequence is anywhere from 0 to n. We can specify these increases by throwing k balls into n+1 boxes, so the total is Sum_{k=0..n} C((n+1)+k-1, k) = C(2n+1, n+1)."
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Some ideas how we can solve this

    1. Note that if i < j, and f(i) = f(j) then for all k such that i<k<j , f(k) = f(i) = f(j)
    2. so essentially we need to divide the domain into contagious paritions and each partition go a specific element in the co-domain.

    so if the domain is divided into 'k' paritions -
    we can do this in (n-1)C(k-1) ways

    so the range has to be 'k' elements - k elements can be selected in (n)C(k) ways

    once this is done there is only one way to map the elemments
    so for a specific value of k we have number of funtions = [(n-1)C(k-1)]*[(n)C(k)]

    sum it from k = 1 to k = n; we will get the |T|

    hope this works - prima facie can't see anything going wrong here

    EDIT - sorry didn't notice earlier posts - looks like the my argument works. The formula I got is exactly similar to what author provided
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Feb 2009
    Posts
    138
    I only had checked for n=2 and n=3, observing the formula gave the "correct" # of elems plus one. If I had verified for greater values of n I'd have discovered the discrepancy is much more severe. In fact, the whole story is this:
    I quote from "Tutorial - Computing with Semigroups in GAP": "Consider the set [n] = {1, 2, ..., n} with the usual total order. An endomorphism of [n] is a map f: [n] --> [n] such that i < j implies if <= jf. Let O_n denote the semigroup of singular endomorphisms of the chain [n]. It is a simple combinatorial observation that O_n has size...". And here they give the formula I wrote.

    In an effort to understand the meaning of the term "singular endomorphism", I tried to deduce the formula. But now, in view of your post, I see I have no other remedy than to learn the definition of singular endomorphism in the context of semigroups. This, however, I have tried to do (using internet). But my efforts have all been in vain. Thanks again for your posts and regards.

    EDIT: nevertheless, the problem as I stated it in post #1 is interesting in itself. I mean, interesting to me.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Feb 2009
    Posts
    138
    It's true. The formula seems to work. I checked it for n=4. But the authors are excluding one of the mappings. It again gave one less than the number of monotone mappings. This difference of one explicitly appears in the term -1 of the formula. The reason of this term ("term"=summand) must lie in the definition of singular endomorphism. Thanks again.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by ENRIQUESTEFANINI View Post
    It's true. The formula seems to work. I checked it for n=4. But the authors are excluding one of the mappings. It again gave one less than the number of monotone mappings. This difference of one explicitly appears in the term -1 of the formula. The reason of this term ("term"=summand) must lie in the definition of singular endomorphism. Thanks again.
    I think instead of

    \sum_{k=1}^{n-1}\left(\begin{array}{c}{n-1}&{k-1}\end{array}\right)\left(\begin{array}{c}n&k\end{  array}\right) - 1

    you meant

    \displaystyle \left[\sum_{k=1}^{n-1}\binom{n-1}{k-1}\binom{n}{k} \right]+1
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Feb 2009
    Posts
    138
    No. The book says -1 (minus one). And later on they use an example with n=4 and say O_n=34. So it could hardly be a typo.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by ENRIQUESTEFANINI View Post
    No. The book says -1 (minus one). And later on they use an example with n=4 and say O_n=34. So it could hardly be a typo.
    We have \displaystyle |T_4|=35

    \displaystyle \sum_{k=1}^{4-1}\binom{4-1}{k-1}\binom{4}{k}=34

    We need to add 1 in order to get |T|.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Yes - I also think it should be

    \displaystyle \left[\sum_{k=1}^{n-1}\binom{n-1}{k-1}\binom{n}{k} \right]+1 = \displaystyle \left[\sum_{k=1}^{n}\binom{n-1}{k-1}\binom{n}{k} \right]
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    (misinterpreted something grammatically, please ignore this post.)
    Last edited by undefined; July 20th 2010 at 03:24 AM.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member
    Joined
    Feb 2009
    Posts
    138
    sum_{k=1..n-1} C(n-1,k-1)C(n,k) = C(2n-1,n-1). So |T_4| = 35 according to this formula. That is, for n=4 |T_4| = C(2*4-1, 4-1) = C(7, 3) = 35.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 18th 2010, 09:14 PM
  2. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 3rd 2010, 06:24 PM
  3. combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 1st 2010, 11:53 PM
  4. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 10th 2009, 07:03 AM
  5. Combinatorics
    Posted in the Statistics Forum
    Replies: 4
    Last Post: December 2nd 2008, 03:27 PM

/mathhelpforum @mathhelpforum