Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

• Forgot your password?
• Apply for membership

1. • CommentRowNumber1.
   • CommentAuthorMirco Richter
   • CommentTimeMar 4th 2012
   • (edited Mar 4th 2012)
   • PermaLink
   Author: Mirco Richter
   Format: MarkdownItexSimple Question: 1.) How many morphisms $f: [n] \rightarrow [m]$ are there in $\Delta$ ? ( Or equivalent: What is $|\Delta [m]_n |$ ? ) 2.) Is there a research field in combinatorics that is concerned with monotonic integer maps from $[n]$ to $[m]$ (Just in case I have another 'combinatorical' question concerning $\Delta$)

   Simple Question:

   1.) How many morphisms are there in ?

   ( Or equivalent: What is $|\Delta [m]_n |$ ? )
   

   2.) Is there a research field in combinatorics that is concerned with monotonic integer maps from to (Just in case I have another ’combinatorical’ question concerning )

2. • CommentRowNumber2.
   • CommentAuthorTodd_Trimble
   • CommentTimeMar 4th 2012
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexMirco, there are a number of classical ways of computing this number. Just so I don't get confused, I'll let $[n]$ denote the ordinal with $n$ elements. You can make the translation if your convention differs. We are trying to count the number of morphisms = order-preserving maps $[n] \to [m]$. The most straightforward way, and a clever method if you know it or happen to think of it, is to imagine having $n$ balls and $m-1$ rods. The balls represent elements of the domain. Now suppose given an order-preserving function $f: [n] \to [m]$. For each $i$ such that $1 \leq i \lt m$, you place a rod after the last element in the union of $f^{-1}(j)$ over all $j \leq i$. The ordered array of balls and rods completely specifies $f$. Since there are $\binom{n+m-1}{n}$ choices of where the $n$ balls sit in this array of $n+m-1$ objects, that's the number in $\hom([n], [m])$. Although I have seen this method before, I didn't remember exactly how it went, and I had to reconstruct it only after I used a more circuitous and elaborate way of calculating it. My method was like this: first count the number of injective maps from $[n]$ to $[m]$; that's just $\binom{m}{n}$. Next, there's a nice trick for calculating the number of surjections: the ordinal category is opposite to the category of finite intervals (a finite interval is by definition a nonempty ordinal and an interval map is a map which preserves order and top and bottom), where the ordinal $[n]$ in $\Delta^{op}$ corresponds to the interval with $n+1$ elements. I can explain this if you like. Anyway, the number of surjections in $\Delta$ from $[n]$ to $[m]$ is the number of injective interval maps from $[m+1]$ to $[n+1]$, and you can convince yourself that this is $\binom{n-1}{m-1}$. Okay, now apply the image factorization: each $f: [n] \to [m]$ factors as a surjective followed by an injective. Let $j$ be the number of elements in the image. We see now that the total number of possibilities is $$\array{ \sum_j Surj([n], [j]) \cdot Inj([j], [m]) & = & \sum_j \binom{n-1}{j-1}\binom{m}{j} \\ & = & \sum_j \binom{n-1}{n-j}\binom{m}{j} \\ & = & \binom{n+m-1}{n} }$$ where the last equation is an instance of a convolution identity which can be given a bijective proof. I don't know what you'd call this area, except that it's a subarea of enumerative combinatorics. There are lots of well-known techniques here. A good introduction is Richard Stanley's book, or Concrete Mathematics by Graham, Knuth, and Patashnik.

   Mirco, there are a number of classical ways of computing this number. Just so I don’t get confused, I’ll let denote the ordinal with elements. You can make the translation if your convention differs. We are trying to count the number of morphisms = order-preserving maps .

   The most straightforward way, and a clever method if you know it or happen to think of it, is to imagine having balls and rods. The balls represent elements of the domain. Now suppose given an order-preserving function . For each such that , you place a rod after the last element in the union of over all . The ordered array of balls and rods completely specifies . Since there are choices of where the balls sit in this array of objects, that’s the number in .

   Although I have seen this method before, I didn’t remember exactly how it went, and I had to reconstruct it only after I used a more circuitous and elaborate way of calculating it. My method was like this: first count the number of injective maps from to ; that’s just . Next, there’s a nice trick for calculating the number of surjections: the ordinal category is opposite to the category of finite intervals (a finite interval is by definition a nonempty ordinal and an interval map is a map which preserves order and top and bottom), where the ordinal in corresponds to the interval with elements. I can explain this if you like. Anyway, the number of surjections in from to is the number of injective interval maps from to , and you can convince yourself that this is .

   Okay, now apply the image factorization: each factors as a surjective followed by an injective. Let be the number of elements in the image. We see now that the total number of possibilities is

   where the last equation is an instance of a convolution identity which can be given a bijective proof.

   I don’t know what you’d call this area, except that it’s a subarea of enumerative combinatorics. There are lots of well-known techniques here. A good introduction is Richard Stanley’s book, or Concrete Mathematics by Graham, Knuth, and Patashnik.

3. • CommentRowNumber3.
   • CommentAuthorMirco Richter
   • CommentTimeMar 4th 2012
   • PermaLink
   Author: Mirco Richter
   Format: MarkdownItexThanks for the great answer. I have to go through it tomorrow. I let you know when I'm done ...

   Thanks for the great answer. I have to go through it tomorrow. I let you know when I’m done …

4. • CommentRowNumber4.
   • CommentAuthorMirco Richter
   • CommentTimeMar 5th 2012
   • (edited Mar 5th 2012)
   • PermaLink
   Author: Mirco Richter
   Format: MarkdownItexOk, I walked through your proof and tweeking it to the convention $[n] = \lbrace 0 \rightarrow 1 \rightarrow \cdots \rightarrow n \rbrace$ for any $[n] \in \Delta$ we get $\binom{m+n+1}{n+1 }= \binom{m+n+1}{m}$ for the number of (monotonic) maps $f: [n] \rightarrow [m]$. The last identity in your proof is known as Vandermonde's identity. So finally we have $#(\Delta[m]_n) = \binom{m+n+1}{m}$. (This last result should be put into the nLab entry on the representables $\Delta[m]$, since it is of particular use for example in explicit constructions like $\mathbb{Z}(\Delta[m])$, where it directly gives $\mathbb{Z}(\Delta[m])_n \simeq \oplus^{\binom{m+n+1}{m}} \mathbb{Z}$.) Right?

   Ok, I walked through your proof and tweeking it to the convention

   for any we get for the number of (monotonic) maps . The last identity in your proof is known as Vandermonde’s identity.

   So finally we have . (This last result should be put into the nLab entry on the representables , since it is of particular use for example in explicit constructions like , where it directly gives .) Right?

5. • CommentRowNumber5.
   • CommentAuthorTodd_Trimble
   • CommentTimeMar 5th 2012
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItex> The last identity in your proof is known as Vandermonde's identity. Yes, I know -- it's a well-known identity. :-) Please feel free to put whatever you find useful into the nLab!

   The last identity in your proof is known as Vandermonde’s identity.

   Yes, I know – it’s a well-known identity. :-)

   Please feel free to put whatever you find useful into the nLab!