Last week, Abdullahi Umar, a Nigerian mathematician working in Oman, visited me in London on his way home from a visit to St Andrews. He works in semigroup theory and has obtained some beautiful results on counting the orders, and numbers of nilpotent elements, in some inverse semigroups of partial bijections on a finite set. Among these are the factorials, binomial coefficients, Stirling, Bell, Catalan, Schröder and Lah numbers.
As it happens, I am in the final stages of writing a book which will be a gentle introduction to enumerative combinatorics; many of these sequences of numbers will occur in the book. So, with his permission, I am going to include some of these results in the book.
However, the basic numbers in this game, the total numbers of partial bijections on an n-element set, are somewhat mysterious; there is no known closed formula for these numbers, and they do not agree with any familiar series from any other part of combinatorics.
Here are the details. To count bijections between k-sets, we first choose two k-sets (there are nCk choices for each, so the square of this number of pairs of such sets – I use this notation because I don’t know a simple way to produce the standard notation for binomial coefficients in HTML), and then choose a bijection between them (there are k! bijections); multiply, and then sum over k. The first few numbers in this sequence are 1, 2, 7, 34, 209, 1546, 13327, . . . This is sequence number A002720 in the On-Line Encyclopedia of Integer Sequences, an indispensible resource for this kind of work, maintained by Neil Sloane.
I began to wonder about the existence of a linear analogue of the formula. This would count the number of partial bijections between subspaces of a finite vector space. I soon found a remarkable fact:
The number of linear bijections between subspaces of a finite vector space is equal to the number of linear maps on the space.
If the space is n-dimensional over a field of order q, the number is qn2.
This result certainly does not hold for the case of sets. The numbers of mappings from a set of size n to itself is simply nn; the sequence begins 1, 1, 4, 27, 256, 3125, 46656, . . .
The proof is remarkably simple. We show that the numbers of transformations of each kind of given rank k are equal. We use the preliminary lemma that the number of complements to a k-dimensional subspace of the n-dimensional vector space V is qk(n-k). The crucial fact is that this formula is unchanged when k is replaced by n-k.
Count pairs consisting of a linear bijection T between k-dimensional subspaces, and a linear map S on V extending T. For each T, to extend it we must choose a complement for the domain of T and map it to zero. For each S, we must choose a complement to the (n-k)-dimensional null space of S and restrict S to this subspace. By our above remark, the number of pairs with a given T is equal to the number of pairs with a given S; so the numbers of Ts and Ss are equal.
Now the point of this post is:
Have you seen this result before?
I would be very interested to hear about it if you have!