The set $[A{]}^k$ of $k$-element subsets and the binomial coefficient $\left(\genfrac{}{}{0px}{}{n}{k}\right):=\mid [n{]}^k\mid$

For a finite set $A$ and $k\in \mathbb{N}$ put

$[A{]}^k:=\{S\subseteq A:\mid S\mid =k\},$

the set of $k$-element subsets of $A$. Every $S\subseteq A$ is finite (A subset of a finite set is finite, with $\mid B\mid \le \mid A\mid$, and equality holds if and only if $B=A$), so the condition $\mid S\mid =k$ makes sense for every subset.

$[A{]}^k$ is finite. It is a subset of $\mathcal{P}(A)$, which is finite by $\mid \mathcal{P}(A)\mid =2^{\mid A\mid }$ for finite $A$, so A subset of a finite set is finite, with $\mid B\mid \le \mid A\mid$, and equality holds if and only if $B=A$ applies.

$\mid [A{]}^k\mid$ depends only on $\mid A\mid$. Let $h:A\to A^{\mathrm{\prime }}$ be a bijection of finite sets. The direct image map $S\mapsto h[S]$ carries $[A{]}^k$ into $[A^{\mathrm{\prime }}{]}^k$, because $h$ restricted to $S$ is a bijection of $S$ onto $h[S]$ and so $\mid h[S]\mid =\mid S\mid =k$ by the transport clause of The cardinality $\mid A\mid$ of a finite set; the map $T\mapsto h^{-1}[T]$ is its two-sided inverse, since $h^{-1}[h[S]]=S$ and $h[h^{-1}[T]]=T$ for a bijection $h$. So $[A{]}^k\approx [A^{\mathrm{\prime }}{]}^k$ and the two have the same cardinality.

Definition. For $n,k\in \mathbb{N}$ set

$\left(\genfrac{}{}{0px}{}{n}{k}\right):=\mid [n{]}^k\mid \in \mathbb{N},$

the binomial coefficient. By the previous paragraph and $\mid n\mid =n$,

$\mid [A{]}^k\mid =\left(\genfrac{}{}{0px}{}{\mid A\mid }{k}\right)\text{for every finite }A\mathrm{.}$

$\left(\genfrac{}{}{0px}{}{n}{k}\right)$ is a count, so it is a natural number by construction. It is not defined as $n!\mathrm{/}(k!(n-k)!)$: that expression involves a division, hence lives in $\mathbb{R}$, and the assertion that its value is a natural number is a theorem, proved in $\left(\genfrac{}{}{0px}{}{n}{k}\right)k!(n-k)!=n!$ for $k\le n$; hence $\left(\genfrac{}{}{0px}{}{n}{k}\right)k!=n^{\underset{‾}{k}}$, the quotient $n!\mathrm{/}(k!(n-k)!)$ is a natural number, and $\left(\genfrac{}{}{0px}{}{n}{k}\right)=\left(\genfrac{}{}{0px}{}{n}{n-k}\right)$. Defining the coefficient as a count makes integrality free and leaves the closed formula something to prove.

Boundary values, read off the definition and not stipulated.

• $\left(\genfrac{}{}{0px}{}{n}{0}\right)=1$ for every $n$, including $n=0$: the subsets of $n$ of cardinality $0$ are exactly the subsets equal to $\mathrm{\varnothing }$ (The cardinality $\mid A\mid$ of a finite set, clause (b)), so $[n{]}^0=\{\mathrm{\varnothing }\}$, a one-element set. No empty-product convention is involved.
• $\left(\genfrac{}{}{0px}{}{n}{n}\right)=1$: if $S\subseteq n$ has $\mid S\mid =n=\mid n\mid$ then $S=n$ by clause 3 of A subset of a finite set is finite, with $\mid B\mid \le \mid A\mid$, and equality holds if and only if $B=A$, so $[n{]}^n=\{n\}$.
• $\left(\genfrac{}{}{0px}{}{n}{k}\right)=0$ for $k>n$: a subset $S\subseteq n$ has $\mid S\mid \le n$ by clause 2 of A subset of a finite set is finite, with $\mid B\mid \le \mid A\mid$, and equality holds if and only if $B=A$, so $\mid S\mid =k>n$ is impossible and $[n{]}^k=\mathrm{\varnothing }$ (Trichotomy of the order on $\mathbb{N}$).
• $\left(\genfrac{}{}{0px}{}{n}{1}\right)=n$: a subset of cardinality $1$ is $\{x\}$ for exactly one $x\in n$, since $\mid S\mid =1$ means $S\approx \{0\}$; so $S\mapsto$ its unique element is a bijection $[n{]}^1\to n$.
• $\left(\genfrac{}{}{0px}{}{0}{0}\right)=1$ and $\left(\genfrac{}{}{0px}{}{0}{k}\right)=0$ for $k\ge 1$, both instances of the above.

A subset of a finite set is finite, with $\mid B\mid \le \mid A\mid$, and equality holds if and only if $B=A$

$\mid \mathcal{P}(A)\mid =2^{\mid A\mid }$ for finite $A$

The cardinality $\mid A\mid$ of a finite set

$\left(\genfrac{}{}{0px}{}{n}{k}\right)k!(n-k)!=n!$ for $k\le n$; hence $\left(\genfrac{}{}{0px}{}{n}{k}\right)k!=n^{\underset{‾}{k}}$, the quotient $n!\mathrm{/}(k!(n-k)!)$ is a natural number, and $\left(\genfrac{}{}{0px}{}{n}{k}\right)=\left(\genfrac{}{}{0px}{}{n}{n-k}\right)$

Trichotomy of the order on $\mathbb{N}$

• Notation. $[A{]}^k$ is standard for the set of $k$-element subsets; it is unrelated to the notation $A^B$ for a set of functions, which appears on this page as well. Where confusion is possible the words are used in full.

• Symmetry is not visible yet. $\left(\genfrac{}{}{0px}{}{n}{k}\right)=\left(\genfrac{}{}{0px}{}{n}{n-k}\right)$ is proved in $\left(\genfrac{}{}{0px}{}{n}{k}\right)k!(n-k)!=n!$ for $k\le n$; hence $\left(\genfrac{}{}{0px}{}{n}{k}\right)k!=n^{\underset{‾}{k}}$, the quotient $n!\mathrm{/}(k!(n-k)!)$ is a natural number, and $\left(\genfrac{}{}{0px}{}{n}{k}\right)=\left(\genfrac{}{}{0px}{}{n}{n-k}\right)$ by exhibiting the complementation bijection $S\mapsto n\setminus S$; from the definition alone there is no reason for the two counts to agree.

• $0$ is a legitimate value of $k$ and of $n$. Every boundary clause above is checked at $0$, which is where a statement about binomial coefficients most often goes wrong in this library's index convention.