Unordered tuples and type algebra

Posted on August 24, 2012 by Brent

At Hac Phi a few weekends ago (which, by the way, was awesome), Dan Doel told me about a certain curiosity in type algebra, and we ended up working out a bunch more details together with Gershom Bazerman, Scott Walck, and probably a couple others I’m forgetting. I decided to write up what we discovered. I have no idea what (if any) of this is really novel, but it was new to me at least.

The Setup

I’ll assume you’re already familiar with the basic ideas of the algebra of types— $0$ represents the void type, $1$ represents the unit type, sum is tagged union, product is (ordered) pairing, and so on.

Given a type $T$ , since product represents pairing, we can write $T^n$ to represent ordered $n$ -tuples of $T$ values. Well, how about unordered $n$ -tuples of $T$ values? Since there are $n!$ possible ways to order $n$ values, it seems that perhaps we could somehow divide by $n!$ to "quotient out" by the symmetries we want to disregard: $T^n/n!$ .

If you’ve never seen this sort of thing before it is certainly not at all obvious that this makes any sense! But bear with me for a minute. At the very least, we can say that if this is to make sense we ought to be able to use these sorts of type expressions to calculate the number of inhabitants of a finite type. So, let’s try it. For now let’s take $T$ = Bool = $2$ . I’ll draw the elements of Bool as and .

There are clearly four different ordered pairs of Bool:

$T^n$ is supposed to represent ordered $n$ -tuples of $T$ , and indeed, $2^2 = 4$ . How about unordered pairs? Since we don’t care about the order I’ll just choose to canonically sort all the $T$ s to the front, followed by all the $F$ s. It’s not hard to see that there are three unordered pairs of Bool:

(To distinguish them from ordered tuples, I’ll draw unordered tuples as above, with the elements slightly separated and a gray circle drawn round them.)

However, when we substitute $T = n = 2$ into $T^n/n!$ , we get not $3$ , but $(2^2)/2 = 2$ . What gives?

The problem

The problem is that $T^n/n!$ is only correct if all the values in the tuples are distinct. Then we overcount each unordered tuple by exactly a factor of $n!$ —namely, all the $n!$ many permutations of the tuple, each of which is distinct as an ordered tuple. However, when some of the tuples have repeated elements, there can be fewer than $n!$ distinct ordered variants of a given unordered tuple. For example, the unordered tuple has only $3$ (rather than $3! = 6$ ) ordered variants, namely

because the two ‘s are identical.

(As a small aside, when working in the theory of combinatorial species one is concerned not with actual data structures but with data structure shapes full of distinct labels—and the fact that the labels are distinct means that $T^n/n!$ is (in some sense) actually the correct way to talk about unordered tuples within the theory of species. More on this in another post, perhaps.)

If $T^n/n!$ is not the correct expression for unordered tuples, what is? In fact, Dan started off this whole thing by telling me the answer to this question—but he didn’t understand why it is the answer; we then proceeded to figure it out. For the purposes of pedagogy I’ll reverse the process, working up from first principles to arrive at the answer.

Counting unordered tuples

The first order of business is to count unordered tuples. Given a set $T$ , how many unordered $n$ -tuples are there with elements drawn from $T$ (where repetition is allowed)? Again, since the order doesn’t matter, we can canonically sort the elements of $T$ with all copies of the first element first, then all copies of the second element, and so on. For example, here is an unordered $8$ -tuple with elements drawn from $T = 4 = \{$ , , , $\}$ :

Now imagine placing "dividers" to indicate the places where changes to , changes to , and so on:

(Note how there are two dividers between the last and the first , indicating that there are no occurrences of .) In fact, given that the elements are canonically sorted, it is unnecessary to specify their actual identities:

So, we can see that unordered $8$ -tuples with elements from $T = 4$ correspond bijectively to such arrangements of eight dots and three dividers. In general, unordered $n$ -tuples are in bijection with arrangements of $n$ dots and $|T|-1$ dividers, and there are as many such arrangements as ways to choose the positions of the $|T|-1$ dividers from among the $n+|T|-1$ total objects, that is,

$\displaystyle \binom{n+|T|-1}{|T|-1}$

(As an aside, this is the same as asking for the number of ways to place $n$ indistinguishable balls in $|T|$ distinguishable boxes—the balls in box $i$ indicate the multiplicity of element $i$ in the unordered $n$ -tuple. This is #4 in Gian-Carlo Rota’s "twelvefold way", and is discussed on page 15 of Richard Stanley’s Enumerative Combinatorics, Volume I. See also this blog post I wrote explaining this and related ideas).

So what?

And now for a little algebra:

$\displaystyle \begin{array}{cl} & \displaystyle \binom{n+|T|-1}{|T|-1} \\ & \\ = & \displaystyle \frac{(n+|T|-1)!}{n!(|T|-1)!} \\ & \\ = & \displaystyle \frac{(n+|T|-1)(n+|T|-2) \cdots (|T|)}{n!} \\ & \\ = & \displaystyle \frac{|T|(|T|+1)(|T|+2) \cdots (|T| + n-1)}{n!}\end{array}$

The expression on top of the fraction is known as a rising factorial and can be abbreviated $|T|^{\overline{n}}$ . (In general, $x^{\overline{n}} = x(x+1)(x+2) \dots (x+n-1)$ , so $1^{\overline{n}} = n!$ .) In the end, we have discovered that the number of unordered $n$ -tuples of $T$ is $|T|^{\overline{n}}/n!$ , which looks surprisingly similar to the naïve but incorrect $T^n / n!$ . In fact, the similarity is no coincidence, and there are good reasons for using a notation for rising factorial similar to the notation for normal powers, as we shall soon see.

And indeed, the correct type expression for unordered $n$ -tuples of values from $T$ is $T^{\overline{n}} / n! = T(T+1)(T+2) \dots (T+(n-1))/n!$ . This means that if we consider the set of ordered $n$ -tuples where the first element is drawn from $T$ , the second element from $T$ plus some extra distinguished element, the third from $T$ plus two extra elements, and so on, there will be exactly $n!$ of them for every unordered $n$ -tuple with elements drawn from $T$ . (In fact, we would even expect there to be some nice function from these "extended $n$ -tuples" to unordered $n$ -tuples such that the preimage of every unordered $n$ -tuple is a set of size exactly $n!$ —just because combinatorics usually works out like that. Finding such a correspondence is left as an exercise for the reader.)

A detour

Before we get back to talking about $T^{\overline{n}}/n!$ , a slight detour. Consider the variant type expression $T^{\underline{n}}/n!$ , where $x^{\underline{n}} = x(x-1)(x-2) \dots (x-n+1)$ is a falling factorial. What (if anything) does it represent?

Subtraction of types is problematic in general (without resorting to virtual species), but in this case we can interpret $T(T-1)(T-2) \dots$ as an ordered $n$ -tuple with no duplicate values. We can choose any element of $T$ to go first, then any but the first element to go second, then any but the first two, and so on. This can in fact be made rigorous from the perspective of types, without involving virtual species—see Dan Piponi’s blog post on the subject.

Infinite sums and discrete calculus

And now for some fun. If we sum $T^{\underline{n}}/n!$ over all $n$ , it ought to represent the type of unordered tuples with distinct values of any length—that is, the type of sets over $T$ .

$\displaystyle S(T) = 1 + T + \frac{T^{\underline{2}}}{2!} + \frac{T^{\underline{3}}}{3!} + \dots$

Can we find a more compact representation for $S(T)$ ?

Consider the forward difference operator $\Delta$ , defined by

$\displaystyle \Delta f(x) = f(x+1) - f(x)$

This is a discrete analogue of the familiar (continuous) differentiation operator from calculus. (For a good introduction to discrete calculus, see Graham et al.‘s Concrete Mathematics, one of my favorite math/CS books ever. See also the Wikipedia page on finite differences.) For our purposes we simply note that

$\displaystyle \Delta x^{\underline{n}} = n x^{\underline{n-1}}$

(proving this is not hard, and is left as an exercise). This is what justifies the notation for falling factorial: it is in some sense a discrete analogue of exponentiation!

The reason to bring $\Delta$ into the picture is that given the above identity for $\Delta$ applied to falling factorials, it is not hard to see that $S(T)$ is its own finite difference:

$\displaystyle \Delta S(T) = S(T)$

Expanding, we get $S(T+1) - S(T) = S(T)$ and hence $S(T+1) = 2 S(T)$ . (Yes, I know, there’s that pesky subtraction of types again; in the time-honored tradition of combinatorics we’ll simply pretend it makes sense and trust there is a way to make it more formal!) Solving this recurrence together with the initial condition $S(0) = 1$ yields

$\displaystyle S(T) = 2^T$

which we can interpret as the space of functions from $T$ to Bool—that is, the type of sets over $T$ , just like it should be! (Note that replacing falling factorial with exponentiation yields something which is its own derivative, with a solution of $e^T$ —which indeed represents the species of sets, though it’s harder to see what $e$ has to do with anything.)

Enough with the detour. What if we sum over $T^{\overline{n}}/n!$ ?

$\displaystyle M(T) = 1 + T + \frac{T^{\overline{2}}}{2!} + \frac{T^{\overline{3}}}{3!} + \dots$

There’s a backward difference operator, $\nabla f(x) = f(x) - f(x-1)$ , with the property that

$\displaystyle \nabla x^{\overline{n}} = n x^{\overline{n-1}}$

Hence $\nabla M(T) = M(T)$ , i.e. $M(T) - M(T-1) = M(T)$ , but here I am a bit stuck. Trying to solve this in a similar manner as before yields $M(T-1) = 0$ , which seems bogus. $0$ is certainly not a solution, since $M(0) = 1$ . I think in this case we are actually not justified in subtracting $M(T)$ from both sides, though I’d be hard-pressed to explain exactly why.

Intuitively, $M(T)$ ought to represent unordered tuples of $T$ of any length—that is, the type of multisets over $T$ . This is isomorphic to the space of functions $T \to \mathbb{N}$ , specifying the multiplicity of each element. I claim that $\mathbb{N}^T$ is in fact a solution to the above equation—though I don’t really know how to derive it (or even what it really means).

$\displaystyle \begin{array}{cl} & \displaystyle \mathbb{N}^T - \mathbb{N}^{T-1} \\ & \\ \cong & \displaystyle \mathbb{N}^{T-1}(\mathbb{N} - 1) \\ & \\ \cong & \displaystyle \mathbb{N}^{T-1} \mathbb{N} \\ & \\ \cong & \displaystyle \mathbb{N}^T \end{array}$

The middle step notes that if you take one element away from the natural numbers, you are left with something which is still isomorphic to the natural numbers. I believe the above can all be made perfectly rigorous, but this blog post is already much too long as it is.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

This entry was posted in combinatorics and tagged algebra, discrete calculus, tuples, types, unordered. Bookmark the permalink.

7 Responses to Unordered tuples and type algebra

Omar Abuzzahab says:

August 24, 2012 at 11:33 pm

I think the problem is that equation for M(T) involving an infinite sum cannot be interpreted as a power series, nor can the result we’re trying to prove – that M(T)=N^T – be interpreted combinatorially. (For S(T) the corresponding equation and results can be).

Lets lean on a simplified analogy: (2+4) / 6 equals 1, which is in some sense a statement purely about integers: the only operations in the statement are + and division, and the division only appears in an instance where you don’t leave the ring of integers. But we want to derive this statement by temporarily leaving the ring of integers: (2+4)/6 = 2/6 + 4/6 = 1. The middle expression steps outside the integers into the rationals. Our demand for justification is satisfied since the steps are legal steps for rational numbers. We turn around at the end and say that we started and ended with integer expressions, so we’ve discovered a true equality about integers too.

With both species and types you can’t make sense of subtraction. If you want to subtract them – not for the backwards difference even, just for the rising factorial – then the only thing to do is to “step outside” and end up in the ring of power series instead. But once there you meet rules you are stuck with, like not being able to take infinite sums without restriction.

Types (unlike both species and power series) somehow don’t have this problem with infinite sums though. Our infinite sum of types is just taking infinite disjoint unions of sets (in my mind at least, I’m hazy on how type expressions are formalized.) So the venn diagram of “stepping outside” types into power series is different, one sort of expressions doesn’t subsume the other! I don’t think I’ve ever noticed that.

Reply
Chris U. says:

August 25, 2012 at 11:16 pm

I think I can derive the N^T solution, but this is after the fact..so who knows.

M(T) – M(T-1) = M(T)
Add M(T-1) to both sides.
M(T) = M(T) + M(T-1) which we can use as a recursion to build M(T).
M(0) = 1
M(1) = M(1) + 1 ~=~ N = N + 1 (I.e. e in M(1) looks like S (S (S… (S O) )
M(2) = M(2) + M(1) ~=~ (i.e. e in M(2) looks like S2 (S2…(S2 (S (S ..(S O) )

So for any finite type its easy..not sure if this actually lets you define M (n) for non finite types..but the identification of exponent and function makes it least sort of obvious.

Hmm..yeah I think you have to handwave that because even for N the recusion fails to define it usefully. M(N) = M(N) + M(N-1) = M(N) + M(N) is true but not ?constructive?/?constraining? (not sure what the right word here is.

Though maybe some sort of argument by continuity on ordinals or something similar could work?

Reply
Pingback: Creating documents with embedded diagrams | blog :: Brent -> [String]
Dan Piponi says:

August 30, 2012 at 12:56 pm

There’s a significant difference between N^T and the sum of rising factorials you give. The sum gives the finite multisets but N^T allows infinite multisets. For example const 1 is an element of N^T but isn’t an element of any of the terms in the sum.

Anyway, it’s cool you’re thinking about these things. I think there’s an enormous area of combinatorial type theory waiting to be explored.

If you haven’t already, check out “umbral calculus”. It’s all about families of polynomials with associated derivative-like operators such as rising factorials with backward differences. Many theorems about ordinary calculus carry over to umbral calculus and I think many of these theorems get type interpretations.

And note also that Conor McBride’s Jokers and Clowns papers is actually about finite differences, though he doesn’t say it.

Reply
Dan Piponi says:

August 30, 2012 at 1:15 pm

So suppose you have a bunch of polynomials with associated derivative-like operator. You can also define an associated exponential-like operator from the power-like series and it will also be a fixed point of the derivative-like operator.

For ordinary monomials x^n you get e^x. For falling factorials you get 2^x. For rising factorials you get N^x.

Reply
Theo says:

September 3, 2012 at 4:34 pm

I am enjoying this type of discussion, and would like to contribute some links. Firstly, these two articles touch on much the same stuff
http://blog.sigfpe.com/2007/09/type-of-distinct-pairs.html
http://blog.sigfpe.com/2007/09/tries-and-their-derivatives_08.html

Reply
Benjamin Braun says:

September 26, 2012 at 8:45 pm

Nice post!

The sum of the first $k + 1$ terms of $M(T)$ is $(T+1)^{\overline{k}/k!$.

Hence $M(T) = (T+1)^{\overline{T}}/T!$.

Proof: Consider adding a “spacer” element to $T$, and then compute the number of unordered $T$-tuples of these $T+1$ elements, that is, $(T+1)^{\overline{T}}/T!$.

Reply