A few words about PWW #33: subset permutations

My previous post showed four rows of diagrams, where the $n$ th row (counting from zero) has diagrams with $n+2$ dots. The diagrams in the $n$ th row depict all possible paths that

start at the top left dot,
end at the top right dot, and
never visit any dot more than once.

For a given diagram, we can choose which dots to visit (representing a subset of the dots), and we can visit the chosen dots in any order (a permutation). I will call the resulting things “subset permutations”, although I don’t know if there is some other more accepted term for them.

It’s not necessary to draw subset permutations as paths; it’s just one nice visual representation. If we number the dots from $1 \dots n$ (excluding the top two, which are uninteresting), each path corresponds precisely to a permutation of some subset of $\{1 \dots n\}$ . Like this:

I thought of this idea the other day—of counting the number of “subset permutations”—and wondered how many there are of each size. I half expected it to turn out to be a sequence of numbers that I already knew well, like the Catalan numbers or certain binomial coefficients or something like that. So I was surprised when it turned out to be a sequence of numbers I don’t think I have ever encountered before (although it has certainly been studied by others).

So, how many subset permutations are there of size $n$ ? Let’s call this number $\mathit{SP}_n$ . From my previous post we can see that starting with $\mathit{SP}_0 = 1$ , the first few values are $1, 2, 5, 16$ . (When I saw 1, 2, 5, I thought sure it was going to be the Catalan numbers—but then the next number was 16 instead of 14…) Can we compute these more generally without just listing them all and counting?

Well, to choose a particular subset permutation of size $n$ , we can first choose how big we want the subset to be, i.e. how many dots to visit, which could be zero, or $n$ , or anything in between. Once we choose to visit $k$ out of $n$ dots, then we have $n$ choices for which dot to visit first, then $(n-1)$ choices for which dot to visit second, all the way down to $(n-k+1)$ choices for the last dot (you should convince yourself that $(n-k+1)$ , not $(n-k)$ , is correct!). This is often notated

$\displaystyle {}_n P_k = n (n-1) (n-2) \dots (n-k+1) = \frac{n!}{(n-k)!}.$

So, in total then, $\mathit{SP}_n$ is the sum of ${}_n P_k$ over all possible $k$ , that is,

$\displaystyle \mathit{SP}_n = \sum_{0 \leq k \leq n} \frac{n!}{(n-k)!}.$

This is already better than just listing all the subset permutations and counting. For example, we can compute that

$\mathit{SP}_4 = 4!/4! + 4!/3! + 4!/2! + 4!/1! + 4!/0! = 1 + 4 + 12 + 24 + 24 = 65.$

And sure enough, if we list them all, we get 65 (you’ll just have to take my word that this is all of them, I suppose!):

However, with a little algebra, we can do even better! First, let’s write out the sum for $\mathit{SP}_n$ explicitly:

$\mathit{SP}_n = 1 + n + n(n-1) + n(n-1)(n-2) + \dots + n!$

If we factor $n$ out of all the terms after the initial $1$ , we get

$\mathit{SP}_n = 1 + n[1 + (n-1) + (n-1)(n-2) + \dots + (n-1)!] = 1 + n \mathit{SP}_{n-1}$

so the subset permutation numbers actually follow a very simple recurrence! To get the $n$ th subset permutation number, we just multiply the previous one by $n$ and add one.

$\begin{array}{rcl} \mathit{SP}_0 &=& 1 \\ \mathit{SP}_1 &=& 1 \cdot 1 + 1 = 2 \\ \mathit{SP}_2 &=& 2 \cdot 2 + 1 = 5 \\ \mathit{SP}_3 &=& 3 \cdot 5 + 1 = 16 \end{array}$

and sure enough, $\mathit{SP}_4 = 4 \cdot 16 + 1 = 65$ . We can now easily calculate the next few subset permutation numbers:

$1,2,5,16,65,326,1957,13700,109601,986410, \dots$

A commenter also wondered about the particular order in which I listed subset permutations in my previous post. The short, somewhat disappointing answer is “whatever order came out of the standard library functions I used”. However, there are definitely more interesting things to say about the ordering, and I think I’ll probably write about that in another post.

About Brent

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

View all posts by Brent →

6 Responses to A few words about PWW #33: subset permutations

Jacob Magnusson says:

August 20, 2021 at 2:33 pm

There’s an alternative derivation of the recurrence relation I like: If there are at least three vertices on a given path, then you have $n$ choices for the first step in the path. After making that first step, you have $\mathit{SP}_{n-1}$ ways to get to the final vertex. So, paths with at least three vertices contribute $n \cdot \mathit{SP}_{n-1}$ paths to the total. You also have the one path with just two vertices. Thus $\mathit{SP}_n = n \cdot \mathit{SP}_{n-1} + 1$ .
- Brent says:
  
  August 20, 2021 at 2:50 pm
  
  Ah, yes, that’s a nice way to think about it!
Naren Sundar says:

August 21, 2021 at 6:39 am

Would be interesting to ask how many of the graphs of SPn are planar.
- Naren Sundar says:
  
  August 21, 2021 at 6:40 am
  
  Or more generally count them by the number of crossings.
- Brent says:
  
  August 21, 2021 at 6:55 am
  
  I mean, they’re all planar, since they are all isomorphic to a path. But I guess you are referring specifically to whether these particular drawings have crossings? That does seem like an interesting question. I think they have crossings exactly when the permutations have descents. So there should be one planar drawing for each possible subset, corresponding to the permutation that is strictly increasing.
  - Brent says:
    
    August 21, 2021 at 6:57 am
    
    So in other words there are always 2^n planar drawings.