Counting the simplex category

Posted byJoe MoellerPosted inTopology

I don’t often think about combinatorics, but when I was on a plane recently (coming back from the Netherlands), I started thinking about a question I’ve just kept in the back of my mind for a few years. You can read about the simplex category here. In this blog post I’ll go through the exact thought process I went through on the plane.

\Delta is the category of finite nonempty totally ordered sets and monotone functions. Dropping the nonempty condition yields a category denoted \Delta_a, called the augmented simplex category. This difference isn’t what I want to talk about now. I want to figure out how big the category is. This stuff is well-known, but I wanted to see what I could figure out without help.

With the definition I gave above, the objects form a proper class, but a skeleton would have countably many objects. In particular, a standard skeleton to consider has objects n := [0< \dots <n]. This notation has the downside that n has cardinality n+1, so I’ll be using n := [0< \dots <n-1] and 0 = \emptyset. I’ll denote the size of the hom-sets by |Hom(m, n)| = (m \to n).

Some values that are immediately clear are

(m \to 0) = 0,
(0 \to n) = 1,
(m \to 1) = 1,
(1 \to n) = n.

Now let’s try just listing some of these hom-sets. I have to have a way to write this down, and I don’t know how to do tables in WordPress well, so excuse the following clunkiness. Each row represents an order preserving function. each column is an input. Since I’m thinking specifically of the sets \{0, \dots, n\}, the first column is the input 0, the second column is the input 1, etc. Each entry is the output value of that row’s function at that column’s input value. I hope this is clear.

Here is the list of functions for (2 \to 3):

0 0
0 1
0 2
1 1
1 2
2 2

which has 6 rows, so (2 \to 3) = 6. Here is the list of functions for (3 \to 2):

0 0 0
0 0 1
0 1 1
1 1 1

which has 4 rows, so (3 \to 2) = 4. Listing these feels very much like listing binary (or base n) numbers, but with the slight change that when you increase a place value, you have to start all the following places at that new value, rather than starting them all out at 0.

I’ll just do a couple more to drive home the point. Here is the list of functions for (3 \to 4):

0 0 0
0 0 1
0 0 2
0 0 3
0 1 1
0 1 2
0 1 3
0 2 2
0 2 3
0 3 3
1 1 1
1 1 2
1 1 3
1 2 2
1 2 3
1 3 3
2 2 2
2 2 3
2 3 3
3 3 3

which has 20 rows, so (3 \to 4) = 20. Last one: here is the list of functions for (4 \to 3):

0 0 0 0
0 0 0 1
0 0 0 2
0 0 1 1
0 0 1 2
0 0 2 2
0 1 1 1
0 1 1 2
0 1 2 2
0 2 2 2
1 1 1 1
1 1 1 2
1 1 2 2
1 2 2 2
2 2 2 2

which has 15 rows, so (4 \to 3) = 15.

Note that we’ve only computed values of (m \to n) for consecutive m and n, but any pair of natural numbers will have a hom-set. Now we’ll try to count these things in a smarter way.

We have enough data to start looking at and try to find some patterns. If you fix the value of the first input, the choices leftover look like some hom-set but with smaller numbers. For instance, in (3 \to 4), if you fix f(0) = 1 then the remaining choices look like (2 \to 3). Look at it like we are partitioning the table by the value in the first column, and each part then looks like some other table of order preserving functions, but with one less input value. The output values change too, but not uniformly. Each part has one less output value than the one above it. We make a slight conceptual leap and get the recursive formula:

(m \to n) = \sum_{i=1}^n (m-1 \to i)

We’re basically summing over the parts of the partitions. Now our job is to find a closed form for this. As a warm-up, we can recover the values of (m \to 1) and (1 \to n) if we assume the recursive formula and the base values (m \to 0) = 0 and (0 \to n) = 1:

(m \to 1) = \sum_{i=1}^1 (m-1 \to i)
\quad = (m-1 \to 1)
\dots = (0 \to 1) = 1

and

(1 \to n) = \sum_{i=1}^n (0 \to i)
\quad = \sum_{i=1}^n 1= n.

It’s interesting that (m \to 0) doesn’t get used in either. We have enough to work with to just calculate some stuff.

(m \to 2) = \sum_{i=1}^2 (m-1 \to i)
= (m-1 \to 2) + (m-1 \to 1)
=(m-1 \to 2) + 1
\dots = (0 \to 2) + m = m + 1,

(2 \to n) = \sum_{i=1}^n (1 \to i)
= \sum_{i=1}^n i = \frac{n(n+1)}{2},

(3 \to n) = \sum_{i=1}^n (2 \to i)
= \sum_{i_1=1}^n \sum_{i_2=1}^{i_1} i_2,

(4 \to n) = \sum_{i=1}^n (3 \to i)
= \sum_{i_1=1}^n \sum_{i_2=1}^{i_1} \sum_{i_3=1}^{i_2} i_3
= \sum_{i_1=1}^n \sum_{i_2=1}^{i_1} \sum_{i_3=1}^{i_2} \sum_{i_4=1}^{i_3} 1,

(m \to n) = \sum_{i_1=1}^n \sum_{i_2=1}^{i_1} \dots \sum_{i_m=1}^{i_{m-1}} 1

So that’s it. We found a closed form for the number of maps in \Delta between any two objects. After I got off the plane, I checked nlab, and it says that (m \to n) = \binom{n+m-1}{m}, but I’m not sure how to get there from here.

Let’s go back to the recursive formula and mess around with it more:

(m \to n) = \sum_{i=1}^n (m-1\to i)
= (m-1 \to n) + \sum_{i=1}^{n-1} (m-1\to i)
= (m-1 \to n) + (m \to n-1)

Weird! I don’t know what it means though. It looks like this recursive formula for binomial coefficients \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}, but not exactly.

Published by Joe Moeller

Mathematician

Leave a comment