\magnification 1200
\def\cp{{\cal P}}
\def\cm{{\cal M}}
\def\ncong#1{\not\equiv #1\pmod{p}}
\hsize 5 in
{\topskip 0.8 true in
\centerline{\bf Congruence problems involving Stirling numbers of the first
kind}
\vskip .25 true in
\centerline{Rhodes Peele}
\centerline{Auburn University at Montgomery}
\centerline{Montgomery, AL 36117-3596}
\vskip .1 true in
\centerline{and}
\vskip .1 true in
\centerline{A. J. Radcliffe}
\centerline{University of Pennsylvania}
\centerline{Philadelphia, PA 19104-6395}
\vskip .1 true in
\centerline{and}
\vskip .1 true in
\centerline{Herbert S. Wilf\footnote{$^*$}{Supported in part by the
United States Office of Naval Research.}}
\centerline{University of Pennsylvania}
\centerline{Philadelphia, PA 19104-6395}
\vskip .4 true in
\baselineskip20pt
\centerline{\bf Abstract}
\vskip 8pt
For a fixed integer $k\ge 0$ and a prime $p$, the number $v(k,p)$ of $n$
such that ${n\brack k}\ncong 0$ (where ${n\brack k}$ is the (signless) Stirling number
of the first kind) is known to be finite. We express its generating
function $\sum_kv(k,p)x^k$ as an infinite product of polynomials in a way that
seems to be computationally useful. We also investigate a connection between this
problem and the number of partitions of an integer $k$ into prime power parts
$p^i$ whose multiplicities $m_i$ satisfy $(m_i \hbox{ mod } p) + \lfloor m_i/p \rfloor
< p$.
\vskip .2 true in
\noindent{\bf Date:} July 7, 1991.
\vskip 8pt
\noindent{\bf Keywords:} Stirling number, congruence, generating function,
Lucas congruence, natural bijection.
\vskip 8pt
\noindent{\bf MR Subject Numbers:} 05A15, 11B73
}
\vfill
\eject
\baselineskip 20pt
\def\bskip{\vskip.3truein}
\def\ub{\underbar}
\def\sqr#1#2{{\vcenter{\vbox{\hrule height.#2pt
\hbox{\vrule width.#2pt height#1pt \kern#1pt
\vrule width.#2pt}
\hrule height.#2pt}}}}
\def\square{\mathchoice\sqr34\sqr34\sqr{2.1}3\sqr{1.5}3}
\noindent {\bf 1. Introduction and summary of results.}
\medskip
It is by now well known that the parities of the binomial coefficients show a
fractal-like appearance when plotted in the $x$-$y$ plane. Similarly, if
$f(n,k)$ is some counting sequence and $p$ is a prime, we can plot an
asterisk at $(n,k)$ if $f(n,k)\ncong 0$, and a blank otherwise, to get other
complex, and often interesting, patterns.
For the ordinary and Gaussian binomial coefficients and for the Stirling
numbers of the second kind, formulas for the number of asterisks in each
column are known ([Si], [Fi], [H1], [Ca]). Moreover in each row the
pattern is periodic, and formulas for the minimum period have been found
([Fi], [Fr], [K1], [K2], [Si], [T], [NW], [Z]) in all three cases.
If ${n\brack k}$, the signless Stirling number of the first kind, denotes, as
usual, the number of permutations of $n$ letters that have $k$ cycles, then
for fixed $k$ and $p$ we will show that there are only finitely many $n$ for
which ${n\brack k}\ncong 0$, i.e., there are only finitely many asterisks in
each row of the pattern. Let $v(n,k)$ be the number of these.
To describe the generating function of the $v(n,k)$ we first need to define a
{\it special integer modulo} $p$. We say that a nonnegative integer $n$ is
special modulo $p$ if $$n\bmod{p}+\biggl\lfloor{n\over p}\biggr\rfloor\le
p-1.$$ This means that $n$ is a 1- or 2-digit $p$-ary integer and, in the
addition of $n$ to its digit reversal, there is no carry out of the units
place. We denote by $N_p$ the (finite) set of all special integers modulo
$p$, and we write $N_p(x)$ for the polynomial $\sum_{n\in N_p}x^n$. For
example, $N_3(x)=1+x+x^2+x^3+x^4+x^6$.
Finally, we denote by $c_p$ the finite sequence that is defined by $c_p(0)=1$
and
$$c_p(i)=|\{n\le p-1: {{n }\brack {i }}\ncong 0\}|\qquad (1\le i\le p-1).$$
We write $C_p(x)$ for the polynomial $\sum_{0\le i\le p-1}c_p(i)x^i$. For
example, $C_3(x)=1+2x+x^2$.
\vskip 12pt
\proclaim Theorem A. The number $v(k,p)$ of $n\ge 0$ such that ${n\brack
k}\ncong 0$ is given by $$\sum_{k\ge 0}v(k,p)x^k=C_p(x)\prod_{j\ge
0}N_p(x^{p^j}).$$ \vskip 18pt
As an illustration of Theorem A, take $p=3$. Then $C_3(x)=1+2x+x^2$ and so
$$\eqalign{\sum_{k\ge 0}v(k,3)x^k&=(1+2x+x^2)\prod_{j\ge 0}N_3(x^{3^j})\cr
&=1+3x+4x^2+5x^3+7x^4+7x^5+7x^6+9x^7+8x^8+8x^9+12x^{10}\cr
&\quad +12x^{11}+12x^{12}+16x^{13}+15x^{14}+13x^{15}+15x^{16}+12x^{17}+\cdots
\cr}$$
Thus there are, for example, 12 values of $n$ for which ${{n }\brack {17 }}$
is not a multiple of 3. In Corollary 2.2 below we will see that the largest
of these is ${{kp }\brack {k }}={{51 }\brack {17 }}$ (which has 59 decimal
digits).
Along the way to proving Theorem A we will find the following result, which
seems to be of independent interest.
\vskip 18pt
{\bf Theorem B.} {\sl Let $k\ge 0$ and $p$ be a fixed integer and prime,
respectively. Then the following two sets are equinumerous:
{\parindent 40pt
\item{$\bullet$} The set of all $j\le k/(p-1)$ for which the binomial
coefficient ${{k-(p-1)j}\choose j}\ncong 0$, and
\item{$\bullet$} The set of all partitions of the integer $k$ into parts that
are powers of $p$, and in which the multiplicity of each part is special
modulo $p$.
}}
Although we find Theorem B by means of generating functions, the form of the
result suggests that there may be a natural bijection between the two sets.
We will give such a bijection also.
\vskip 18pt
Our results dualize, in an interesting way, results of Carlitz [Ca]. He
studied similar questions for the Stirling numbers of the second kind. More
precisely, he studied the number of $k$ for which ${n\brace k}$ is not
divisible by $p$ and deduced infinite product generating functions for these
numbers that are quite similar to ours. His results are complete if
$p=2,3,5$, but only partial for other values of $p$. The duality of the
questions and the similarity of the answers is arresting.
\bigskip
\noindent{\bf 2. An analog of Lucas's congruence}
\medskip
Lucas's congruence ([Fi], [L]) for binomial coefficients asserts that
${n'p+n_0\choose k'p+k_0}\equiv {n'\choose k'}{n_0\choose k_0}$ $(\bmod\, p)$
if $n'$, $k'$, $n_0$ and $k_0$ are
nonnegative integers with $n_0$ and $k_0$ less than $p$. It is easily proved
by viewing $(x+1)^{n'p+n_0}=(x+1)^{n'p}(x+1)^{n_0}$ as an identity over
$GF(p)\,[x]$ and using the ``freshman" $\left( (x+1)^p\equiv x^p+1\right)$
and binomial theorems. By imitating this proof we can get a somewhat similar
congruence for the residue modulo $p$ of ${n\brack k}$. \medskip Recall that
${n\brack k}=(n-1){{n-1 }\brack {k }}+{{n-1 }\brack {k-1 }}$ for $n,k>0$,
${{n }\brack {0 }} = 0$ for $n>0$, ${{0 }\brack {k }} = 0$ for $k>0$, and
${{0 }\brack {0 }} = 1$. Further recall that the ordinary generating function
for $\{{{n }\brack {\cdot }}\}$ is $$s_n(x)=x(x+1)(x+2)\cdots (x+n-1).$$
\medskip For the remainder of this section, all of our computations will take
place in the polynomial ring $GF(p)[x]$. To begin with, note that $s_0(x)=1$
is the only $s_n(x)$ with a constant term, and that $$s_p(x)=x^p-x\eqno(1)$$
in $GF(p)[x]$ since both sides of (1) are polynomials of degree $p$ with
simple roots $r=0,1,\ldots,p-1$ and leading coefficient 1. \medskip
\proclaim Lemma 1. For
all $n$, $$s_n(x)\equiv x^{n'}(x^{p-1}-1)^{n'}s_{n_0}(x)\quad
\pmod{p}\eqno(2)$$ where $n'=\lfloor{n/p}\rfloor$ and $n_0=n\bmod{p}$.
\noindent{\bf Proof:} We have $n=n'p+n_0$ with $0\leq n_00).\cr}\eqno(3)$$
Then
$${n\brack k}=(-1)^{n'-j}{n'\choose j} {{n_0 }\brack {i }}\quad (\bmod{p}).\eqno(4)$$
\vskip 10pt
\proclaim Corollary 2.2. For a fixed $k$ the set $\{n :
{n\brack k}\ncong 0\}$ is finite. Its largest element is $pk$ and its
smallest is $k$.
\medskip
\noindent {\bf Proof.} If $n>pk$ then in (3) above, $j<0$ and so ${n\brack
k}=0\ (\bmod\,p)$. If $n=pk$ then $n'= n_0=i=j=0$ and ${{pk }\brack {k
}}=(-1)^k\ (\bmod\,p)$. If $n=k$ then $n'=j$,$n_0=i$, and ${{k }\brack {k
}}=1\ (\bmod\,p)$. If $n