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.

Printable View

- Jul 19th 2010, 10:30 PMENRIQUESTEFANINICombinatorics.
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 PMundefined
- Jul 19th 2010, 11:05 PMENRIQUESTEFANINI
Yes. if, jf are f(i), f(j) respectively. Thanks for your reply.

- Jul 19th 2010, 11:36 PMundefined
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 AMENRIQUESTEFANINI
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 AMundefined
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 AMaman_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 AMENRIQUESTEFANINI
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 AMENRIQUESTEFANINI
**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 AMundefined
- Jul 20th 2010, 01:41 AMENRIQUESTEFANINI
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 AMundefined
- Jul 20th 2010, 01:59 AMaman_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 AMundefined
(misinterpreted something grammatically, please ignore this post.)

- Jul 20th 2010, 02:07 AMENRIQUESTEFANINI
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.