Not signed in (Sign In)

## Not signed in

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

• Sign in using OpenID

## Discussion Tag Cloud

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

• CommentRowNumber1.
• CommentAuthorMirco Richter
• CommentTimeMar 4th 2012
• (edited Mar 4th 2012)

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

• CommentRowNumber2.
• CommentAuthorTodd_Trimble
• CommentTimeMar 4th 2012

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.

• CommentRowNumber3.
• CommentAuthorMirco Richter
• CommentTimeMar 4th 2012

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

• CommentRowNumber4.
• CommentAuthorMirco Richter
• CommentTimeMar 5th 2012
• (edited Mar 5th 2012)

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?

• CommentRowNumber5.
• CommentAuthorTodd_Trimble
• CommentTimeMar 5th 2012

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!