# Combinatorics.

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Jul 19th 2010, 10:30 PM
ENRIQUESTEFANINI
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.
• Jul 19th 2010, 11:01 PM
undefined
Quote:

Originally Posted by ENRIQUESTEFANINI
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.
• Jul 19th 2010, 11:05 PM
ENRIQUESTEFANINI
• Jul 19th 2010, 11:36 PM
undefined
Quote:

Originally Posted by ENRIQUESTEFANINI

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.
• Jul 20th 2010, 12:05 AM
ENRIQUESTEFANINI
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:

$\displaystyle \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.
• Jul 20th 2010, 12:15 AM
undefined
Quote:

Originally Posted by ENRIQUESTEFANINI
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:

$\displaystyle \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 \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)."
• Jul 20th 2010, 12:32 AM
aman_cc
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
• Jul 20th 2010, 12:41 AM
ENRIQUESTEFANINI
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.
• Jul 20th 2010, 01:22 AM
ENRIQUESTEFANINI
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.
• Jul 20th 2010, 01:34 AM
undefined
Quote:

Originally Posted by ENRIQUESTEFANINI
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.

$\displaystyle \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 \displaystyle \left[\sum_{k=1}^{n-1}\binom{n-1}{k-1}\binom{n}{k} \right]+1$
• Jul 20th 2010, 01:41 AM
ENRIQUESTEFANINI
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.
• Jul 20th 2010, 01:57 AM
undefined
Quote:

Originally Posted by ENRIQUESTEFANINI
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 \displaystyle |T_4|=35$

$\displaystyle \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|.
• Jul 20th 2010, 01:59 AM
aman_cc
Yes - I also think it should be

$\displaystyle \displaystyle \left[\sum_{k=1}^{n-1}\binom{n-1}{k-1}\binom{n}{k} \right]+1$ = $\displaystyle \displaystyle \left[\sum_{k=1}^{n}\binom{n-1}{k-1}\binom{n}{k} \right]$
• Jul 20th 2010, 02:05 AM
undefined
(misinterpreted something grammatically, please ignore this post.)
• Jul 20th 2010, 02:07 AM
ENRIQUESTEFANINI
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.
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last