\documentclass[12pt]{article}
\textwidth= 6.5in
\textheight= 9.0in
\topmargin = -20pt
\evensidemargin=0pt
\oddsidemargin=0pt
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9

\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{ifthen}
\newtheorem{thm}{Theorem}
\newtheorem{lm}{Lemma}
\renewcommand{\tablename}{Table}
\begin{document}
\vspace*{-60pt} 
\centerline{\smalltt INTEGERS: 
 \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 5(1) 
(2005), \#A21} 
\vskip 50pt 

\begin{center}
{\bf ON $2$-ADIC ORDERS OF STIRLING NUMBERS OF THE SECOND KIND}
\vskip 20pt
{\bf Stefan De Wannemacker}\\
{\smallit Department of Mathematics, University College Dublin, Belfield, Dublin 4, Ireland}\\
{\tt sdwannem@maths.ucd.ie}\\  \vskip 10pt
\end{center}
\vskip 30pt \centerline{\smallit Received: 7/15/04,
Revised: 8/11/05, Accepted: 9/26/05,
Published: 10/4/05} \vskip 30pt

\centerline{\bf Abstract}

\noindent We prove that for any $k = 1,\ldots,2^{n}$ the $2$-adic
order of the Stirling number $S(2^{n}, k)$ of the second kind is
exactly $d(k)-1$, where $d(k)$ denotes the number of $1$'s among
the binary digits of $k$. This confirms a conjecture of Lengyel.

\pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm
ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 5(1)
(2005), \#A21\hfill}

\thispagestyle{empty} \baselineskip=15pt \vskip 30pt

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                                                                %
%  Introduction                                                                                                  %
%                                                                                                                %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{\normalsize 1. Introduction}
For a nonzero integer $m$, if $2^h$ is the highest power of two
dividing $m$, then we say that the $2$-adic order $\rho_2(m)$ of
$m$ is $h$. In this paper $\rho_2(\cdot)$ is called the $2$-adic
valuation function.\\
Legendre observed that if $n \in \mathbb{N}=\{0,1,2,\ldots\}$ then
$\rho_2(n!)=n-d(n)$, where $d(n)$ is the number of $1$'s in the
binary representation of $n$, in other words $d(n)
=\sum_{\lambda=0}^{\infty}{\varepsilon}_\lambda(n)$ if
$n=\sum_{\lambda=0}^{\infty}{\varepsilon}_\lambda(n)2^\lambda$
with ${\varepsilon}_\lambda(n) \in \{0,1\}$.  Kummer proved that
$\rho_2\left(\binom{n}{k}\right)=d(k)+d(n-k)-d(n)$ whenever $0\leq
k \leq n$.\\
Let $n\in \mathbb{N}$. The Stirling numbers $S(n,k)\, (k\in
\mathbb{N})$ of the second kind are given by
\[x^n=\sum_{k=0}^{\infty}S(n,k)(x)_k,\] where
$(x)_k=x(x-1)(x-2)\ldots(x-k+1)$ for $k \in \mathbb{N}\setminus
\{0\}$ and $(x)_0=1.$  Actually $S(n,k)$ is the number of ways in
which it is possible to partition a set with $n$ elements into
exactly  $k$\ nonempty subsets.  For more details and basic
results on Stirling numbers of the second kind we refer the reader
to \cite{GKP} and \cite{COM}.\\
In this paper we study $2$-adic orders of Stirling
numbers of the second kind, and establish the following theorem
which was conjectured by T.Lengyel \cite{LEN} and verified by him
in some special cases.
\begin{thm}
Let $n,k \in \mathbb{N}$ and $1\leq k\leq 2^n$. Then we have
\[\rho_2(S(2^n,k)) = d(k) - 1.\]
\end{thm}

In the next section we reveal some useful properties of Stirling
numbers of the second kind.  We are going to prove Theorem 1 in
Section 3 on the basis of Section 2.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                                                                %
%  Auxiliary results                                                                                             %
%                                                                                                                %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{\normalsize 2. Auxiliary results on Stirling numbers of the second kind}
The following identity relates the Stirling numbers of the second
kind $S(n+m,\cdot)$ to $S(n,\cdot)$ and $S(m,\cdot)$.\\
\begin{thm}\label{Wannemacker} Let $n,m,k \in \mathbb{N}$
such that $0 \leq k \leq n+m$.  Then
\[S(n+m,k) = \sum_{i=0}^{k}\sum_{j=i}^{k}\binom{j}{i}\frac{(k-i)!}{(k-j)!}\
S(n,k-i)S(m,j).\]
\end{thm}
\begin{proof} Let $n, m \in \mathbb{N}$.  Then
\begin{align*}
x^{n+m}\,&=\ x^nx^m=\ \sum_{r=0}^{n}S(n,r)(x)_r\sum_{j=0}^{m}S(m,j)(x)_j\\
&=\ \sum_{r=0}^{n}S(n,r)(x)_r\sum_{j=0}^{m}j!S(m,j)\binom{x}{j}\\
&=\ \sum_{r=0}^{n}S(n,r)(x)_r\sum_{j=0}^{m}j!S(m,j)\sum_{i=0}^j\binom{x-r}{i}\binom{r}{j-i}\\
&\text{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad(by the Chu-Vandermonde identity)}\\
&=\
\sum_{r=0}^{n}S(n,r)\sum_{j=0}^{m}S(m,j)\sum_{i=0}^j\frac{j!}{i!}\binom{r}{j-i}(x)_{r+i}\\
\end{align*}
Thus, for any $k=0,1,\ldots,n+m\ $ we have
\begin{align*}
S(n+m,k)\,&=\ \sum_{i=0}^{k}\sum_{j=i}^{k}\frac{j!}{i!}\binom{k-i}{j-i}\ S(n,k-i)S(m,j)\\
&=\ \sum_{i=0}^{k}\sum_{j=i}^{k}\binom{j}{i}\frac{(k-i)!}{(k-j)!}\
S(n,k-i)S(m,j).
\end{align*}
\end{proof}

\noindent
{\bf Remark: } Stirling numbers of the second kind occur in a
natural way while making calculations in the Witt ring (see
\cite{WAN} for further details). It was in this context
that the previous identity arose.\\
\begin{lm}\label{lower_bound_d} Let $m,n \in \mathbb{N}$. Then
\[d(m+n)\leq d(m) + d(n)\] and equality holds if and only if \[\sum_{\lambda=0}^{\infty}
\varepsilon_\lambda(m)\varepsilon_\lambda(n)=0,\] i.e., when $m$
and $n$ have no non-zero binary digit in common.
\end{lm}
\begin{proof}
If $m$ and $n$ have no non-zero binary digit in common then it is
obvious that $d(m+n) = \sum \varepsilon_\lambda(m+n)=\sum
(\varepsilon_\lambda(m) + \varepsilon_\lambda(n)) = d(m) + d(n).$
On the other hand, suppose that $m$ and $n$ have a non-zero binary
digit in common.  Let us say that $\lambda_0$ is the lowest
natural number such that
$\varepsilon_{\lambda_0}(m)=\varepsilon_{\lambda_0}(n)=1$. Then it
is clear that $\varepsilon_{\lambda_0}(m+n)=0$ and 1 is added to
$\varepsilon_{{\lambda_0}+1}(m)+\varepsilon_{{\lambda_0}+1}(n)$ to
obtain an expression for $\varepsilon_{{\lambda_0}+1}(m+n)$.
Anyhow, at least one non-zero binary digit is lost in $d(m+n)$.
\end{proof}
\noindent{\bf Remark: }\label{remark} The case
$d(m+n)=d(m)+d(n)-1$ occurs if and only if
 $\varepsilon_{{\lambda_0}+1}(m)=\varepsilon_{{\lambda_0}+1}(n)=0$
with ${\lambda_0}$ the unique natural number such that
$\varepsilon_{\lambda_0}(m)=\varepsilon_{\lambda_0}(n)=1$.
\\
\ \\
A new lower bound on the $2$-adic order of Stirling numbers of the
second kind can be obtained as follows.
\begin{thm} Let $n,k \in \mathbb{N}$ and $0 \leq k \leq
n$. Then
\[\rho_2\left(S(n,k)\right) \geq d(k) - d(n).\]
\end{thm}
\begin{proof}
We use induction on $n$.\\
\\
For $n=0$, $\rho_2(S(0,0))=\rho_2(1)\geq d(0) - d(0)$.\\
\\
Assume now that the above inequality is true for all $i<n$.  We
will prove the theorem for $n$. Observe that for $k=0$ the result
is obviously true.\\
Let $1\leq k \leq n$. The Stirling numbers of the second kind
satisfy the well-known `vertical' recurrence relation
\[S(n,k)=\sum_{i=k-1}^{n-1}\binom{n-1}{i}S(i,k-1).\]
Combining this with the `triangular' recurrence relation
\[S(n,k)=S(n-1,k-1)+kS(n-1,k)\]
we obtain
\[kS(n,k) = \sum_{i=k-1}^{n-1}\binom{n}{i}S(i,k-1).\]
Thus
\begin{align*}
\rho_2(kS(n,k))&=\rho_2\left(\sum_{i=k-1}^{n-1}\binom{n}{i}S(i,k-1)\right)\\
&\geq \min_{k-1\leq i\leq n-1}\{ \rho_2\left(\binom{n}{i}\right)+d(k-1) - d(i)\}\\
& \text{\qquad\qquad\qquad\qquad\qquad\qquad(by the induction hypothesis)}\\
&= \min_{k-1\leq i\leq n-1}\{ d(n-i) + d(k-1) - d(n)\}\\
& \text{\qquad\qquad\qquad\qquad\qquad\qquad(by the Kummer identity)}\\
&= d(k-1)-d(n) + 1.
\end{align*}
So,\\
\begin{align*}
\rho_2(S(n,k))&\geq d(k-1) - \rho_2(k) + 1 -d(n)\\
&=d(k)-d(n).
\end{align*}
\end{proof}
\section*{\normalsize 3. Proof of Lengyel's conjecture}
We use induction on $n$.
For $n=0$, $\rho_2(S(1,1))=\rho_2(1)=0=d(1)-1$.
We assume the theorem is true for all powers $2^i$ where
$i<n$.  We will prove that the theorem holds for $2^n$.\\
By Theorem \ref{Wannemacker}
\begin{equation}
\label{Stirling} S(2^n,k) =
\sum_{i=0}^{k}\sum_{j=i}^{k}\binom{j}{i}\frac{(k-i)!}{(k-j)!}\
S(2^{n-1},k-i)S(2^{n-1},j).
\end{equation}\\
We will take a closer look at the $2$-adic valuation of each term
in this sum \eqref{Stirling}.
\begin{align*}
\rho_2&\left(\binom{j}{i}\frac{(k-i)!}{(k-j)!}\ S(2^{n-1},k-i)S(2^{n-1},j)\right)\\
&=\rho_2\left(\binom{j}{i}\right)+\rho_2((k-i)!)-\rho_2((k-j)!)+\rho_2(S(2^{n-1},k-i))+\rho_2(S(2^{n-1},j))\\
&=\rho_2\left(\binom{j}{i}\right)+\rho_2((k-i)!)-\rho_2((k-j)!)+d(k-i)+d(j)-2\\
&\text{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad(by the induction hypothesis)}\\
&=d(i)+d(j-i)-d(j)+(k-i)-d(k-i)-(k-j)+d(k-j)+d(k-i)+d(j)-2\\
&\text{\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad(by the Kummer and Legendre identities)}\\
&=d(i)+d(j-i)+j-i+d(k-j)-2.
\end{align*}
The inequality of Lemma 1 implies that
\[d(i)+d(j-i)+j-i+d(k-j)-2 \geq d(j)+j-i+d(k-j)-2 \geq d(k)-2+j-i.\]
Since $j\geq i$, the $2$-adic valuation of every term in the sum
is at least $d(k)-2$.  To prove that the $2$-adic valuation of the
global sum \eqref{Stirling} equals $d(k)-1$ we will calculate the
number of terms with $2$-adic valuation $d(k)-2$ and the number of
terms with $2$-adic valuation $d(k)-1$. These two results together
will show that the $2$-adic valuation of
\eqref{Stirling} equals $d(k) - 1$.\\

For $k=1$ the theorem holds since $\rho_2(S(2^n,1))=\rho_2(1)=0=d(1)-1,$ for all $n\in \mathbb{N}$.\\
So assume $k\neq 1$.

$\text{ }$\\
\textbf{Case 1 : $d(i)+d(j-i)+j-i+d(k-j)-2 = d(k)-2$.}\\
\vspace*{2ex}\\
Since $d(i)+d(j-i)+d(k-j)\geq d(k)$ and $j\geq i$, this situation
can occur only when $j=i$ and $d(i)+d(k-i)=d(k)$. By Lemma 1 this
holds only when $i$ and $k-i$ have no non-zero binary digit in
common, or equivalently, when
$\varepsilon_\lambda(i)+\varepsilon_\lambda(k-i)=\varepsilon_\lambda(k)$,
for all $\lambda\in \mathbb{N}$.\\
If $\varepsilon_\lambda(k)=1$ (this occurs $d(k)$ times), the
possible values for $\varepsilon_\lambda(i)$ are $0$ and $1$.\\
If $\varepsilon_\lambda(k)=0$, then $\varepsilon_\lambda(i)=0$ as
well.\\ So, for a given $k$, there are $2^{d(k)}$ possibilities
for $i=j$. We need to modify this number of possibilities since it
includes the non-occurring situations $i=j=0$ and $i=j=k$. This
means we have $2^{d(k)}-2$ terms in
\eqref{Stirling} with $2$-adic valuation $d(k)-2$.\\
In the case where $d(k)=1$, i.e. $k=2^m$, there are no terms
satisfying the condition.  When $d(k)>1$, these $2^{d(k)} -2$
terms contribute, in total, $M2^{d(k)-1}$ to (1).\\
We will show that $M$ is odd.  Let $O(i)$ be the odd part of
$S(2^{n-1},i)$.  Consider the sum in this case\\
\begin{equation*}
\begin{split}
& \sum_{i=1\atop d(i)+d(k-i)=d(k)}^{k-1}S(2^{n-1},k-i)S(2^{n-1},i)\\
&= \sum_{i=1\atop d(i)+d(k-i)=d(k)}^{k-1}O(k-i)O(i)2^{d(k)-2}.\\
\end{split}
\end{equation*}
The latter expression is invariant under switching $i$ and $k-i$
and since $i=k/2$ (in the case $k$ even) never occurs
($d(k/2)+d(k/2)=2d(k)\neq d(k)$) we obtain
\begin{equation*}
\begin{split}
&\ \sum_{i=1\atop {d(i)+d(k-i)=d(k)\atop i<k/2}}^{k-1}O(k-i)O(i)2^{d(k)-1}.\\
\end{split}
\end{equation*}
This last expression consists of an odd number, $2^{d(k)-1}-1$, of
terms, so it contributes, in total, $M2^{d(k)-1}$ to \eqref{Stirling}, where $M$ is odd.\\
\ \\
\textbf{Case 2 : $d(i)+d(j-i)+j-i+d(k-j)-2 = d(k)-1$.}\\
\vspace*{2ex}\\
Since $d(i)+d(j-i)+d(k-j)\geq d(k)$ and $j\geq i$, this situation
can occur only when $j=i+1$ and $d(i)+d(k-i-1)=d(k)-1$ or when
$j=i$ and $d(i)+d(k-i)=d(k)+1$.\\
\vspace*{2ex}\\
\textbf{$\text{ }\ \text{ }\ $Case 2.1 : $d(i)+d(k-i-1) = d(k)-1$ and $j=i+1$.}\\
\vspace*{2ex}\\
Since $d(k - 1) \leq d(i) + d(k - i - 1) = d(k) - 1$, $k$ must be
odd. We have $d(i)+d((k-1)-i) = d(k-1)$.  As in Case 1, there are
$2^{d(k-1)}$ possible values for $i$ (the case $i=k$ doesn't occur
and the case $i=0$ and $j=1$ is allowed). This is
an even number of terms since $k \neq 1$.\\
\vspace*{2ex}\\
\textbf{$\text{ }\ \text{ }\ $Case 2.2 : $d(i)+d(k-i) = d(k)+1$ and $j=i$.}\\
\vspace*{2ex}\\
By Lemma 1 this can occur only when there is just one value of
$\lambda \in \mathbb{N}$ for which
$\varepsilon_\lambda(i)=\varepsilon_\lambda(k-i)=1$. Moreover one
must have
$\varepsilon_{\lambda+1}(i)=\varepsilon_{\lambda+1}(k-i)=0$.  This
implies that $\varepsilon_\lambda(k)=0$ and
$\varepsilon_{\lambda+1}(k)=1$.  Following the same reasoning as
in Case 1 with the remaining $d(k)-1$ non-zero binary digits of
$k$, we have $2^{d(k)-1}$ possibilities for $i$ (the cases $i=0$
and $i=k$ don't occur).\\
So there are $2^{d(k)-1}$ terms in  \eqref{Stirling} which come
under Case 2.2 (and thus have $2$-adic valuation $d(k) - 1$). When
$d(k) = 1$, this number is 1, otherwise it is even.
\vspace*{3ex}\\
After considering all the possible cases and counting the number
of terms with $2$-adic valuation $d(k)-2$ and $2$-adic valuation
$d(k)-1$, we can conclude that $\rho_2(S(2^n,k))=d(k)-1$.  An
overview of all the cases is given in the following table.\\
\begin{table}[!th]
\begin{tabular}{|l|c|c|c|c|}
\hline
&&&&\\
\textbf{} &  $\textbf{Case 1}\atop{\text{ }\atop \text{coefficient
of }2^{d(k)-2}}$& $\textbf{Case 2.1}\atop{\text{ }\atop
\text{coefficient of }2^{d(k)-1}}$& $\textbf{Case 2.2}\atop{\text{
}\atop \text{coefficient of }2^{d(k)-1}}$
&  \textbf{coefficient of }$\mathbf{ 2^{d(k)-1}}$  \\
&&&&\\
\hline
&&&&\\
$\mathbf{d(k)=1\ (k\neq 1)}$  & 0 & 0 & odd & odd \\
&&&&\\
$\mathbf{d(k)>1\ \&\ k\ \textbf{odd}}$  & 2 x odd & even & even & odd \\
&&&&\\
$\mathbf{d(k)>1\ \&\ k\ \textbf{even}}$  & 2 x odd & 0 & even & odd \\
&&&&\\
\hline
\end{tabular}
\end{table}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                                                                %
%  Acknowledgments                                                                                               %
%                                                                                                                %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section*{\normalsize Acknowledgments}
%I would like to thank Miche\'{a}l \'{O} Searc\'{o}id, Frank De
%Clerck and Tam\'{a}s Lengyel for their comments on a previous
%version of these results.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                                                                %
%  THE BIBLIOGRAPHY                                                                                              %
%                                                                                                                %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{999}
\bibitem{WAN} {\bf S. De Wannemacker},
{\em Polynomials annihilating the Witt ring and $2$-adic valuation
of Stirling numbers}, Math. Nachr. (to appear).
\bibitem{GKP} {\bf R. L. Graham, D. E. Knuth, O. Patashnik},
{\em Concrete Mathematics, a foundation for computer science},
Addison Wesley, 1989.
\bibitem{LEN} {\bf T. Lengyel},
{\em On the divisibility by 2 of the Stirling numbers of the
second kind}, The Fibonacci Quarterly {\bf 32}, 1994, \mbox{pp.
194--201}.
\bibitem{COM} {\bf L. Comtet},
{\em Advanced Combinatorics}, D. Reidel, 1974.
\end{thebibliography}
\end{document}