The Math Less Traveled

A few words about PWW #33: subset permutations

Posted on August 20, 2021 by Brent

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.

Posted in combinatorics, posts without words | Tagged Haskell, path, permutation, subset | 6 Comments

Post without words #33

Posted on August 18, 2021 by Brent

Posted in combinatorics, posts without words | Tagged path, permutation, subset | 4 Comments

Happy tau day!

Posted on June 28, 2021 by Brent

Happy Tau Day! The Tau Manifesto by Michael Hartl is now available in print, if you’re in the market for a particularly nerdy coffee table book and conversation starter:

I also wrote about Tau Day ten years ago; see that post for more links! Using $\tau$ we can make the most beautiful equation in the world even more beautiful:

$e^{i \tau} = 1 + 0i$

Please enjoy eating two pi(e)s today. I’ll be back soon with some solutions to the parallelogram area challenge!

Posted in famous numbers, links | Tagged day, pi, tau | 1 Comment

Challenge: area of a parallelogram

Posted on June 24, 2021 by Brent

And now for something completely different!¹

Suppose we have a parallelogram with one corner at the origin, and two adjacent corners at coordinates $(a,b)$ and $(c,d)$ . What is the area of the parallelogram?

There are probably many different ways to derive the answer; post your ideas in the comments!

…or is it?↩

Posted in challenges, geometry | Tagged area, parallelogram | 18 Comments

Post without words #32

Posted on June 8, 2021 by Brent

Posted in posts without words | Tagged coloring, grid, lattice, square | 8 Comments

The Natural Number Game

Posted on May 25, 2021 by Brent

Hello everyone! It has been quite a while since I have written anything here—my last post was in March 2020, and since then I have been overwhelmed dealing with online and hybrid teaching, plus a newborn (who is now almost 5 months old and very cute):

But the spring semester is finally over, and I have a sabbatical in the fall, so I plan to do a bunch more writing! I have several ideas of things to come (feel free to send me suggestions as well), but to start things out for today I just have a fun link:

The Natural Number Game

The idea is to use a computer proof assistant to formally prove a lot of basic facts about arithmetic. That is, you get to build proofs using a special precise notation, and the computer will automatically check whether your proof is correct. But the whole thing is organized like a game, with a tutorial, levels that build on each other and introduce new ideas and techniques just before you need them, etc. It’s a lot of fun and honestly kind of addicting.

There is very little background needed other than some capability for abstract thinking. Things start out quite easy and progress slowly, though things become quite challenging by the time you make it all the way to the end.

Posted in challenges, computation, proof | Tagged computer, game, Lean, natural, number, proof | 6 Comments

An exploration of forward differences for bored elementary school students

Posted on March 22, 2020 by Brent

Last week I made a mathematics worksheet for my 8-year-old son, whose school is closed due to the coronavirus pandemic. I’m republishing it here so others can use it for similar purposes.

Figurate numbers and forward differences

There are lots of further directions this could be taken but I’ll leave that to you and your kids. I tried to create something that was conducive to open-ended exploration rather than something that had a single particular goal in mind.

Ways to prove a bijection

Posted on March 17, 2020 by Brent

You have a function $f : A \to B$ and want to prove it is a bijection. What can you do?

By the book

A bijection is defined as a function which is both one-to-one and onto. So prove that $f$ is one-to-one, and prove that it is onto.

This is straightforward, and it’s what I would expect the students in my Discrete Math class to do, but in my experience it’s actually not used all that much. One of the following methods usually ends up being easier in practice.

By size

If $A$ and $B$ are finite and have the same size, it’s enough to prove either that $f$ is one-to-one, or that $f$ is onto. A one-to-one function between two finite sets of the same size must also be onto, and vice versa. (Of course, if $A$ and $B$ don’t have the same size, then there can’t possibly be a bijection between them in the first place.)

Intuitively, this makes sense: on the one hand, in order for $f$ to be onto, it “can’t afford” to send multiple elements of $A$ to the same element of $B$ , because then it won’t have enough to cover every element of $B$ . So it must be one-to-one. Likewise, in order to be one-to-one, it can’t afford to miss any elements of $B$ , because then the elements of $A$ have to “squeeze” into fewer elements of $B$ , and some of them are bound to end up mapping to the same element of $B$ . So it must be onto.

However, this is actually kind of tricky to formally prove! Note that the definition of “ $A$ and $B$ have the same size” is that there exists some bijection $g : A \to B$ . A proof has to start with a one-to-one (or onto) function $f$ , and some completely unrelated bijection $g$ , and somehow prove that $f$ is onto (or one-to-one). Also, a valid proof must somehow account for the fact that this becomes false when $A$ and $B$ are infinite: a one-to-one function between two infinite sets of the same size need not be onto, or vice versa; we saw several examples in my previous post, such as $f : \mathbb{N} \to \mathbb{N}$ defined by $f(n) = 2n$ . Although tricky to come up with, the proof is cute and not too hard to understand once you see it; I think I may write about it in another post!

Note that we can even relax the condition on sizes a bit further: for example, it’s enough to prove that $f$ is one-to-one, and the finite size of $A$ is greater than or equal to the finite size of $B$ . The point is that $f$ being a one-to-one function implies that the size of $A$ is less than or equal to the size of $B$ , so in fact they have equal sizes.

By inverse

One can also prove that $f : A \to B$ is a bijection by showing that it has an inverse: a function $g : B \to A$ such that $g(f(a)) = a$ and $f(g(b)) = b$ for all $a \in A$ and $b \in B$ . As we saw in my last post, these facts imply that $f$ is one-to-one and onto, and hence a bijection. And it really is necessary to prove both $g(f(a)) = a$ and $f(g(b)) = b$ : if only one of these hold then $g$ is called a left or right inverse, respectively (more generally, a one-sided inverse), but $f$ needs to have a full-fledged two-sided inverse in order to be a bijection.

…unless $A$ and $B$ are of the same finite size! In that case, it’s enough to show the existence of a one-sided inverse—say, a function $g$ such that $g(f(a)) = a$ . Then $f$ is (say) a one-to-one function between finite equal-sized sets, hence it is also onto (and hence $g$ is actually a two-sided inverse).

We must be careful, however: sometimes the reason for constructing a bijection in the first place is in order to show that $A$ and $B$ have the same size! This kind of thing is common in combinatorics. In that case one really must show a two-sided inverse, even when $A$ and $B$ are finite; otherwise you end up assuming what you are trying to prove.

By mutual injection?

I’ll leave you with one more to ponder. Suppose $f : A \to B$ is one-to-one, and there is another function $g : B \to A$ which is also one-to-one. We don’t assume anything in particular about the relationship between $f$ and $g$ . Are $f$ and $g$ necessarily bijections?

Posted in logic, proof | Tagged bijection, finite, function, injection, invertible, one-to-one, onto, proof, surjection | 7 Comments

One-sided inverses, surjections, and injections

Posted on March 14, 2020 by Brent

Several commenters correctly answered the question from my previous post: if we have a function $f : A \to B$ and $g : B \to A$ such that $g(f(a)) = a$ for every $a \in A$ , then $f$ is not necessarily invertible. Here are a few counterexamples:

Commenter Buddha Buck came up with probably the simplest counterexample: let $A$ be a set with a single element, and $B$ a set with two elements. It does not even matter what the elements are! There’s only one possible function $g : B \to A$ , which sends both elements of $B$ to the single element of $A$ . No matter what $f$ does on that single element $a \in A$ (there are two choices, of course), $g(f(a)) = a$ . But clearly $f$ is not a bijection.
Another counterexample is from commenter designerspaces: let $f : \mathbb{N} \to \mathbb{Z}$ be the function that includes the natural numbers in the integers—that is, it acts as the identity on all the natural numbers (i.e. nonnegative integers) and is undefined on negative integers. $g : \mathbb{Z} \to \mathbb{N}$ can be the absolute value function. Then $g(f(n)) = |n| = n$ whenever $n$ is a natural number, but $f$ is not a bijection, since it doesn’t match up the negative integers with anything.

Unlike the previous example, in this case it is actually possible to make a bijection between $\mathbb{N}$ and $\mathbb{Z}$ , for example, the function that sends even $n$ to $n/2$ and odd $n$ to $-(n+1)/2$ .
Another simple example would be the function $f : \mathbb{N} \to \mathbb{N}$ defined by $f(n) = 2n$ . Then the function $g(n) = \lfloor n/2 \rfloor$ satisfies the condition, but $f$ is not a bijection, again, because it leaves out a bunch of elements.
Can you come up with an example $f : \mathbb{R} \to \mathbb{R}$ defined on the real numbers $\mathbb{R}$ (along with a corresponding $g$ )? Bonus points if your example function is continuous.

All these examples have something in common, namely, one or more elements of the codomain that are not “hit” by $f$ . Michael Paul Goldenberg noted this phenomenon in general. And in fact we can make this intuition precise.

Theorem. If $f : A \to B$ and $g : B \to A$ such that $g(f(a)) = a$ for all $a \in A$ , then $f$ is injective (one-to-one).

Proof. Suppose for some $a_1, a_2 \in A$ we have $f(a_1) = f(a_2)$ . Then applying $g$ to both sides of this equation yields $g(f(a_1)) = g(f(a_2))$ , but because $g(f(a)) = a$ for all $a \in A$ , this in turn means that $a_1 = a_2$ . Hence $f$ is injective.

Corollary. since bijections are exactly those functions which are both injective (one-to-one) and surjective (onto), any such function $f : A \to B$ which is not a bijection must not be surjective.

And what about the opposite case, when there are functions $f : A \to B$ and $g : B \to A$ such that $f(g(b)) = b$ for all $b \in B$ ? As you might guess, such functions are guaranteed to be surjective—can you see why?

Posted in logic | Tagged bijection, function, injection, invertible, one-to-one, onto, surjection | 1 Comment

Test your intuition: bijections

Posted on March 3, 2020 by Brent

Suppose we have sets $A$ and $B$ and a function $f : A \to B$ (that is, $f$ ’s domain is $A$ and its codomain is $B$ ). Suppose there is another function $g : B \to A$ such that $g(f(a)) = a$ for every $a \in A$ . Is $f$ necessarily a bijection? That is, does $f$ necessarily match up each element of $A$ with a unique element of $B$ and vice versa? Or put yet another way, is $f$ necessarily invertible?

If yes, prove it!
If no, provide a counterexample! For bonus points, what additional assumptions could we impose to make it true?

Posted in logic | Tagged bijection, function, intuition, invertible | 12 Comments

The Math Less Traveled

A few words about PWW #33: subset permutations

Post without words #33

Happy tau day!

Challenge: area of a parallelogram

Post without words #32

The Natural Number Game

An exploration of forward differences for bored elementary school students

Ways to prove a bijection

By the book

By size

By inverse

By mutual injection?

One-sided inverses, surjections, and injections

Test your intuition: bijections

Follow Blog via Email

Meta

Categories

Archives