A counting problem

I quite often get questions by email. Mostly I can’t answer them, but sometimes I can, and sometimes the answers might be of more general interest.

Suppose that we have m boxes and a supply of identical balls. In how many distinct ways can we place n balls in the boxes? This is a standard combinatorial problem: we are choosing boxes from the set of m to place the balls in, and doing this n times, where the order of choice is unimportant and selections may be repeated. The answer is the binomial coefficient (m+n−1 choose n).

What if the boxes as well as the balls are indistinguishable? Then we can arrange them in a row so that the numbers of balls per box are non-increasing; the answer is the number of partitions of n into at most m parts; this is another standard problem, and while there is no simple formula for the solution, at least it is at least polynomial on residue classes.

The question I was asked was a common generalisation of these two. Suppose that a permutation group G acts on the set of boxes. How many ways of putting the balls into boxes, if two arrangements related by an element of G are not distinguished?

There is a standard piece of technology to answer such questions, the Cycle Index Theorem (in its simplest form). Take indeterminates s1,…,sm. For each element g of the permutation group, form the monomial in which the exponent of the power of si is the number of cycles of length i in the cycle decomposition of g. Then sum these monomials over all gG, and divide by |G|, the order of G; the resulting polynomial is the cycle index of G, denoted Z(G).

Now suppose that we have a set F of “figures”, each with a non-negative integer “weight”. The set of figures may be infinite, but we assume that there are only finitely many figures of any given weight. So the figures are described by a polynomial or formal power series A(x), in which the coefficient of xn is the number of figures of weight n.

We are interested in decorating the elements of the set X on which G acts with figures, and counting such “configurations” up to the action of G. Such a configuration is a function from X to F; the group G acts on the set of functions in a natural way, and we want to count the number of orbits of G on functions whose total weight (the sum of the weights of its values is given. So there is another polynomial or formal power series B(x), in which the coefficient of xn is the number of G-orbits on functions of weight n.

Now the Cycle Index Theorem states that B(x) is obtained from the cycle index Z(G) by replacing si by A(xi) for i = 1,…m.

In our problem, we take a figure of weight i, for each non-negative integer i, to mean that there are i balls in the box to which that figure is attached. So a function is an allocation of balls to boxes, and its weight is the number of balls attached. The figure-counting series is given by A(x) = 1+x+x2+… = (1−x)−1. Applying the Cycle Index Theorem gives the configuration counting series B(x).

For example, let G be the trivial group, with cycle index s1m. Then the generating function for the original balls-in-boxes problem is (1−x)m. Applying the Negative Binomial Theorem gives the result with which I began.

Extensions are possible. For example, if there are r distinguishable colours of balls, then the figure-counting series is (1−x)r, or (if we wish to keep track of the number of balls of each colour) the product of (1−xi)−1 for i = 1,…,r.

There is another interpretation, close to my heart, which I will treat in somewhat less detail. This involves oligomorphic permutation groups, those for which the number of orbits on n-element subsets of the domain is finite for all n. The counting problem here is exactly the same as counting orbits on n-sets of the group S Wr G, the wreath product of an infinite symmetric group S with G. The domain is partitioned into m infinite sets, and we have symmetric groups acting independently on each of these; elements of G permute these blocks among themselves. Now an n-element set of the domain is specified, up to the action of the symmetric groups, by giving the cardinality of its intersection with each part; and we want to count the orbits of G on such m-tuples summing to n. So the orbit counting problem is identical with the original balls-in-boxes problem. Now a standard formula for counting orbits of a wreath product gives the answer, which turns out to be the same as the one obtained using the Cycle Index Theorem.

Posted in doing mathematics, exposition | Tagged , , | 1 Comment

A trip to Hull

Queen Victoria

At the end of last week I went to Hull. This is a place I hadn’t been to before, although it was City of Culture last year. I stayed overnight in the Hull Royal Hotel, where Queen Victoria (pictured above) had been an earlier guest. The hotel is so close to the station that, when you look out of the window at breakfast, you find yourself looking down Platforms 4 and 5, watching the trains come and go.

I was there to give the 2018 John Venn lecture. John Venn, inventor of the eponymous diagrams, was born in Hull in 1834, though he spent most of his career in Cambridge, where he was a fellow and sometime President of Gonville and Caius college, an institution with which I have a somewhat tenuous association.

I talked about the commutative law. As well as some of the stuff I talked about here (one of my most controversial posts ever, I am not sure why), it gave me a chance to wander round some of the back roads of logic, quantum mechanics, cryptography, etc., and to show some pictures from Alice’s Adventures in Wonderland and Through the Looking Glass. The slides are in the usual place, if you are interested.

After a very nice dinner, I slept well, and had time before I caught my train to have a short walk around the town.

The countryside through which the train runs on the way to Hull is extremely flat, like the Fens in East Anglia but if anything even more so. One of the stations is called Gilberdyke (you get the idea). After a while, hills appeared to the north (the Yorkshire Wolds, where I once ran one of the toughest half marathons of my life, and won a small prize as Fourth Veteran), then the Humber to the south, the wide estuary into which the rivers Ouse and Trent flow, now spanned by the Humber Bridge. I had just time enough in the morning to get down to the old docks, where (among other things) more than two million people from Europe arrived on their way to the New World (they mostly crossed to Liverpool and took ship there). It has a somewhat bleak and desolate feeling now.

The Humber

To finish, this is an excuse to recite one of my favourite poems to you, “Days”, by another famous inhabitant of Hull, Philip Larkin:

What are days for?
Days are where we live.
They come, they wake us
Time and time over.

They are to be happy in:
Where can we live but days?

Ah, solving that question
Brings the priest and the doctor
In their long coats
Running over the fields.

Posted in geography, history | Tagged , , , , , , , | Leave a comment

Publication lists and repositories

How many publications do I have?

Actually, I don’t care too much about that; but if I were younger and applying for promotion, it would actually matter. But suppose you wanted to answer the question, or indeed to get copies or reviews of the papers, or to find citation counts.

You could turn to the abstracting/reviewing websites, MathSciNet or Zentralblatt Math. They list, respectively, 320 and 328 publications, Zentralblatt giving the additional information that this includes 16 books. MathSciNet also finds 3252 citations of my work. Of course, both of these sites give access to reviews of the papers, and in some cases it is possible to get the published papers from there. But this depends on having the relevant subscriptions (as indeed does access to these two sites).

What about Web of Science? Well, I completely failed to find how to search for just my publications, and there are lots of people called P Cameron beavering away! Accurate author identification really matters.

Lots of people use Google Scholar, and it is not hard to see why. This site credits me with 381 publications, having 11351 citations. How do they get so many? I went down to the end of the list and found all sorts of things, some just about legitimate (documents put on the web but never published), some just crazy (fififiifiifli%fifi§§%fi._, by P. J. Cameron and N. M. Singhi, anyone?) There are ways of tidying this up, but it hardly seems worth the trouble. As to finding three times as many citations as MathSciNet does, I really don’t know how they manage this.

ORCiD tries to be accurate and reliable; it links to other databases and also allows me to edit entries easily. It lists 265 publications. Some of these were imported from Scopus, which lists 249 documents and 2991 citations. Also, increasingly, publishers are allowing you to log in via ORCiD rather than needing a separate login for each journal.

ORCiD gives DOIs for the papers it lists, which means that you can get anything (even book chapters) if you have the appropriate subscription (usually the case if you are logged in to a university account, though this may change).

Scopus is a commercial site; the information there seems fairly reliable (if incomplete), with one exception. Here is the list of my interests on Scopus: Mathematics, Computer Science, Physics and Astronomy, Social Sciences, Biochemistry, Genetics and Molecular Biology, Engineering, Decision Sciences, Psychology. Most of these are spurious. (I do have one paper in each of the Communications in Mathematical Physics and the Journal of Mathematical Psychology, but that doesn’t mean that either physics or psychology is a research interest of mine.)

DBLP gives me 128 publications of which 121 are journal articles (the others are parts in collections or informal publications). It links to everything and gives easy access to the other sources I have mentioned here. Why relatively few? It is a computer science database; frankly, I am surprised that I have as many as 128 publications that can be classified as computer science. (But I was astonished at the size of the DBLP database: they have over 8000 authors listed with the surname Wu, for example.)

I have 65 papers on the arXiv classified as mathematics, 5 computer science and 4 statistics (but there are some overlaps). Of course, I have not been putting papers on the arXiv for my entire career; first it didn’t exist, and then when it did I was too incompetent to use it, so my earliest papers there were posted by coauthors. And of course the great advantage of the arXiv is that you may freely get copies of the papers there. Most new papers of mine go there now, as well as some historical documents dug out of the files which may be of some interest.

The St Andrews repository lists 78 of my publications. These are the ones since the last-but-one research assessment (we were instructed some years ago to enter all these, and I never got round to putting in earlier ones: the process is far from straightforward). It is a repository: as well as titles, open-access copies or post-acceptance manuscripts available there.

According to my own list I have 344 publications, of which 17 are books. This is not completely accurate either. When I drew up this list some years ago, I made a few mistakes, so that one number in the range has no corresponding publication, while others have several (e.g. several chapters in the same book). Also, this list includes papers which are in press or have been accepted for publication, which it would not be reasonable for MathSciNet or Zentralblatt to know about.

So clearly MathSciNet and Zentralblatt are the most accurate sources. But if I were applying for promotion, you can see how Google Scholar would be tempting. Also, in my view, the arXiv is the most important repository.

Posted in publishing, technology | Tagged , , , , , , | Leave a comment

A new kind of design?

Rosemary and I have just put on the arXiv a paper prompted by a question by Valery Fedorov. Suppose that we are testing a number v1 of drugs on a number v2 of cancer types. To simplify the protocol, at each centre involved in the trial, only a limited number k1 (less than v1) of drugs will be used, and only a limited number k2 (less than v2) of cancer types will be treated. Thus, at each centre, the number of combinations of drug and cancer type is k1k2, and these combinations have the structure of a rectangle. Other desirable “balance” properties are that each pair of distinct drugs are used together at a constant number of centres, each pair of distinct cancer types are treated together at a constant number of centres, and each drug is used on each cancer type at a constant number of centres.

These designs have some familiar aspects. If you know about triple arrays, you might think that they are just triple arrays, but this is not so: if we lay out the plan with drugs and cancer types as rows and columns, then each cell contains a fixed number (not necessarily 1) of centres; moreover, the last condition says just this, whereas the last condition for triple arrays asks for the intersection of the set of letters in a row and the set of letters in a column.

Of course it is interesting to know how few centres are required if all these conditions are met, for reasons of reducing the cost of the trial. One of the things we prove is that the number b of centres is at least v1+v2−1. Despite my claim above, this is exactly the same inequality that is known for triple arrays, and our proof works almost without change for triple arrays. Moreover, it also generalises the well-known inequalities of Fisher and Bose for balanced designs and balanced resolvable designs respectively (these two types of structure being “degenerate” examples of our new designs).

We give many different constructions.

The reason we have put it on the arXiv now is that it appears that these designs are actually useful, and being used, in practice; moreover, they might be useful even in a more general setting where combinations of drugs can be given to a patient.

But, inevitably, the effect of preparing it for the arXiv has led us to further insights, solutions to some questions, and new lines of possible inquiry. So the published version, if one is ever produced, will contain more …

Posted in exposition | Tagged , , , , , | Leave a comment

Summer research into print

I described here the outcome of a summer research project in 2016 with St Andrews undergraduates Horacio Guerra and Šimon Jurina, on power graphs of torsion-free groups. (It took us a while to write it up, for various reasons.)

The paper was published on-line yesterday here, in the Journal of Algebraic Combinatorics.

Congratulations to Horacio and Šimon! They have beaten me: I was already a postgraduate student when my first paper was published.

Posted in doing mathematics, history | Tagged , , , | 1 Comment


I have been elected a Fellow of the Royal Society of Edinburgh. You can find the press release here.

Posted in Uncategorized | 6 Comments

Equitable partitions of Latin square graphs

On our recent trip to Shanghai, Rosemary Bailey and I met Sergey Goryainov, who gave a talk about some joint work with his supervisor Alexander Gavrilyuk at the International Workshop on Bannai–Ito Theory in Hangzhou. I mentioned it in my write-up and promised more to follow. The follow-up is here: Rosemary and I got to work on the problem and together the four of us have proved a generalisation.

I have spoken about the result at the Combinatorics Study Group in Queen Mary and at the St Andrews Research Day. A paper containing the complete proof of the theorem is now on the arXiv.

Equitable partitions

Let Γ be a finite graph; I will always assume it to be connected and regular with valency k. Let Ω be its vertex set.

A partition Π = {S1,…,Sr} of Ω is said to be equitable if there is a r×r matrix M (the quotient matrix of the equitable partition) such that a vertex in Si has exactly mij neighbours in Sj.

Equitable partitions of graphs include a large number of structures of interest
in finite geometry and combinatorics. Here are a few examples.

  • Let G be a group of automorphisms of Γ. Then the orbits of G on the vertex set of Γ form an equitable partition.
  • Consider the distance partition of Γ with respect to a vertex v: this is the partition Π whose ith part is the set of vertices at distance i from v, for i=0,…,d (where d is the diameter of Γ. These partitions are all equitable with the same matrix if and only if Γ is distance-regular: this is equivalent to the usual definition of a distance-regular graph.
  • Many important structures in finite geometry, including ovoids, spreads, and “Cameron–Liebler line classes”, fit into this framework.

We call a subset S of Ω perfect if the partition into S and its complement is equitable.

Theorem: The spectrum of the quotient matrix of an equitable partition is contained in the spectrum of the adjacency matrix A(Γ) of Γ.

To see this, let V be the real vector space of real functions on Ω, and let vi be the characteristic function of Si. Then from the definition we get

viA(Γ) = ∑mjivj,

so the subspace spanned by the vectors vi is invariant under A(Γ), and the matrix of the restriction relative to the given basis is the quotient matrix of the equitable partition.

In particular, in the case of a distance-regular graph, the quotient matrix M of the distance partition has each eigenvalue of A(Γ) with multiplicity 1.

Since Γ is regular and connected, its valency k is a simple eigenvalue of A(Γ). Also, the matrix M of the equivariant partition has all row sums equal to k; so k is an eigenvalue of M, called the principal eigenvalue.

If S is a perfect set such that the matrix of the partition {S,Ω\S} has eigenvalues k and μ, then we call S a μ-perfect set.

Here I am concerned with equitable partitions with just one non-principal eigenvalue. These of course include all such partitions with just two parts. In general, the partition Π has all non-principal eigenvalues equal to μ if and only if the characteristic vectors of its parts all lie in the sum of the eigenspaces with eigenvalues k and μ of A(Γ). From this fact, we get the following results, which reduce the problem of their classification to that of the minimal μ-perfect sets:

Proposition: Let Π = {S1,…,Sr} be a partition of the vertex set of the connected regular graph Γ.

  • If Π is equitable with all non-principal eigenvalues μ then each set Si is μ-perfect.
  • Conversely, if all but one of the Si are μ-perfect, then Π is equitable with all non-principal eigenvalues μ.

We call such partitions Π μ-equitable.

Latin square graphs

A Latin square L is a n×n array with entries from the set {1,…,n}, such that each letter occurs once in each row and once in each column.

Latin squares are important in combinatorics, since they are highly regular structures (giving rise to strongly regular graphs, as we will see) but exist in great profusion (the number of Latin squares of order n grows faster than the exponential of n2).

Given a Latin square L, the corresponding Latin square graph Γ has as vertices the n2 cells of L, two cells being adjacent if they lie in the same row or the same column or contain the same letter.

It is well known that this graph is a strongly regular graph (a distance-regular graph with diameter 2), which has valency 3(n−1), and whose other eigenvalues are n−3 (with multiplicity 3(n−1)) and −3 (with multiplicity (n−1)(n−2)).

Proposition: In a Latin square graph, the set of cells in any row (or in any column, or containing any letter) is (n−3)-perfect.

For a cell in a row is joined to n−1 other cells in that row and 2(n−1) cells outside; while a cell outside a row is joined to two cells in the row (one in the same column, and one with the same letter) and 3n−5 cells outside. So the partition is equitable, with matrix having eigenvalues 3(n−1) and n−3. It follows that any partition, each of whose parts is a union of rows (or columns, or letters), is equitable, with all non-trivial eigenvalues equal to n−3.

Are there any others?

At the International Workshop on Bannai–Ito Theory in Hangzhou, China, in November 2017, Sergey Goryainov talked about the following result that he and Alexander Gavrilyuk had proved:

Theorem: Let L be the Cayley table of an elementary abelian 2-group G of order n. Then a minimal (n−3)-perfect set in the Latin square graph is a row, a column, a letter, or the set of n2/4 cells corresponding to a subgroup of G of index 2.

Rosemary and I decided to have a go at generalising this result … Eventually the gang of four came up with a complete solution.

The main theorem

We found a couple more constructions.

Corner sets: Let L be the Cayley table of the cyclic group of order n, which we regard as being the set of integers modulo n. A typical corner set looks like this:

A corner set

A fairly simple calculation shows that a corner set is (n−3)-perfect.

We will also call a set obtained from a corner set as above by permuting rows,
columns or letters a corner set.

Inflation: Let L0 be a Latin square of order s. Construct an n×n array, where n = st, by replacing each entry of L0 by a Latin square of order t, where the squares which replace a given letter all use the same alphabet of size t, and the alphabets associated with different letters of L0 are pairwise disjoint. The resulting array is a Latin square L of order n, called an inflation of L0.

A short calculation shows that if S0 is a set of cells of L0 which is (s−3)-perfect, then the set of |S0|t2 cells of L in the corresponding subsquares is (n−3)-perfect. We call this set an inflation of S0.

Again, we use the same term for any square obtained by permuting rows, columns and letters.

In particular, in the unique Latin square of order 2, any single cell is a corner set; inflating this we see that, in a Latin square of even order n, any subsquare of order n/2 is an inflation of a corner set, and so is (n−3)-perfect.

Now we can state the main theorem:

Theorem: A minimal (n−3)-perfect subset of a Latin square graph from a square of order n is a row, a column, a letter, or an inflation of a corner set in a cyclic square.

The proof of this is quite complicated and I will not attempt even a sketch here. Read it on the arXiv if you are interested!

Going further?

The other non-principal eigenvalue of a Latin square graph is −3. Can we say anything about −3-perfect sets? Such a set S has the property that it meets any row, column or letter in a constant number s of cells, and its cardinality is sn.

In particular, with s = 1, such set is a transversal, a set containing one cell from each row, column or letter. One of the oldest conjectures about Latin squares is Ryser’s conjecture, asserting that any Latin square of odd order has a transversal. Many squares of even order do too, but some do not (for example, the Cayley table of the cyclic group). The conjecture is still open despite a lot of work, so characterising such sets is unlikely to be achieved soon!

We see also that, if an equitable partition Π has all non-principal eigenvalues −3, then all its parts satisfy the above condition, so that rows, columns, letters, and parts of Π form an orthogonal array of strength 2. In particular, if our square has an orthogonal mate, then the letters of this mate form such a partition.

There is a partition with parts of sizes 7, 14 and 28 of a Latin square of order 7 derived from the Fano plane.

If we consider partitions where both non-principal eigenvalues occur, there is much more freedom, and probably no hope of a classification. To mention just two examples:

  • The distance partition of the graph with respect to any cell. (As noted earlier, the non-principal eigenvalues each occur with multiplicity 1.)
  • The partition into t×t subsquares associated with a t-fold inflation of a Latin square of order s. (Both non-principal eigenvalues occur if and only if s > 2.)
Posted in Uncategorized | Tagged , , , , | Leave a comment