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.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).
    • CommentRowNumber1.
    • CommentAuthorMirco Richter
    • CommentTimeMar 4th 2012
    • (edited Mar 4th 2012)

    Simple Question:

    1.) How many morphisms f:[n][m]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][n] to [m][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][n] denote the ordinal with nn elements. You can make the translation if your convention differs. We are trying to count the number of morphisms = order-preserving maps [n][m][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 nn balls and m1m-1 rods. The balls represent elements of the domain. Now suppose given an order-preserving function f:[n][m]f: [n] \to [m]. For each ii such that 1i<m1 \leq i \lt m, you place a rod after the last element in the union of f 1(j)f^{-1}(j) over all jij \leq i. The ordered array of balls and rods completely specifies ff. Since there are (n+m1n)\binom{n+m-1}{n} choices of where the nn balls sit in this array of n+m1n+m-1 objects, that’s the number in hom([n],[m])\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][n] to [m][m]; that’s just (mn)\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][n] in Δ op\Delta^{op} corresponds to the interval with n+1n+1 elements. I can explain this if you like. Anyway, the number of surjections in Δ\Delta from [n][n] to [m][m] is the number of injective interval maps from [m+1][m+1] to [n+1][n+1], and you can convince yourself that this is (n1m1)\binom{n-1}{m-1}.

    Okay, now apply the image factorization: each f:[n][m]f: [n] \to [m] factors as a surjective followed by an injective. Let jj be the number of elements in the image. We see now that the total number of possibilities is

    jSurj([n],[j])Inj([j],[m]) = j(n1j1)(mj) = j(n1nj)(mj) = (n+m1n)\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]={01n}[n] = \lbrace 0 \rightarrow 1 \rightarrow \cdots \rightarrow n \rbrace

    for any [n]Δ[n] \in \Delta we get (m+n+1n+1)=(m+n+1m)\binom{m+n+1}{n+1 }= \binom{m+n+1}{m} for the number of (monotonic) maps f:[n][m]f: [n] \rightarrow [m]. The last identity in your proof is known as Vandermonde’s identity.

    So finally we have #(Δ[m] n)=(m+n+1m)#(\Delta[m]_n) = \binom{m+n+1}{m}. (This last result should be put into the nLab entry on the representables Δ[m]\Delta[m], since it is of particular use for example in explicit constructions like (Δ[m])\mathbb{Z}(\Delta[m]), where it directly gives (Δ[m]) n (m+n+1m)\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!