Letter to the Editor of the Monthly about v. 102, issue 10 (Dec. 1995)

Doron ZEILBERGER^{1}

I would like to comment on two of the articles of v. 102, # 10 (Dec. 1995).

1. The Sing-Sing problem (pp. 880- 887), by Blom, Holst, and Sandell, is a special case of a standard set of problems handled by the powerful Goulden-Jackson method (see section 2.8 of their book: I. Goulden and D. Jackson, Combinatorial Enumeration, John Wiley, 1983). The generating function, according to the number of occurrences of ‘double letters’ of words in the alphabet {1, 2, ..., n}, is (using the G-J L-cluster method)

(1 − ∑_{i=1}^{n} \frac{x_{i}}{1 + (1 − t)x_{i}})^{−1} .

To get their result (for the linear case, the other cases are minor variations, that can also be handled by G-J), one should extract the coefficient of x_{1}^{2} ⋯ x_{n}^{2}, by first using the multinomial theorem, and then noting that the only way that [x/(1 + (1 − t)x)]^{m} can have coefficient x^{2} is when m = 1 or m = 2, and hence in the multinomial expansion we should choose which of the (x_{i}/(1+(1−t)x_{i}))^{m_{i}} should have m_{i} = 1, and which m_{i} = 2, and use symmetry. Finally to get Theorem 2, extract the coeff. of t^{k}.

The same method can be used to solve the (SING)^{r} problem with any r, where one would extract the coeff. of x_{1}^{r} ⋯ x_{n}^{r}, and get an (r − 1)-fold binomial coefficients sum, which implies that the g.f. (in t) is always P-recursive (i.e. satisfies a linear recurrence with polynomial coefficients, see e.g. A = B, by Petkovsek, Wilf, and Myself, A.K. Peters, 1996), in particular the probability of a word in 1^{r} … n^{r} having no double letters is P-recursive.

Ad: A Maple package GOULSON, written by me, implementing the Goulden-Jackson L-cluster method, can be obtained from http://www.math.temple.edu/~zeilberg (click on ‘Maple packages and programs’, and then on ‘GOULSON’). (Also by Anon. ftp to ftp.math.temple.edu,

directory pub/zeilberg/programs).

2. Theorem 1 of the same paper is completely routine. It is clear by a priori combinatorial grounds (changing the order of summation), that the mean and variance are rational functions with predictable denominators, and numerators that are polynomials in n of low degrees, hence a completely rigorous, yet brute force, proof, would be to empirically find these quantities empirically for small n, and then fit a polynomial into the data. See my paper, The Joy of Brute Force, published in http://www.math.temple.edu/˜ zeilberg, 1995.

1 Department of Mathematics, Temple University, Philadelphia, PA 19122, USA. zeilberg@math.temple.edu

http://www.math.temple.edu/~zeilberg   ftp://ftp.math.temple.edu/pub/zeilberg .

Jan. 7, 1996.

3. The same brute force approach yields that, in the paper by Blecksmith and Laud (pp. 893-903), the quantity ∑_{j} B(j), summed over all n−digit integers (in base b), equals (b−1)b^{n−2}(1+n(b−1)), hence the average is (b−1)n/b+1/b. (The variance turns out to be (b−1)(n−1)/b^{2}. It follows that a random n − digit number has, on the average, .9n + .1 ± .3(n − 1)^{1/2} blocks). Their ‘conjecture’ (right at the end of the paper, p. 903) is an immediate consequence.

4. While the above brute force argument is more elegant, another derivation is as follows. Let the weight of an n − digit integer j in base b be equal to t^{B(j)}, where B(j) is the number of blocks of j. (For example B(12131) = 5, B(44444) = 1, B(11222) = 2). Then the generating function,

∑_{j} t^{B(j)} ,

where the sum ranges over all n−digit integers, is clearly (b−1)t((b−1)t+1)^{n−1}. Indeed the most significant digit can be one of (b−1) possibilities (0 is not allowed), and it starts a block, explaining the t. Now every time you start a less significant digit, you either repeat the previous one (not creating a new block), which explains the 1 inside the ((b − 1)t + 1)^{n−1}, or you get a brand-new digit, ((b − 1) possibilities), hence creating a new block, explaining the (b − 1)t. Now the mean and variance (and higher moments) can be obtained by repeated diff., plugging in t = 1, and using the formulas of ‘Concrete Math’ by Graham, Knuth, Patashnik, Addison-Wesley , section 8.3.

5. As I wrote the above observation up, it occurred to me that the above problem is very standard, it is the problem of ‘runs’ in rolling a b-faced die (where the first throw can’t be 0).