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 $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$)

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 $[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.

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

   $[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?

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!