  
%AMM.tex: a plain TeX file of the paper `Letter to the Editor ... v.102 #10'
%outputs 2 pages
%begin macros
\def\mod{\mathop{\rm mod} \nolimits}
\baselineskip=14pt
\parskip=10pt
\def\Tilde{\char126\relax}
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
 height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\lheading#1{\bigbreak \noindent {\bf#1} 
}
\parindent=0pt
\overfullrule=0in
%end macros
\bf
\centerline
{Letter to the Editor of the Monthly about v. 102, issue 10 (Dec. 1995)}
\rm
\bigskip
\centerline{ {\it Doron ZEILBERGER}\footnote{$^1$}
{\eightrm  \raggedright
Department of Mathematics, Temple University,
Philadelphia, PA 19122, USA. 
{\eighttt zeilberg@math.temple.edu \break
http://www.math.temple.edu/\Tilde zeilberg \quad
 ftp://ftp.math.temple.edu/pub/zeilberg} \quad .
\break
Jan. 7, 1996.
} 
}
 
I would like to comment on two of the articles of v. 102, \# 10 (Dec. 1995).
 
{\bf 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- \sum_{i=1}^n {{x_i}\over {1+(1-t)x_i}})^{-1} \quad.
$$
 
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 \cdots 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 \cdots 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 \dots n^r$ having
no double letters is P-recursive.
 
{\bf Ad:} A Maple package {\it GOULSON}, written by me, implementing
the Goulden-Jackson L-cluster method, can be obtained from
{\tt http://www.math.temple.edu/\Tilde zeilberg} (click on `Maple packages
and programs', and then on `GOULSON'). (Also by Anon. ftp to
{\tt ftp.math.temple.edu}, directory {\tt pub/zeilberg/programs}).
 
{\bf 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, {\it The Joy of Brute Force},
published in {\it http://www.math.temple.edu/\Tilde zeilberg}, 1995.
 
{\bf 3}. The same brute force approach yields that, in the
paper by Blecksmith and Laud (pp. 893-903), the quantity
$\sum_{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 \pm .3 (n-1)^{1/2}$
blocks). Their `conjecture' (right at the end of the paper,
p. 903) is an immediate consequence.
 
{\bf 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,
$$
\sum_j t^{B(j)} \quad,
$$
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.
 
{\bf 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$).
 
\bye
