notes.tex

\section*{Stirling Numbers of the First Kind}

\subsection*{Definition}

The \textbf{Stirling number of the first kind} $s(n,k)$ counts the number of permutations of $n$ distinct elements that decompose into exactly $k$ disjoint cycles:
\[
\boxed{
s(n,k) = \text{number of permutations of } n \text{ elements with exactly } k \text{ cycles.}
}
\]

These numbers may also be signed as $s(n,k) = (-1)^{n-k} |s(n,k)|$, where $|s(n,k)|$ counts the number of permutations regardless of sign.

\subsection*{Cycles in a permutation}

A \textbf{cycle} is a component of a permutation that maps elements among themselves in a circular fashion.  
For example, in a permutation of $\{1,2,3,4\}$:
\[
\pi(1)=3,\ \pi(3)=1,\ \pi(2)=4,\ \pi(4)=2,
\]
we can write:
\[
\pi = (1\ 3)(2\ 4),
\]
which consists of two disjoint cycles: $(1\ 3)$ and $(2\ 4)$.

Thus, this permutation contributes to $s(4,2)$ since it has $2$ cycles.

\subsection*{Recurrence Relation}

The Stirling numbers of the first kind satisfy:
\[
\boxed{
s(n,k) = s(n-1,k-1) + (n-1)\,s(n-1,k)
}
\]
with base cases:
\[
s(0,0)=1, \quad s(n,0)=0 \ (n>0), \quad s(0,k)=0 \ (k>0).
\]

\paragraph{Interpretation.}
To build a permutation of $n$ elements:
\begin{itemize}
    \item[(1)] The new element $n$ may form a new cycle by itself, contributing $s(n-1,k-1)$.
    \item[(2)] Or it may be inserted into one of the existing $(n-1)$ positions in the cycles, contributing $(n-1)s(n-1,k)$.
\end{itemize}

\subsection*{Closed Form}

A closed expression using inclusion–exclusion is:
\[
\boxed{
s(n,k) = \frac{1}{k!} \sum_{j=0}^{k} (-1)^j \binom{n}{j} (k-j)^n.
}
\]

\subsection*{Example}

For $n=3$:
\[
\begin{aligned}
s(3,1) &= s(2,0) + 2s(2,1) = 0 + 2(1) = 2, \\
s(3,2) &= s(2,1) + 2s(2,2) = 1 + 2(1) = 3, \\
s(3,3) &= s(2,2) + 2s(2,3) = 1 + 0 = 1.
\end{aligned}
\]

\subsection*{Relation to Falling Factorials}

The falling factorial, also called the \textbf{lower factorial}, is defined as:
\[
(x)_k = x(x-1)(x-2)\cdots(x-k+1).
\]

Then, the Stirling numbers of the first kind appear in the expansion:
\[
(x)_n = \sum_{k=0}^{n} s(n,k)\,x^k,
\]
and conversely, the Stirling numbers of the second kind satisfy:
\[
x^n = \sum_{k=0}^{n} S(n,k)\,(x)_k.
\]

Thus, $s(n,k)$ and $S(n,k)$ form \textbf{inverse transformations} between the bases $\{x^k\}$ and $\{(x)_k\}$.

\subsection*{Difference Between Ordinary Powers and Falling Factorials}

\[
\begin{aligned}
x^k &= x \cdot x \cdot x \cdots x \quad (\text{k times}), \\
(x)_k &= x(x-1)(x-2)\cdots(x-k+1).
\end{aligned}
\]

\begin{center}
\begin{tabular}{c|c|c}
$k$ & $x^k$ & $(x)_k$ \\ \hline
0 & $1$ & $1$ \\
1 & $x$ & $x$ \\
2 & $x^2$ & $x^2 - x$ \\
3 & $x^3$ & $x^3 - 3x^2 + 2x$
\end{tabular}
\end{center}

\noindent
Hence, Stirling numbers of both kinds describe the conversion between these two polynomial forms:
\[
\boxed{
\begin{aligned}
x^n &= \sum_{k=0}^{n} S(n,k)\,(x)_k, \\
(x)_n &= \sum_{k=0}^{n} s(n,k)\,x^k.
\end{aligned}
}
\]


\section*{Stirling Numbers of the Second Kind}

\subsection*{Definition}

The \textbf{Stirling number of the second kind} $S(n,k)$ counts the number of ways to partition a set of $n$ distinct elements into $k$ non-empty, unlabeled subsets:
\[
\boxed{
S(n,k) = \text{number of ways to partition } \{1,2,\dots,n\} \text{ into } k \text{ non-empty subsets.}
}
\]

\subsection*{Recurrence Relation}

The Stirling numbers of the second kind satisfy:
\[
\boxed{
S(n,k) = S(n-1,k-1) + k\,S(n-1,k)
}
\]
with base cases:
\[
S(0,0)=1, \quad S(n,0)=0 \ (n>0), \quad S(0,k)=0 \ (k>0).
\]

\paragraph{Interpretation.}
To build a partition of $n$ elements:
\begin{itemize}
    \item[(1)] The new element $n$ may form a new subset by itself, contributing $S(n-1,k-1)$.
    \item[(2)] Or it may be added to one of the existing $k$ subsets, contributing $kS(n-1,k)$.
\end{itemize}

\subsection*{Closed Forms}

Two equivalent closed forms exist:
\[
\boxed{
S(n,k) = \frac{1}{k!} \sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^n
}
\]
and equivalently,
\[
\boxed{
S(n,k) = \frac{1}{k!} \sum_{j=0}^{k} (-1)^j \binom{k}{j} (k-j)^n.
}
\]

\subsection*{Relation to Bell Numbers}

The total number of partitions of a set of size $n$ (the $n$-th Bell number) is:
\[
B_n = \sum_{k=0}^{n} S(n,k).
\]


\section*{Lucas' Theorem}

\subsection*{General Statement}

Let $p$ be a prime number, and let $n,k \ge 0$ with base-$p$ expansions:
\[
n = n_0 + n_1p + n_2p^2 + \cdots + n_rp^r, \qquad
k = k_0 + k_1p + k_2p^2 + \cdots + k_rp^r,
\]
where $0 \le n_i, k_i < p$.

Then:
\[
\boxed{
\binom{n}{k} \equiv \prod_{i=0}^{r} \binom{n_i}{k_i} \pmod{p}.
}
\]

If any $k_i > n_i$, then $\binom{n_i}{k_i} = 0$, so the entire product is $0$.

\subsection*{Special Case: $p = 2$}

When $p = 2$, the digits $n_i, k_i \in \{0,1\}$ are the binary bits of $n$ and $k$:
\[
\binom{n}{k} \equiv \prod_{i=0}^{r} \binom{n_i}{k_i} \pmod{2}.
\]

Since $\binom{n_i}{k_i} \equiv 1 \pmod{2}$ if and only if $k_i \le n_i$, we have:
\[
\boxed{
\binom{n}{k} \text{ is odd } \iff k_i \le n_i \text{ for all bits } i.
}
\]

Equivalently, in bitwise form:
\[
\boxed{
\binom{n}{k} \text{ is odd } \iff (k \,\&\, \sim n) = 0
\iff (n \,\&\, k) = k.
}
\]

Thus, $\binom{n}{k}$ is odd if and only if $k$ is a \textbf{submask} of $n$ in binary.

\paragraph{Corollaries.}
\begin{itemize}
    \item The parity pattern of Pascal's triangle (mod 2) forms the \textbf{Sierpiński triangle}.
    \item $\binom{n}{k} \bmod 2 = 1$ exactly when $k$'s bits are contained in $n$'s bits.
\end{itemize}

\subsection*{Bitmask Relations}

Two equivalent bitwise characterizations of ``$k$ is a submask of $n$'':
\[
(k \,\&\, \sim n) = 0 \quad \Longleftrightarrow \quad (n \,\&\, k) = k.
\]

Both mean that every bit set in $k$ is also set in $n$.

\subsection*{Iterating Over Submasks in C++}

\textbf{Code pattern:}
\begin{verbatim}
for (int sub = mask; ; sub = (sub - 1) & mask) {
    // use sub (it is a submask of mask)
    if (sub == 0) break;
}
\end{verbatim}