## Posts Tagged ‘**combinatorics**’

## Borges’ Theorem

No doubt one of the most delightful parts of writing a book of mathematics is the search for clever literary quotations to place at the beginning of chapters or to scatter throughout the book as appropriate (perhaps also, in the eyes of some, one of the greatest wastes of time). Flajolet and Sedgewick, in Analytic Combinatorics, make reference to the following result, which they call “Borges’ Theorem”, namely that given any finite set P of words, a random text of length n will contain every word of P with probability tending to 1 exponentially fast as n tends to infinity. The reason for the appellation “Borges’ Theorem” is due to Borges’ story The Library of Babel, which describes a library that contains

Everything: the minutely detailed history of the future, the archangels’ autobiographies, the faithful catalogues of the Library, thousands and thousands of false catalogues, the demonstration of the fallacy of those catalogues, the demonstration of the fallacy of the true catalogue, the Gnostic gospel of Basilides, the commentary on that gospel, the commentary on the commentary on that gospel, the true story of your death, the translation of every book in all languages, the interpolations of every book in all books.

## The necklace splitting problem

The necklace splitting problem may be formulated (somewhat fancifully) as follows.

Suppose that two thieves have stolen a necklace. The necklace is open at the clasp and consists of some number of jewels of k different types. There are an even number of jewels of each type. The thieves wish to cut the necklace into as few pieces as possible and share the pieces between the two of them so that each thief has a fair share of each type of jewel. What is the minimum number of cuts that suffices?

Alon and West (*Proc. Amer. Math. Soc.* 98 (1986) 623-628) showed that k cuts always suffices for a fair division of the necklace, regardless of the total number of jewels. Remarkably, the (very short!) proof of this combinatorial result uses a result from topology, namely the Borsuk-Ulam theorem.

## Hoffman’s eigenvalue bound on the size of an independent set

We present here Hoffman’s eigenvalue bound on the size of an independent set in a regular graph. We follow the presentation of Ellis, Friedgut, and Pilpel. Recall that a graph is -regular if every vertex has degree .

**Theorem**. Let be a -regular graph with adjacency matrix . Let be the eigenvalues of . Let be an independent set in . Then

.

*Proof*. Let us suppose that . Let be the inner product on defined by , where the denotes the usual dot product. Let be the corresponding norm on .

The adjacency matrix is a real symmetric matrix, so we may suppose that the eigenvectors (corresponding to the eigenvalues ) form an orthonormal basis of with respect to the inner product . Note that since is -regular, is the vector with all entries equal to . Let be the characteristic vector of the independent set and define .

Observe that counts the number of edges among the vertices of . Since is an independent set, we have . We write as a linear combination of the eigenvectors; i.e.,

.

Since the ‘s form an orthonormal set, we have . By Parseval’s identity we also have

.

We therefore have

.

Thus,

,

whence we obtain

,

as required.

## The number of ways of shuffling a cabinet

No doubt the first question on the mind of anyone reading the previous post concerning John A. Macdonald’s double shuffle is, “In how many ways could Macdonald have appointed his former cabinet members to new ministries so that no minister was appointed to the same position that he had held in the previous Macdonald government?”

Letting denote the number of ministers in Macdonald’s cabinet, the answer to this question is , the number of derangements of an -element set. A *derangement* is a permutation such that no element is mapped to itself. The number of derangements of an -element set is well-known to be , which turns out to be simply the nearest integer to .

I am too lazy to bother writing a proof of this formula here, so instead I refer the reader to, for example, the book *Concrete Mathematics* by Graham, Knuth and Patashnik.

## The Fine-Wilf Theorem

The Fine-Wilf Theorem is as follows. Supppose and are two infinite periodic sequences with periods and respectively. If and agree on their first terms then the two sequences are identical.

We present here the elegant algebraic proof given as the solution to Problem 134 in Bollobas’ book *The Art of Mathematics* and attributed by Bollobas to Ernst Straus.

We first define formal power series and . By the periodicity hypothesis, we have and for some polynomials of maximum degrees and respectively. However, since divides each of and , we also have

where is some polynomial of degree at most . If the first coefficients of and coincide, then the first coefficients of are zero, whence the polynomial is the zero polynomial. It follows that is identically zero, so that and and hence and are identical, as claimed.

We should point out that several other results that we have discussed in previous posts appear as problems in the previously mentioned book by Bollobas.

- Cauchy-Davenport is Problem 96.
- Erdos-Ginzburg-Ziv is Problem 97.
- Bollobas’ Cross-Intersecting Pairs Theorem is a weaker version of a result of Frankl given as Problem 113.
- Problem 115 is a consequence of the two families result discussed here.

## Enumerating permutations by number of inversions

We have previously given a proof of the identity

,

which is Euler’s Pentagonal Number Theorem. We now describe how to apply this formula to derive a formula for the number of permutations of elements with inversions. Let be a permutation of , written in the so-called “one line” notation. An inversion of is a pair such that and . Let denote the number of inversions of . Then we claim that the generating function of is

.

We prove this by induction on . For , we have one permutation with no inversions and one with one inversion, whence we obtain the generating function , as claimed.

Suppose the claim holds for and let be a permutation of . We create a new permutation by inserting into . If we insert after all elements of we have created no new inversions; if we insert after all but one element of we have created one new inversion; and in general, if we insert after all but elements of we create new inversions. Thus the number of permutations so created is enumerated by the generating function

,

as claimed. This completes the proof.

Let denote the coefficient of in ; i.e., is the number of permutations of elements with inversions. We wish to deduce a formula for . Since is the coefficient of in , it must also equal the coefficient of in the infinite product . By Euler’s Pentagonal Number Theorem, we have

.

Thus, is the coefficient of in . By the binomial theorem, we have

(recall that ). Thus, letting denote the pentagonal numbers, we obtain a term in by multiplying a term from by a term from . The coefficient of in is , and the coefficient of in is . Thus, the coefficient of is given by

,

where the sum is over all for which . This is the desired formula for the number of permutations of elements with inversions.

## Another intersecting families result

We have previously discussed the following result of Kleitman concerning intersecting families of sets: if are monotone decreasing families of subsets of , then . Suppose that instead of the hypothesis that are monotone decreasing, we instead have that is even for every , . In this case we have the following result of Ahlswede, El Gamal, and Pang (1984).

**Theorem**. If are families of subsets of such that is even for every , , then .

*Proof*. Let and be the vector spaces over GF(2) generated by the sets of characteristic vectors of the sets in and respectively. The assumption that is even for every , means that the inner product is 0 over GF(2) for every , . In other words is contained in the orthogonal complement of . Since , we have , as required.