References: Rosen 8e §6.4; Graham–Knuth–Patashnik, Concrete Mathematics, ch. 5; Tucker §5.5; Aigner, A Course in Enumeration.
2 / 32
1. Recap — $\binom{n}{k}$ and the two kinds of proof
For integers $0 \leq k \leq n$:
$$\binom{n}{k} \;=\; \frac{n!}{k!\,(n-k)!}.$$
This counts the number of $k$-subsets of an $n$-element set. By convention $\binom{n}{k} = 0$ when $k < 0$ or $k > n$.
An identity $A = B$ between two combinatorial quantities can be proved two complementary ways:
Algebraic proof. Manipulate the factorial / polynomial form until both sides agree.
Combinatorial proof (bijective or double-count). Exhibit a finite set $S$ such that $|S| = A$ counted one way and $|S| = B$ counted another. Equality of the two counts is automatic.
Combinatorial proofs are often shorter, more illuminating and easier to generalise — they make the formula explain something rather than just compute. We give both forms whenever both are natural.
Rosen 8e §6.4; Concrete Mathematics §5.1.
3 / 32
2. Symmetry identity
For $0 \leq k \leq n$, $\;\displaystyle \binom{n}{k} = \binom{n}{n-k}.$
Combinatorial. Choosing $k$ elements to keep from an $n$-set is the same as choosing the $n - k$ elements to discard. The map $S \mapsto S^c$ (complement) is a bijection between $k$-subsets and $(n-k)$-subsets, so both classes have the same size. $\square$
$\binom{20}{7} = \binom{20}{13} = 77\,520$. Symmetry halves the workload when computing entries of Pascal's triangle: only the left half need be stored.
Rosen 8e §6.4 Corollary 1.
4 / 32
3. Pascal's identity
For $1 \leq k \leq n$:
$$\binom{n}{k} \;=\; \binom{n-1}{k-1} \;+\; \binom{n-1}{k}.$$
Combinatorial. Distinguish a fixed element $a$ of an $n$-set $S$. Every $k$-subset of $S$ either contains $a$ or does not:
Contains $a$: choose $k - 1$ more elements from $S \setminus \{a\}$ — $\binom{n-1}{k-1}$ subsets.
Excludes $a$: choose all $k$ from $S \setminus \{a\}$ — $\binom{n-1}{k}$ subsets.
The two classes are disjoint and exhaust the $k$-subsets, so by the sum rule the count is $\binom{n-1}{k-1} + \binom{n-1}{k}$. $\square$
Pascal's identity is the recurrence that builds Pascal's triangle (next slide).
Rosen 8e §6.4 Theorem 2.
5 / 32
4. Pascal's triangle — patterns
Row $n$
Entries
$0$
1
$1$
1
1
$2$
1
2
1
$3$
1
3
3
1
$4$
1
4
6
4
1
$5$
1
5
10
10
5
1
$6$
1
6
15
20
15
6
1
Hidden patterns
Row symmetry (slide 4): each row reads the same backwards.
Row sum: the entries of row $n$ sum to $2^n$ (slide 9).
Fibonacci numbers appear as sums along the rising diagonals: $1, 1, 1+1, 1+2, 1+3+1, 1+4+3, \dots = 1, 1, 2, 3, 5, 8, \dots$
Hockey-stick / Christmas-stocking: the diagonal sum from any entry slants down to its hockey-stick value (slide 17).
Sierpinski triangle: shading the odd entries reveals a fractal — entry $\binom{n}{k}$ is odd iff every binary bit of $k$ is also a bit of $n$ (Kummer / Lucas).
Rosen 8e §6.4; Concrete Mathematics §5.1.
6 / 32
5. Absorption identity
For $1 \leq k \leq n$:
$$k \binom{n}{k} \;=\; n \binom{n-1}{k-1}.$$
Combinatorial (committee–chairperson). Count pairs $(S, c)$ where $S$ is a $k$-subset of $\{1, \dots, n\}$ and $c \in S$ is a distinguished chairperson. Side 1 — choose the committee, then the chair. $\binom{n}{k}$ committees, each gives $k$ chairs $\Rightarrow$ $k \binom{n}{k}$ pairs. Side 2 — choose the chair, then the other members. $n$ chairs, then $\binom{n-1}{k-1}$ ways for the remaining $k - 1$ members $\Rightarrow$ $n \binom{n-1}{k-1}$ pairs. Equate. $\square$
Algebraic. $k \binom{n}{k} = k \cdot \dfrac{n!}{k!(n-k)!} = \dfrac{n!}{(k-1)!(n-k)!} = n \cdot \dfrac{(n-1)!}{(k-1)!(n-k)!} = n \binom{n-1}{k-1}$. $\square$
Reading the identity right-to-left gives $\binom{n}{k} = \dfrac{n}{k} \binom{n-1}{k-1}$ — a recurrence used to compute $\binom{n}{k}$ along a single row very efficiently.
Concrete Mathematics §5.1 (5.5).
7 / 32
6. Binomial theorem — central result
For any $x, y$ and integer $n \geq 0$:
$$(x + y)^n \;=\; \sum_{k=0}^{n} \binom{n}{k}\, x^{k}\, y^{n-k}.$$
Combinatorial. Expand $(x+y)^n = (x+y)(x+y) \cdots (x+y)$ — $n$ factors. Distributing yields $2^n$ monomials, each a product of one $z_i \in \{x, y\}$ per factor. The monomial $x^{k} y^{n-k}$ arises from choosing $k$ factors that contribute $x$ — there are $\binom{n}{k}$ such choices. Collecting like terms gives the formula. $\square$
Inductive. Base $n = 0$: $(x+y)^0 = 1 = \binom{0}{0} x^0 y^0$. Step:
$(x+y)^{n+1} = (x + y)(x+y)^n = (x+y)\sum_{k} \binom{n}{k} x^k y^{n-k}.$ Distributing and re-indexing,
the coefficient of $x^k y^{n+1-k}$ is $\binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k}$ by Pascal. $\square$
$(1 + x)^n = \sum_k \binom{n}{k} x^k$. Coefficient of $x^5$ in $(2+x)^{12}$ is $\binom{12}{5} \cdot 2^{7} = 792 \cdot 128 = 101\,376$.
Proof 1 — binomial theorem. Set $x = y = 1$ in $(x + y)^n = \sum_k \binom{n}{k} x^k y^{n-k}$:
$2^n = \sum_k \binom{n}{k}$. $\square$
Proof 2 — combinatorial. Both sides count the number of subsets of an $n$-element set. Left: classify subsets by size $k$ — there are $\binom{n}{k}$ subsets of size $k$. Right: each of the $n$ elements is independently "in" or "out" of the subset — $2^n$ total. $\square$
For every $n \geq 1$:
$$\sum_{k=0}^{n} (-1)^k \binom{n}{k} \;=\; 0.$$
Algebraic. Set $x = -1$ and $y = 1$ in the binomial theorem: $(1 - 1)^n = 0$ for $n \geq 1$. Expanding gives $\sum_k \binom{n}{k} (-1)^k \cdot 1^{n-k} = 0$. $\square$
Combinatorial — involution. Let $E$ = even-size subsets of $\{1, \dots, n\}$, $O$ = odd-size subsets. We show $|E| = |O|$. Fix the element $1 \in \{1, \dots, n\}$ (we assume $n \geq 1$). Define $\varphi : E \cup O \to E \cup O$ by $\varphi(S) = S \mathbin{\triangle} \{1\}$ (toggle membership of $1$). Then $\varphi$ is its own inverse (an involution) and it swaps subsets of even size with subsets of odd size. So $|E| = |O|$, hence $|E| - |O| = \sum_k (-1)^k \binom{n}{k} = 0$. $\square$
Combining with $\sum \binom{n}{k} = 2^n$ gives $\sum_{k\text{ even}} \binom{n}{k} = \sum_{k\text{ odd}} \binom{n}{k} = 2^{n-1}$ for $n \geq 1$.
Algebraic. Set $x = 2, y = 1$ in $(x + y)^n = \sum \binom{n}{k} x^k y^{n-k}$:
$(2 + 1)^n = 3^n = \sum 2^k \binom{n}{k}$. $\square$
Combinatorial. Count the number of ways to label each of $n$ items with one of three colours $\{R, G, B\}$. Right side. Each of the $n$ items has $3$ choices $\Rightarrow$ $3^n$ labellings. Left side. First choose the subset of items that will be labelled non-$R$ — say there are $k$ such items, with $\binom{n}{k}$ choices. Each of those $k$ items takes one of two colours ($G$ or $B$) $\Rightarrow$ $2^k$ ways. Sum over $k$: $\sum 2^k \binom{n}{k}$. $\square$
More generally, $\sum_{k=0}^{n} a^k \binom{n}{k} = (1+a)^n$ for any $a$.
Rosen 8e §6.4 Ex. 13.
11 / 32
10. $\sum k \binom{n}{k} = n\,2^{n-1}$
$\displaystyle \sum_{k=0}^{n} k \binom{n}{k} \;=\; n \cdot 2^{n-1}.$
Combinatorial (chair–committee, sum form). Count pairs $(S, c)$ with $c \in S \subseteq \{1, \dots, n\}$ (no size restriction). Side 1 — by committee size. A committee of size $k$ contributes $\binom{n}{k} \cdot k$ pairs (the committee, then the chair). Sum over $k$: $\sum_k k \binom{n}{k}$. Side 2 — by chair first. Choose the chair in $n$ ways. The remaining $n - 1$ people are independently in/out, giving $2^{n-1}$ committees. Total: $n \cdot 2^{n-1}$. Equate. $\square$
Algebraic. Differentiate $(1+x)^n = \sum \binom{n}{k} x^k$ with respect to $x$:
$n(1+x)^{n-1} = \sum_k k \binom{n}{k} x^{k-1}.$
Set $x = 1$: $n \cdot 2^{n-1} = \sum k \binom{n}{k}$. $\square$
Average size of a uniformly random subset of $\{1, \dots, n\}$:
$\dfrac{\sum_k k \binom{n}{k}}{2^n} = \dfrac{n \cdot 2^{n-1}}{2^n} = \dfrac{n}{2}$ — half the elements, as expected.
Algebraic. Differentiate $(1+x)^n = \sum \binom{n}{k} x^k$ twice and multiply by $x$ tactically.
Apply the operator $x\,\tfrac{d}{dx}$: $\sum k \binom{n}{k} x^k = x \cdot n (1+x)^{n-1}$.
Apply it again: $\sum k^2 \binom{n}{k} x^k = x \cdot \tfrac{d}{dx}\bigl[\,x \cdot n(1+x)^{n-1}\,\bigr] = nx(1+x)^{n-1} + n(n-1)x^2(1+x)^{n-2}.$
Set $x = 1$: $\sum k^2 \binom{n}{k} = n \cdot 2^{n-1} + n(n-1) \cdot 2^{n-2} = 2^{n-2}\bigl[2n + n(n-1)\bigr] = 2^{n-2} \cdot n(n+1)$. $\square$
Variance of the size $K$ of a uniformly random subset of $\{1, \dots, n\}$: $\mathbb{E}[K^2] = n(n+1)/4$ and $\mathbb{E}[K] = n/2$, so $\mathrm{Var}(K) = n(n+1)/4 - n^2/4 = n/4$ — confirming $K \sim \text{Binomial}(n, 1/2)$.
Concrete Mathematics §5.2.
13 / 32
12. Vandermonde identity
For non-negative integers $m, n, r$:
$$\binom{m + n}{r} \;=\; \sum_{k=0}^{r} \binom{m}{k} \binom{n}{r - k}.$$
Combinatorial. Count $r$-subsets of $\{1, 2, \dots, m + n\}$. Split this set into a "left" part $L = \{1, \dots, m\}$ and a "right" part $R = \{m+1, \dots, m+n\}$. Any $r$-subset $T$ takes $k$ elements from $L$ and $r - k$ from $R$ for some $0 \leq k \leq r$. The number of such pairs is $\binom{m}{k} \binom{n}{r-k}$. Summing over $k$ counts every $r$-subset exactly once. $\square$
Algebraic. Coefficient of $x^r$ in $(1+x)^{m+n}$ is $\binom{m+n}{r}$. But $(1+x)^{m+n} = (1+x)^m (1+x)^n$. The Cauchy product of the two binomial expansions gives, for the coefficient of $x^r$:
$\sum_{k} \binom{m}{k} \binom{n}{r-k}$. Equate the two coefficients. $\square$
Setting $m = n = r$ and using symmetry $\binom{n}{r - k} = \binom{n}{n - r + k}$ does not give a special identity directly; but setting $m = n, r = n$ does (see slide 16).
Rosen 8e §6.4 Theorem 4.
14 / 32
12.bis Worked example — Vandermonde in action
A florist has $15$ roses and $15$ lavender flowers. Customer wants a bouquet of $10$ flowers.
How many bouquets with exactly $3$ roses and $7$ lavenders?
$\binom{15}{3} \binom{15}{7} = 455 \cdot 6\,435 = 2\,927\,925$.
How many bouquets with $1$ to $3$ roses?
$\sum_{k=1}^{3} \binom{15}{k}\binom{15}{10-k} = 15 \cdot \binom{15}{9} + \binom{15}{2}\binom{15}{8} + \binom{15}{3}\binom{15}{7} = 75\,075 + 675\,675 + 2\,927\,925 = 3\,678\,675$.
How many bouquets of $10$ flowers in total?
By Vandermonde, $\displaystyle \sum_{k=0}^{10} \binom{15}{k}\binom{15}{10-k} = \binom{30}{10} = 30\,045\,015$.
Combinatorial. Set $m = n$ and $r = n$ in Vandermonde:
$\binom{2n}{n} = \sum_k \binom{n}{k}\binom{n}{n-k} = \sum_k \binom{n}{k}^2$
using symmetry $\binom{n}{n-k} = \binom{n}{k}$. $\square$
$\sum_{k=0}^{5} \binom{5}{k}^2 = 1 + 25 + 100 + 100 + 25 + 1 = 252 = \binom{10}{5}$. ✓
Combinatorial meaning: number of ways to choose $n$ items from a set of $2n$ split into two halves — must take $k$ from one half and $n - k$ from the other.
Concrete Mathematics §5.1 (5.23).
16 / 32
14. Hockey-stick identity
For $0 \leq r \leq n$:
$\displaystyle \sum_{i=r}^{n} \binom{i}{r} \;=\; \binom{n+1}{r+1}.$
Combinatorial. Count $(r+1)$-subsets of $\{1, 2, \dots, n+1\}$. Classify each such subset by its largest element, call it $i + 1$. The remaining $r$ elements are chosen from $\{1, \dots, i\}$ — $\binom{i}{r}$ ways. The largest element ranges over $r+1, r+2, \dots, n+1$, i.e. $i \in \{r, r+1, \dots, n\}$. Summing: $\sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1}$. $\square$
Inductive. Base $n = r$: $\binom{r}{r} = 1 = \binom{r+1}{r+1}$. Step: assume at $n$. Then
$\sum_{i=r}^{n+1}\binom{i}{r} = \binom{n+1}{r+1} + \binom{n+1}{r} = \binom{n+2}{r+1}$ by Pascal's identity. $\square$
Visually in Pascal's triangle, the identity traces a "hockey stick": start at row $r$, slide diagonally down, the sum lies one step below-and-out — the blade of the stick.
Rosen 8e §6.4 Theorem 5.
17 / 32
15. Negative-binomial extension
For any real $\alpha$ and integer $k \geq 0$, define
$$\binom{\alpha}{k} \;:=\; \frac{\alpha (\alpha - 1) \cdots (\alpha - k + 1)}{k!}.$$
For $\alpha = n$ a non-negative integer this reduces to the usual binomial; for negative $\alpha$ it makes sense and obeys the same algebra.
Generalised binomial theorem (Newton). For $|x| < 1$ and any real $\alpha$:
$(1 + x)^{\alpha} \;=\; \sum_{k=0}^{\infty} \binom{\alpha}{k} x^k.$
For positive integer $r$ and $k \geq 0$:
$\binom{-r}{k} \;=\; (-1)^k \binom{r + k - 1}{k}.$
This identity is the heart of the negative binomial series $(1 - x)^{-r} = \sum_k \binom{r+k-1}{k} x^k$ — counting multisets of size $k$ from $r$ types (stars and bars again).
Concrete Mathematics §5.3; Newton, De Methodis Serierum et Fluxionum.
18 / 32
16. Catalan numbers from binomials
The $n$-th Catalan number is
$C_n \;:=\; \dfrac{1}{n+1} \binom{2n}{n} \;=\; \binom{2n}{n} - \binom{2n}{n+1}.$
First terms: $C_0 = 1$, $C_1 = 1$, $C_2 = 2$, $C_3 = 5$, $C_4 = 14$, $C_5 = 42$, $C_6 = 132$, $C_7 = 429$.
$C_n$ counts an astonishing number of structures: triangulations of an $(n+2)$-gon; Dyck paths of length $2n$; balanced parenthesisations of $n$ pairs; rooted binary trees with $n$ internal nodes; and many more (Stanley's Enumerative Combinatorics, vol. 2, lists over $200$).
Stanley, EC2, exercise 6.19; OEIS A000108.
19 / 32
17. Multinomial extension
For non-negative integers $k_1, \dots, k_r$ summing to $n$:
$\binom{n}{k_1, k_2, \dots, k_r} \;:=\; \frac{n!}{k_1!\,k_2! \cdots k_r!}.$
Pick a distinguished element of the $n$-set; it ends up in exactly one of the $r$ classes — say class $i$. The number of ways to partition the remaining $n - 1$ elements into classes of sizes $k_1, \dots, k_i - 1, \dots, k_r$ is the term. Summing over $i$ covers all cases. $\square$
Coefficient of $x^2 y^3 z$ in $(x + y + z)^6$ is $\binom{6}{2, 3, 1} = 60$. The trinomial expansion of $(x+y+z)^4$ has $\binom{4+2}{2} = 15$ terms.
Rosen 8e §6.4 Theorem 3.
20 / 32
18. Generating-function preview
The ordinary generating function (OGF) of a sequence $(a_n)$ is the formal power series $A(x) = \sum_{n \geq 0} a_n x^n$. Identities between sequences become identities between power series.
The binomial theorem says $\sum_n \binom{r}{n} x^n = (1+x)^r$. From this seed, three more identities pop out at once:
Generating functions are studied in depth in a later course (Concrete Mathematics, ch. 7); for now they provide a slick way to verify any of the identities we have proved.
Most identities on this lesson reduce to one of three combinatorial schemata:
Double counting
Count the same finite set $S$ in two different ways — both expressions for $|S|$ must agree.
Bijection
Exhibit a bijection $\varphi : A \to B$ between sets of sizes $|A|, |B|$; conclude $|A| = |B|$.
Involution
Find a self-inverse map $\varphi : X \to X$ with no fixed points that swaps an even-coloured element with an odd-coloured one — conclude $|X_{\text{even}}| = |X_{\text{odd}}|$.
Double-counting proved $k \binom{n}{k} = n \binom{n-1}{k-1}$ (slide 7) and $\sum k \binom{n}{k} = n 2^{n-1}$ (slide 12). Bijection proved $\binom{n}{k} = \binom{n}{n-k}$ (slide 4) via complementation. Involution proved $\sum (-1)^k \binom{n}{k} = 0$ (slide 10) via the toggle map.
When you see a binomial identity, ask: "What is being counted?" If both sides count the same thing two ways, the identity is essentially proved.
Aigner, A Course in Enumeration, ch. 1; Concrete Mathematics §5.2.
22 / 32
20. Worked example — Maeve's portfolio
Maeve invests $1$ unit in each of $8$ stock options out of $20$ offered.
(a) Total portfolios? $\binom{20}{8} = 125\,970$.
(b) Maeve has a favourite stock and picks it first. The remaining $7$ stocks come from the other $19$. Portfolio count: $\binom{19}{7} = 50\,388$.
(c) Portfolios that exclude the favourite stock? Same recipe: $\binom{19}{8} = 75\,582$.
$\displaystyle \sum_{k=0}^{n} k \binom{n}{k}^2 \;=\; n \binom{2n-1}{n-1}.$
Use absorption (slide 7) on the left, then Vandermonde:
$\sum_k k \binom{n}{k}\binom{n}{k} = \sum_k n \binom{n-1}{k-1}\binom{n}{k} = n \sum_k \binom{n-1}{k-1}\binom{n}{n-k} = n \binom{2n-1}{n-1}.$
The last step is Vandermonde with $m = n - 1, r = n - 1$, after re-indexing $k' = k - 1$. $\square$
By Vandermonde with $m = n$, $r = n - 1$:
$\binom{2n}{n-1} = \sum_k \binom{n}{k}\binom{n}{n-1-k} = \sum_k \binom{n}{k}\binom{n}{k+1}$
using symmetry $\binom{n}{n-1-k} = \binom{n}{k+1}$ (where the index shift accounts for $n - 1 - k = n - (k+1)$). $\square$
Concrete Mathematics §5.1 exercises.
25 / 32
23. Discovering identities with SymPy
Python — importsfrom sympy import symbols, binomial, Sum, simplify, factor, oo
n, k = symbols('n k', integer=True, nonnegative=True)
SymPy — verify Vandermonde for specific m, n, rm_val, n_val, r_val = 8, 12, 5
lhs = binomial(m_val + n_val, r_val)
rhs = sum(binomial(m_val, j) * binomial(n_val, r_val - j) for j in range(r_val + 1))
print(lhs, rhs, lhs == rhs) # 15504 15504 True
SymPy uses Gosper's algorithm and the Wilf–Zeilberger pair method to evaluate many binomial sums in closed form automatically — a remarkable XX-th-century achievement.
Petkovsek–Wilf–Zeilberger, A = B, 1996.
26 / 32
24. Common pitfalls
Index-shift errors. When applying Vandermonde, double-check that $k$ and $r - k$ both range over valid indices: both must satisfy $0 \leq k \leq r$ and $0 \leq r - k \leq n$. Outside this range, $\binom{m}{k} = 0$ — terms vanish but the bookkeeping must still be right.
Forgetting the base case. When proving an identity by induction on $n$, always handle $n = 0$ (or the smallest applicable $n$) explicitly. Many identities (like the alternating-sum) are vacuous or "$0/0$" at $n = 0$.
Confusing $\sum_{k} \binom{n}{k}^2$ with $\bigl(\sum_k \binom{n}{k}\bigr)^2$. They are not equal:
$\bigl(2^n\bigr)^2 = 4^n,\qquad \binom{2n}{n} \approx \frac{4^n}{\sqrt{\pi n}}$ (Stirling). The squared row-sum is much larger.
"Hockey-stick" wrong direction. The identity is
$\sum_{i = r}^{n} \binom{i}{r} = \binom{n+1}{r+1}$ — the lower index of $\binom{i}{r}$ varies; the upper index of $\binom{n+1}{r+1}$ rises by one. A common mistake is to vary the upper index instead.
Symmetry, Pascal, absorption — three foundational identities; each proved combinatorially and algebraically.
Binomial theorem — proved by counting monomials and by induction.
Row sum, alternating sum, weighted sums — proved with at least two methods each; the involution proof for the alternating sum is particularly clean.
Vandermonde & hockey-stick — proved combinatorially via classification by a chosen element.
Sum of squares $\sum \binom{n}{k}^2 = \binom{2n}{n}$ — special case of Vandermonde.
Negative binomial — extension to real / negative parameters via Newton's series.
Catalan numbers — appearance via $\binom{2n}{n}/(n+1)$.
Multinomial theorem generalises the binomial.
Three combinatorial-proof schemata: double-counting, bijection, involution.
29 / 32
27. Python / SymPy toolbox
Python — importsfrom math import comb, factorial
from sympy import binomial, Sum, symbols, simplify, oo, catalan
from sympy.functions.combinatorial.factorials import factorial as sym_fact
Python — numeric checksprint(comb(20, 8)) # 125970
print(sum(comb(15, k) for k in range(16))) # 32768 = 2**15
print(sum((-1)**k * comb(15, k) for k in range(16))) # 0
print(sum(k * comb(15, k) for k in range(16))) # 15 * 2**14 = 245760
print(sum(comb(15, k)**2 for k in range(16))) # comb(30,15) = 155117520
SymPy — Pascal triangle row generatordef pascal(n_max):
row = [1]
yield row
for n in range(1, n_max + 1):
row = [1] + [row[i] + row[i+1] for i in range(n-1)] + [1]
yield row
for r in pascal(7):
print(' '.join(str(x).rjust(3) for x in r))
30 / 32
28. Wolfram → Python quick reference
Operation
Wolfram
Python / SymPy
Binomial $\binom{n}{k}$
Binomial[n, k]
math.comb(n, k) · sympy.binomial(n, k)
Multinomial $\binom{n}{n_1,\ldots,n_r}$
Multinomial[n1, …]
factorial(n)//prod(factorial(ni) for ni in v)
Sum $\sum_k$ in closed form
Sum[Binomial[n,k]^2,{k,0,n}]
Sum(binomial(n,k)**2,(k,0,n)).doit()
$n$-th Catalan number
CatalanNumber[n]
sympy.catalan(n)
Pascal's triangle entry
PascalTriangle[n]
[comb(n, k) for k in range(n+1)]
Verify a binomial identity
FullSimplify[lhs - rhs]
simplify(lhs - rhs)
Falling factorial / Pochhammer
FactorialPower[n, k]
math.perm(n, k)
31 / 32
Bibliography
K. H. Rosen. Discrete Mathematics and Its Applications, 8th ed., McGraw-Hill, 2019 — §6.4 (binomial coefficients), §6.5 (multinomials).
R. L. Graham, D. E. Knuth, O. Patashnik. Concrete Mathematics, 2nd ed., Addison-Wesley, 1994 — ch. 5 (binomial coefficients) — the encyclopedia.
A. Tucker. Applied Combinatorics, 6th ed., Wiley, 2012 — §5.5.