LinkBack URL
About LinkBacksHi:
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..Originally Posted by ENRIQUESTEFANINI
EDIT: Oh sorry that's only if f is onto. Okay let me think about it.
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.
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:
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: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:
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.
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)."
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
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.
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.
  |
