The isomorphism theorems
For a homomorphism \(\varphi\colon G\to H\), the first isomorphism theorem gives \(G/\ker\varphi\cong\im\varphi\). The second theorem compares a subgroup \(H\le G\) with a normal subgroup \(N\normal G\): \(HN/N\cong H/(H\intersect N)\). The third theorem compares nested normal subgroups \(K\le N\) of \(G\): \((G/K)/(N/K)\cong G/N\). The correspondence theorem identifies the subgroups of \(G/N\) with the subgroups of \(G\) containing \(N\).
First isomorphism theorem for groups (Tag T-I5N43)
Let \(\phi\colon G\to H\) be a group homomorphism. Then \(\ker \phi\) is a normal subgroup of \(G\), \(\im \phi\) is a subgroup of \(H\), and \[ G/\ker \phi \to \im \phi,\qquad g\ker\phi\mapsto\phi(g), \] is a well-defined group isomorphism.
For \(x\in\ker\phi\) and \(g\in G\), \(\phi(gxg^{-1})=\phi(g)\phi(g)^{-1}=e\), so \(\ker\phi\normal G\); \(\im\phi\) is the image of a group under a homomorphism, hence a subgroup of \(H\). The map is well defined and injective because \(\phi(g)=\phi(g')\) if and only if \(g^{-1}g'\in\ker\phi\), it is surjective by construction, and it is a homomorphism because \(\phi\) is.
Second isomorphism theorem for groups (Tag T-NFQBO)
Let \(G\) be a group, \(S \leq G\) a subgroup, and \(N \normal G\) a normal subgroup. Then \[ \frac{SN}{N} \cong \frac{S}{S\intersect N}. \] If \(S\) and \(N\) are finite, then \[ \abs{SN} = \frac{\abs S \abs N}{\abs{S\intersect N}}. \]
Correspondence and third isomorphism theorems (Tag T-6CQEB)
Let \(G\) be a group and \(N\normal G\) a normal subgroup.
If \(N\leq K\leq G\), then \(K/N\) is a subgroup of \(G/N\).
For \(N\leq K\leq G\), \(K\normal G\) if and only if \(K/N\normal G/N\).
The map \(K\mapsto K/N\) is a bijection from the subgroups \(K\) of \(G\) containing \(N\) to the subgroups of \(G/N\), and it restricts to a bijection between normal subgroups.
If \(N\leq K\) and \(K\normal G\), then \[ \frac{G/N}{K/N} \cong \frac{G}{K}. \]
Let \(\pi\colon G\to G/N\) be the quotient map. (a) \(K/N=\pi(K)\) is the image of a subgroup. (c) The inverse of \(K\mapsto\pi(K)\) is \(\bar K\mapsto\pi^{-1}(\bar K)\): \(\pi^{-1}(\bar K)\) is a subgroup containing \(N\), \(\pi(\pi^{-1}(\bar K))=\bar K\) since \(\pi\) is surjective, and \(\pi^{-1}(\pi(K))=KN=K\) since \(N\leq K\). (b) Since \(\pi(gKg^{-1})=\pi(g)\pi(K)\pi(g)^{-1}\) and \(\pi\) is a bijection on subgroups containing \(N\), \(gKg^{-1}=K\) for all \(g\in G\) if and only if \(\bar g(K/N)\bar g^{-1}=K/N\) for all \(\bar g\in G/N\); this also gives the second half of (c). (d) The map \(G/N\to G/K\), \(gN\mapsto gK\), is well defined because \(N\leq K\), and it is a surjective homomorphism with kernel \(K/N\); apply the first isomorphism theorem.
Correspondence theorem for groups (Tag T-RLVA4)
Let \(G\) be a group, \(N \normal G\) a normal subgroup, and \(\pi\colon G\to G/N\) the quotient map. Then \[ \theset{H \leq G \suchthat N \subseteq H} \mapstofrom \theset{\overline{H} \suchthat \overline{H} \leq G/N}, \qquad H \mapsto H/N, \qquad \pi^{-1}(\overline{H}) \mapsfrom \overline{H}, \] are mutually inverse bijections between the subgroups of \(G\) containing \(N\) and the subgroups of the quotient group \(G/N\).
Products
A group \(G\) is the internal direct product of subgroups \(H\) and \(K\) if \(H,K\normal G\), \(H\intersect K=1\), and \(HK=G\); then \(hk=kh\) for all \(h\in H\), \(k\in K\), and \(G\cong H\times K\). If only \(N\normal G\) is normal, \(H\le G\), \(N\intersect H=1\), and \(NH=G\), then conjugation defines a homomorphism \(\psi\colon H\to\Aut(N)\), \(\psi(h)(n)=hn\inverseof{h}\), and \(G\cong N\semidirect_\psi H\). In particular, when a Sylow subgroup \(N\) of \(G\) is normal and has a complement \(H\), the isomorphism type of \(G\) is determined by \(N\), \(H\), and \(\psi\).
The product $HK$ is a subgroup when $H$ normalizes $K$ (Tag PR-BEIVF)
Let \(G\) be a group and \(H, K \leq G\) subgroups with \(H \leq N_G(K)\), where \(N_G(K)\) is the normalizer of \(K\). Then \(HK = \theset{hk \st h \in H,\ k \in K}\) is a subgroup of \(G\). In particular, this holds when \(K \normal G\).
Chinese remainder theorem (Tag T-TTZ2Y)
Let \(p\) and \(q\) be positive integers with \(\gcd(p, q) = 1\). Then \[ \ZZ/pq\ZZ \cong \ZZ/p\ZZ \times \ZZ/q\ZZ. \]
Recognizing internal direct products (Tag T-SVJUN)
Let \(G\) be a group with subgroups \(H\) and \(K\) such that
\(H, K \normal G\),
\(G = HK\), and
\(H\intersect K = \theset{e}\).
Then the map \(H \times K\to G\), \((h,k)\mapsto hk\), is an isomorphism, so \(G \cong H \times K\).
Hypothesis 1 may be replaced by the condition that \(hk=kh\) for all \(h\in H\) and \(k\in K\): together with \(G=HK\), this condition implies that \(H\) and \(K\) are normal in \(G\).
Recognition theorem for internal direct products (Tag FT-7NMQR)
Let \(G\) be a group and let \(H,K\le G\) be normal subgroups with \(H\cap K=\theset{e}\) and \(HK=G\). Then the map \[ H\times K\to G,\qquad(h,k)\mapsto hk, \] is an isomorphism of groups.
For \(h\in H\) and \(k\in K\), the commutator \(hkh^{-1}k^{-1}\) lies in \(K\) because \(K\) is normal and in \(H\) because \(H\) is normal, so it is \(e\) and \(hk=kh\). Hence \((h,k)(h',k')=(hh',kk')\mapsto hh'kk'=hkh'k'\), and the map is a homomorphism. Its kernel consists of the pairs with \(hk=e\), so \(h=k^{-1}\in H\cap K=\theset{e}\), and the map is injective. It is surjective because \(HK=G\).
Recognizing direct products (Tag E-DFUYC)
Prove the “recognizing direct products” theorem. Can the conditions be relaxed?
Solution
The recognizing-direct-products theorem says that if \(H,K\le G\) satisfy \[ H\trianglelefteq G, \qquad K\trianglelefteq G, \qquad H\cap K=\{e\}, \qquad HK=G, \] then \(G\cong H\times K\).
<1>1. Every element of \(H\) commutes with every element of \(K\).
Let \(h\in H\) and \(k\in K\). Since \(H\) is normal, \[ kh^{-1}k^{-1}\in H, \] so \[ [h,k]=hkh^{-1}k^{-1}\in H. \] Since \(K\) is normal, \[ hkh^{-1}\in K, \] so \([h,k]\in K\) as well. Hence \[ [h,k]\in H\cap K=\{e\}, \] and therefore \(hk=kh\).
<1>2. The multiplication map \[ \mu:H\times K\longrightarrow G, \qquad \mu(h,k)=hk, \] is a homomorphism.
For \((h_1,k_1),(h_2,k_2)\in H\times K\), <1>1 gives \(k_1h_2=h_2k_1\). Thus \[ \mu(h_1,k_1)\mu(h_2,k_2) =h_1k_1h_2k_2 =h_1h_2k_1k_2 =\mu(h_1h_2,k_1k_2). \]
<1>3. The map \(\mu\) is surjective.
The hypothesis \(HK=G\) says exactly that every \(g\in G\) can be written \(g=hk\) with \(h\in H\) and \(k\in K\).
<1>4. The map \(\mu\) is injective.
If \(\mu(h,k)=e\), then \(hk=e\), so \[ h=k^{-1}. \] The left side lies in \(H\) and the right side lies in \(K\), hence \[ h=k^{-1}\in H\cap K=\{e\}. \] Thus \(h=k=e\), so \(\ker\mu=\{(e,e)\}\).
<1>5. Therefore \(G\cong H\times K\).
By <1>2–<1>4, \(\mu\) is a bijective homomorphism.
<1>6. The normality hypotheses can be replaced by the weaker-looking condition that \(H\) and \(K\) commute elementwise.
Assume only \[ HK=G, \qquad H\cap K=\{e\}, \qquad [h,k]=e\quad\text{for all }h\in H,\ k\in K. \] Then the proofs of <1>2–<1>5 apply verbatim, so \(G\cong H\times K\). Thus direct elementwise commutation is the condition actually needed to make the multiplication map a homomorphism; normality in the original theorem is a sufficient way to obtain it from the trivial-intersection hypothesis.
Recognition theorem for internal direct products (Tag E-R6I7G)
Let \(H,K\le G\). Assume \[ G=HK, \qquad H\cap K=\{e\}, \qquad H\trianglelefteq G, \qquad K\trianglelefteq G. \] Prove that the multiplication map \[ \Gamma:H\times K\longrightarrow G, \qquad \Gamma(h,k)=hk, \] is an isomorphism. Determine how the normality hypotheses can be weakened.
Solution
<1>1. Every element of \(H\) commutes with every element of \(K\).
Let \(h\in H\) and \(k\in K\). Because \(H\trianglelefteq G\), \[ kh^{-1}k^{-1}\in H, \] so \[ [h,k]=hkh^{-1}k^{-1}=h(kh^{-1}k^{-1})\in H. \] Because \(K\trianglelefteq G\), \[ hkh^{-1}\in K, \] so \[ [h,k]=(hkh^{-1})k^{-1}\in K. \] Thus \[ [h,k]\in H\cap K=\{e\}, \] hence \([h,k]=e\) and therefore \(hk=kh\).
<1>2. The map \(\Gamma\) is a homomorphism.
For \((h_1,k_1),(h_2,k_2)\in H\times K\), <1>1 gives \(k_1h_2=h_2k_1\). Hence \[ \begin{aligned} \Gamma(h_1,k_1)\Gamma(h_2,k_2) &=h_1k_1h_2k_2\\ &=h_1h_2k_1k_2\\ &=\Gamma(h_1h_2,k_1k_2). \end{aligned} \]
<1>3. The map \(\Gamma\) is surjective.
The hypothesis \(G=HK\) says exactly that every \(g\in G\) has the form \(g=hk\) with \(h\in H\), \(k\in K\). Thus every \(g\) lies in the image of \(\Gamma\).
<1>4. The map \(\Gamma\) is injective.
Suppose \[ \Gamma(h,k)=hk=e. \] Then \[ h=k^{-1}. \] The left side belongs to \(H\) and the right side belongs to \(K\), so \[ h=k^{-1}\in H\cap K=\{e\}. \] Hence \(h=e\) and \(k=e\), so the kernel is trivial. Since \(\Gamma\) is a homomorphism, it is injective.
<1>5. Therefore \[ G\cong H\times K. \]
By <1>2–<1>4, \(\Gamma\) is a bijective homomorphism.
<1>6. The normality assumptions can be weakened to the single condition \[ [H,K]=1, \] i.e. every element of \(H\) commutes with every element of \(K\).
The proof of <1>2 uses only elementwise commutation, while <1>3 and <1>4 use only \(G=HK\) and \(H\cap K=\{e\}\). Thus the three conditions \[ G=HK, \qquad H\cap K=\{e\}, \qquad [H,K]=1 \] already imply \(G\cong H\times K\).
Conversely, if the multiplication map \(H\times K\to G\) is a homomorphism, then \[ (h,e)(e,k)=(h,k)=(e,k)(h,e) \] in \(H\times K\), so their images satisfy \(hk=kh\) in \(G\). Hence elementwise commutation is exactly the condition needed in place of normality for this multiplication-map proof.
<1>7. In the finite coprime-order case, trivial intersection is automatic.
If \(H\) and \(K\) are finite and \(\gcd(|H|,|K|)=1\), then \(|H\cap K|\) divides both \(|H|\) and \(|K|\) by Lagrange’s theorem. Hence \(|H\cap K|=1\), so \(H\cap K=\{e\}\).
Recognizing internal direct products of finitely many subgroups (Tag T-YNKCZ)
Let \(G\) be a group with subgroups \(H_1,\ldots,H_n\) such that
\(H_i \normal G\) for all \(i\),
\(G = H_1 \cdots H_n\), and
for each \(k\), \(H_k \intersect \left(H_1 \cdots H_{k-1}H_{k+1} \cdots H_n\right) = \theset{e}\).
Then the map \(\prod_{i=1}^n H_i\to G\), \((h_1,\ldots,h_n)\mapsto h_1\cdots h_n\), is an isomorphism, so \(G \cong \prod_{i=1}^n H_i\).
Recognizing internal semidirect products (Tag T-SB6AV)
Let \(G\) be a group with subgroups \(N \normal G\) and \(H\leq G\) such that \(G = NH\) and \(N\intersect H=\theset{e}\). Let \(\psi\colon H \to \Aut(N)\) be the conjugation action, \(\psi(h)=h(\wait)h^{-1}\). Then \(G \cong N \semidirect_\psi H\).
If moreover \(H\normal G\), then \(hnh^{-1}n^{-1}\in N\intersect H=\theset{e}\) for all \(n\in N\) and \(h\in H\), so \(\psi\) is trivial and \(G\cong N\times H\).
(Semidirect products with a given kernel and complement)
For groups \(N\) and \(H\), if \(\varphi,\psi\colon H\to\Aut(N)\) satisfy \(\psi=\varphi\circ\alpha\) for some \(\alpha\in\Aut(H)\), then \(N\semidirect_\varphi H\cong N\semidirect_\psi H\). For \(N=\ZZ/n\), \(\Aut(\ZZ/n)\cong(\ZZ/n)^\times\), so every semidirect product \(\ZZ/n\semidirect_\psi H\) is given by a homomorphism \(\psi\colon H\to(\ZZ/n)^\times\).
Automorphism groups
For cyclic \(N\cong\ZZ/n\), \(\Aut(N)\cong(\ZZ/n)^\times\), whose order is the number of integers in \(\ts{1,\ldots,n}\) coprime to \(n\), the value at \(n\) of Euler's totient function.
Automorphism groups of cyclic groups and related counts (Tag PR-N6S6P)
Let \(\varphi\) be Euler's totient function.
For \(n \geq 1\), a cyclic group \(C_n\) has exactly \(\varphi(n)\) generators, and for primes \(p \neq q\) and \(k, \ell \geq 1\), \[ \begin{aligned} \varphi(p) &= p-1, \\ \varphi(p^k) &= p^{k-1}(p - 1), \\ \varphi(p^k q^\ell) &= \varphi(p^k)\,\varphi(q^\ell). \end{aligned} \]
\(\Aut(C_n) \cong \unitsof{(\ZZ/n\ZZ)}\), a group of order \(\varphi(n)\). It is cyclic if and only if \(n = 1, 2, 4, p^k\), or \(2p^k\) with \(p\) an odd prime and \(k \geq 1\).
For \(p\) an odd prime and \(k \geq 1\), \(\Aut(C_{p^k}) \cong C_{\varphi(p^k)}\); in particular \(\Aut(C_p) \cong C_{p-1}\).
\(\Aut(C_2) = 1\), \(\Aut(C_4) \cong C_2\), and for \(k \geq 3\), \(\Aut(C_{2^k}) \cong C_2 \times C_{2^{k-2}}\).
If \(G\) and \(H\) are finite groups of coprime orders, then \(\Aut(G \times H) \cong \Aut(G) \times \Aut(H)\). Consequently, if \(n = \prod_{k=1}^\ell p_k^{n_k}\) with distinct primes \(p_k\), \(p_1 = 2\), and \(n_1 \geq 3\), then \(C_n \cong \prod_{k=1}^{\ell} C_{p_k^{n_k}}\) and \[ \begin{aligned} \Aut(C_n) &\cong \prod_{k=1}^\ell \Aut\qty{C_{p_k^{n_k}}} \\ &\cong \prod_{k=1}^\ell \unitsof{(\ZZ/p_k^{n_k}\ZZ)} \\ &\cong \qty{C_2 \times C_{2^{n_1-2}} } \times \prod_{k=2}^\ell C_{m_k}, \qquad m_k \coloneqq \varphi(p_k^{n_k}) = p_k^{n_k-1}(p_k-1). \end{aligned} \]
For \(m \geq 2\) and \(n \geq 1\), \(\Aut(C_m^n) \cong \GL_n(\ZZ/m\ZZ)\). For \(p\) prime, \(\Aut(C_p^n) \cong \GL_n(\FF_p)\), and \[ \abs{\GL_n(\FF_p)} = \prod_{k=0}^{n-1}(p^n-p^k) = (p^n-1)(p^n-p)(p^n-p^2)\cdots(p^n-p^{n-1}). \]
For \(m, n \geq 1\), \(\abs{\Hom(C_n, C_m)} = \gcd(n, m)\).
Let \(N, H\) be groups, \(\psi\colon H \to \Aut(N)\) a homomorphism, \(\sigma \in \Aut(H)\), and \(\tau \in \Aut(N)\), and let \(c_\tau\colon \Aut(N) \to \Aut(N)\) be conjugation \(\alpha \mapsto \tau\alpha\inverseof{\tau}\). Then \(N \semidirect_\psi H \cong N \semidirect_{c_\tau \circ \psi \circ \sigma} H\).
For every group \(G\), \(\Inn(G) \cong G/Z(G)\).
\(\Aut(C_8) \cong \unitsof{(\ZZ/8\ZZ)} = \theset{1, 3, 5, 7}\) has every nonidentity element of order \(2\), so \(\Aut(C_8) \cong C_2 \times C_2 \not\cong C_4\).
By (h), for \(N = C_p^n\) and \(H = C_k = \gens{h}\), a homomorphism \(\psi\colon C_k \to \GL_n(\FF_p)\) is determined by the matrix \(A = \psi(h)\), and replacing \(A\) by a similar matrix \(PA\inverseof{P}\) gives an isomorphic semidirect product. So it suffices to take \(A\) in a canonical form, such as the rational canonical form.
Finitely generated abelian groups
A finite abelian group has an invariant factor decomposition \(\ZZ/d_1\times\cdots\times\ZZ/d_k\) with \(d_1\divides d_2\divides\cdots\divides d_k\), and an elementary divisor decomposition as a product of cyclic groups of prime-power order; each is unique up to the order of the factors. The elementary divisors are the prime-power factors of the \(d_i\), and \(d_k\) is the product, over the primes \(p\), of the largest elementary divisor that is a power of \(p\). The order of the group is \(d_1\cdots d_k\) and its exponent is \(d_k\).
Invariant factor decomposition (Tag D-SS34F)
Let \(G\) be a finitely generated abelian group, and for \(n\geq 1\) let \(C_n\) denote the cyclic group of order \(n\). An invariant factor decomposition of \(G\) is an isomorphism \[ G \cong \ZZ^r \times \prod_{k=1}^m C_{n_k} \] with \(r,m\geq 0\) and integers \(n_1,\ldots,n_m\geq 2\) such that \(n_1 \divides n_2\divides \cdots \divides n_m\). The integers \(n_1,\ldots,n_m\) are the invariant factors of \(G\).
Every finitely generated abelian group \(G\) has an invariant factor decomposition, the direct product of the free abelian group \(\ZZ^r\) and finitely many finite cyclic groups. The integers \(r\) and \(m\) and the invariant factors \(n_1,\ldots,n_m\) are uniquely determined by \(G\).
Elementary divisor decomposition (Tag D-JQNJQ)
Let \(G\) be a finitely generated abelian group, and for \(n\geq 1\) let \(C_n\) denote the cyclic group of order \(n\). An elementary divisor decomposition of \(G\) is an isomorphism \[ G \cong \ZZ^r \times \prod_{k=1}^m C_{p_k^{e_k}} \] with \(r,m\geq 0\), primes \(p_1,\ldots,p_m\) that need not be distinct, and exponents \(e_1,\ldots,e_m\geq 1\). The prime powers \(p_1^{e_1},\ldots,p_m^{e_m}\) are the elementary divisors of \(G\).
Every finitely generated abelian group \(G\) has an elementary divisor decomposition. The integer \(r\) and the list \(p_1^{e_1},\ldots,p_m^{e_m}\), up to reordering, are uniquely determined by \(G\).
Invariant factors of a module over a PID (Tag FD-JTWOB)
Let \(R\) be a principal ideal domain and \(M\) a finitely generated \(R\)-module. By the structure theorem, there are an integer \(r\geq 0\) and nonzero nonunits \(r_1,\ldots,r_m\in R\) with \[ M\cong R^r\oplus\bigoplus_{i=1}^m R/(r_i) \qquad\text{and}\qquad r_1 \divides r_2 \divides \cdots \divides r_m, \] and \(r_1,\ldots,r_m\) are unique up to units. The elements \(r_1,\ldots,r_m\) are the invariant factors of \(M\).
Elementary divisors of a finite abelian group (Tag FD-H764S)
Let \(G\) be a finite abelian group. By the elementary divisor decomposition, there are primes \(p_1,\ldots,p_m\), not necessarily distinct, and integers \(\alpha_1,\ldots,\alpha_m\geq 1\) with \[ G \cong \bigoplus_{i=1}^m \ZZ/p_i^{\alpha_i} \ZZ, \] and the list \(p_1^{\alpha_1},\ldots,p_m^{\alpha_m}\) is unique up to order. These prime powers are the elementary divisors of \(G\).
Converting between elementary divisors and invariant factors (Tag PR-TLPVU)
Let \(G\) be a finite abelian group with \(G\cong\bigoplus_{i=1}^s \ZZ/m_i\ZZ\) for integers \(m_i\geq 2\), not necessarily distinct.
The elementary divisors of \(G\) are the prime powers \(p^e\), \(e\geq1\), occurring in the factorizations \(m_i=\prod_p p^{e_{p,i}}\), listed with multiplicity over all \(i\); that is, \(G\cong\bigoplus_{i}\bigoplus_{p} \ZZ/p^{e_{p,i}}\ZZ\).
For each prime \(p\), list the exponents of the \(p\)-power elementary divisors in decreasing order, \(e_{p,1}\geq e_{p,2}\geq\cdots\), padding with zeros. Put \(d_j\coloneqq\prod_p p^{e_{p,j}}\) and let \(t\) be the largest \(j\) with \(d_j\neq 1\). Then \(d_t\divides d_{t-1}\divides\cdots\divides d_1\) and \[ G\cong \ZZ/d_t\ZZ\oplus\cdots\oplus\ZZ/d_1\ZZ \] is the invariant factor decomposition of \(G\).
By the Chinese remainder theorem, \(\ZZ/m\ZZ\cong\bigoplus_p\ZZ/p^{e_p}\ZZ\) for \(m=\prod_p p^{e_p}\), which gives (a). For (b), the same theorem gives \(\ZZ/d_j\ZZ\cong\bigoplus_p\ZZ/p^{e_{p,j}}\ZZ\), so \(\bigoplus_j\ZZ/d_j\ZZ\) has the same elementary divisors as \(G\) and is isomorphic to \(G\). Since \(e_{p,j+1}\leq e_{p,j}\) for every \(p\), \(d_{j+1}\divides d_j\).
Let \(G=\ZZ/12\ZZ\oplus\ZZ/18\ZZ\oplus\ZZ/5\ZZ\). Since \(12=2^2\cdot3\) and \(18=2\cdot3^2\), the elementary divisors are \(2^2, 2, 3^2, 3, 5\). The largest power of each prime gives \(d_1=2^2\cdot3^2\cdot5=180\), and the remaining powers give \(d_2=2\cdot3=6\). Hence \(G\cong\ZZ/6\ZZ\oplus\ZZ/180\ZZ\), with \(6\divides180\).
Number of abelian groups of order $n$ as a product of partition numbers (Tag PR-2JG3F)
Let \(n = \prod_{k=1}^m p_k^{e_k}\), where \(p_1, \ldots, p_m\) are distinct primes and \(e_1, \ldots, e_m \geq 1\), and for an integer \(e \geq 1\) let \(P(e)\) be the number of partitions of \(e\). Up to isomorphism, there are exactly \(\prod_{k=1}^m P(e_k)\) abelian groups of order \(n\).
Recurrence for the partition numbers $P_k(n)$ and $P(n)$ (Tag PR-434DX)
For integers \(m \geq 0\) and \(k \geq 0\), let \(P_k(m)\) be the number of partitions of \(m\) into exactly \(k\) positive parts, so that \(P_0(0) = 1\), \(P_0(m) = 0\) for \(m \geq 1\), and \(P_k(m) = 0\) for \(k > m\). Let \(P(m) \coloneqq \sum_{k=0}^m P_k(m)\) be the number of partitions of \(m\). Then for \(n \geq k \geq 1\), \[ P_k(n) = P_k(n-k) + P_{k-1}(n-1), \] and for \(n \geq 1\), \[ P(n) = \sum_{k=1}^n P_k(n-k) + P(n-1). \]
Divide the partitions of \(n\) into \(k\) parts into two classes. Those whose parts are all at least \(2\) correspond bijectively to partitions of \(n-k\) into \(k\) parts, by subtracting \(1\) from each part; in the other direction, \([1,1,1,3] \mapsto [2,2,2,4]\). Those with a part equal to \(1\) correspond bijectively to partitions of \(n-1\) into \(k-1\) parts, by deleting one part equal to \(1\); in the other direction, \([1,1,2,5] \mapsto [1,1,2,5,1]\). This proves the first identity.
Summing it over \(1 \leq k \leq n\) gives \[ P(n) = \sum_{k=1}^n P_k(n-k) + \sum_{j=0}^{n-1} P_j(n-1) = \sum_{k=1}^n P_k(n-k) + P(n-1). \] Applying the same identity to \(P(n-1)\), \(P(n-2)\), and so on computes \(P(n)\) recursively: \[ \begin{aligned} P(n) &= \sum_{k=1}^n P_k(n-k) + P(n-1) \\ &= \sum_{k=1}^n P_k(n-k) + \sum_{k=1}^{n-1} P_k(n-1-k) + P(n-2) \\ &= \cdots \end{aligned} \]