TAOCP 7.2.1.4: Generating All Partitions
Section 7.2.1.4 exercises: 73/73 solved.
Section 7.2.1.4. Generating All Partitions
Exercises from TAOCP Volume 4 Section 7.2.1.4: 73/73 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | ▶ [M21] | math-medium | solved | 5m25s |
| 2 | ▶ [20] | medium | solved | 5m12s |
| 3 | [M17] | math-medium | solved | 3m57s |
| 4 | [M22] | math-medium | solved | 8m24s |
| 5 | ▶ [23] | medium | solved | 16m48s |
| 6 | [20] | medium | solved | 5m37s |
| 7 | [M20] | math-medium | solved | 20m58s |
| 8 | [15] | simple | solved | 8m22s |
| 9 | [22] | medium | solved | 19m42s |
| 10 | [21] | medium | solved | 5m23s |
| 11 | [M22] | math-medium | solved | 16m06s |
| 12 | ▶ [M21] | math-medium | solved | 13m09s |
| 13 | ▶ [M23] | math-medium | solved | 6m55s |
| 14 | ▶ [M28] | math-hard | solved | 19m21s |
| 15 | [M20] | math-medium | solved | 24m20s |
| 16 | [M21] | math-medium | solved | 6m39s |
| 17 | [M26] | math-hard | solved | 8m12s |
| 18 | ▶ [M23] | math-medium | solved | 29m25s |
| 19 | [M22] | math-medium | solved | 28m04s |
| 20 | ▶ [M21] | math-medium | solved | 7m17s |
| 21 | [M21] | math-medium | solved | 8m18s |
| 22 | [HM21] | hm-medium | solved | 6m30s |
| 23 | [HM25] | hm-medium | solved | 8m12s |
| 24 | [M26] | math-hard | solved | 8m03s |
| 25 | [HM27] | hm-hard | solved | 24m12s |
| 26 | [HM22] | hm-medium | solved | 20m22s |
| 27 | [HM21] | hm-medium | solved | 5m33s |
| 28 | [HM42] | hm-project | solved | 20m10s |
| 29 | ▶ [M16] | math-medium | solved | 5m30s |
| 30 | [M17] | math-medium | solved | 14m41s |
| 31 | [M24] | math-medium | solved | 26m02s |
| 32 | [M15] | math-simple | solved | 5m41s |
| 33 | [HM20] | hm-medium | solved | 16m37s |
| 34 | ▶ [HM21] | hm-medium | solved | 4m04s |
| 35 | [HM21] | hm-medium | solved | 23m26s |
| 36 | [HM24] | hm-medium | solved | 8m14s |
| 37 | [M22] | math-medium | solved | 8m36s |
| 38 | [M20] | math-medium | solved | 19m15s |
| 39 | [M20] | math-medium | solved | 8m18s |
| 40 | ▶ [M25] | math-medium | solved | 8m36s |
| 41 | [HM42] | hm-project | solved | 8m49s |
| 42 | [HM42] | hm-project | solved | 8m11s |
| 43 | [M18] | math-medium | solved | 8m56s |
| 44 | ▶ [M22] | math-medium | solved | 8m37s |
| 45 | [HM21] | hm-medium | solved | 21m59s |
| 46 | [M20] | math-medium | solved | 8m36s |
| 47 | ▶ [HM22] | hm-medium | solved | 21m39s |
| 48 | [HM40] | hm-project | solved | 24m13s |
| 49 | ▶ [HM26] | hm-hard | solved | 5m40s |
| 50 | [HM33] | hm-hard | solved | 10m02s |
| 51 | [M46] | math-research | solved | 5m34s |
| 52 | ▶ [M21] | math-medium | solved | 4m20s |
| 53 | ▶ [M21] | math-medium | solved | 15m27s |
| 54 | ▶ [M30] | math-hard | solved | 5m37s |
| 55 | ▶ [M37] | math-project | solved | 13m24s |
| 56 | ▶ [M32] | math-hard | solved | 16m20s |
| 57 | [M22] | math-medium | solved | 7m03s |
| 58 | [M23] | math-medium | solved | 32m07s |
| 59 | [M22] | math-medium | solved | 44m15s |
| 60 | [23] | medium | solved | 19m50s |
| 61 | [26] | hard | solved | 23m04s |
| 62 | [46] | research | solved | 22m36s |
| 63 | [47] | research | solved | 21m27s |
| 64 | ▶ [32] | hard | solved | 8m28s |
| 65 | [23] | medium | solved | 3m55s |
| 66 | ▶ [M25] | math-medium | solved | 18m58s |
| 67 | [M25] | math-medium | solved | 13m15s |
| 68 | [M23] | math-medium | solved | 5m46s |
| 69 | [M30] | math-hard | solved | 23m05s |
| 70 | [M30] | math-hard | solved | 5m35s |
| 71 | [M46] | math-research | solved | 5m34s |
| 72 | [M30] | math-hard | solved | 5m30s |
| 73 | [M25] | math-medium | solved | 5m31s |
TAOCP 7.2.1.4 Exercise 1
The rim representation $(p_1 \ldots p_t, q_1 \ldots q_t)$ encodes the boundary (outer rim) of the Ferrers diagram of the partition $a_1 a_2 \ldots$ as an alternating sequence of maximal horizontal and...
TAOCP 7.2.1.4 Exercise 2
The rim representation $(p_1 \ldots p_t, q_1 \ldots q_t)$ encodes the boundary (outer rim) of the Ferrers diagram of the partition $a_1 a_2 \ldots$ as an alternating sequence of maximal horizontal and...
TAOCP 7.2.1.4 Exercise 3
The rim representation $(p_1 \ldots p_t, q_1 \ldots q_t)$ encodes the boundary (outer rim) of the Ferrers diagram of the partition $a_1 a_2 \ldots$ as an alternating sequence of maximal horizontal and...
TAOCP 7.2.1.4 Exercise 4
Let the Ferrers diagram of $a_1a_2\cdots a_m$ consist of cells $(i,j)$ with $1\le i\le m$ and $1\le j\le a_i$.
TAOCP 7.2.1.4 Exercise 5
Let $c_1c_2\cdots c_n$ be the part-count representation of a partition of $n$, so that $\sum_{j=1}^n j c_j = n.$ The colex order on partitions corresponds to lexicographic order on the reversed vector...
TAOCP 7.2.1.4 Exercise 6
Let $c_1,c_2,c_5,c_{10},c_{20},c_{50},c_{100}$ denote the numbers of coins of each denomination in cents.
TAOCP 7.2.1.4 Exercise 7
Let $a_1 \ge \cdots \ge a_n \ge 0$ and $a'_1 \ge \cdots \ge a'_n \ge 0$ be partitions of $n$.
TAOCP 7.2.1.4 Exercise 8
Let $\alpha$ be a partition of $n$, written in frequency form as $\alpha:\quad 1^{c_1} 2^{c_2} 3^{c_3}\cdots,$ where $c_j \ge 0$ and $\sum_{j\ge 1} j c_j = n$.
TAOCP 7.2.1.4 Exercise 9
Let $a_1 a_2 \dots a_m$ be a partition written in nonincreasing form, and let $b_1 b_2 \dots b_m$ be its conjugate, so $b_j$ is the number of indices $i$ with $a_i \ge j$.
TAOCP 7.2.1.4 Exercise 10
Let $a_1 > a_2 > \cdots > a_m \ge 1$ be a partition of $n$ into distinct parts.
TAOCP 7.2.1.4 Exercise 11
Let $a_1,a_2,a_5,a_{10},a_{20},a_{50},a_{100}\ge 0$ denote the numbers of coins of each denomination used to form 100 cents.
TAOCP 7.2.1.4 Exercise 12
A partition into distinct parts corresponds to a sequence $a_1 \ge a_2 \ge \cdots \ge a_m \ge 1$ in which all parts are distinct, so each positive integer $k$ appears at most once.
TAOCP 7.2.1.4 Exercise 13
A partition $\alpha$ is self-conjugate when its Ferrers diagram is symmetric across the main diagonal.
TAOCP 7.2.1.4 Exercise 14
Let $\alpha$ be a self-conjugate partition of $n$.
TAOCP 7.2.1.4 Exercise 15
Let $\alpha$ be a self-conjugate partition of $n$.
TAOCP 7.2.1.4 Exercise 16
A partition of $n$ has **trace $k$** when its Ferrers diagram has Durfee square of size $k$.
TAOCP 7.2.1.4 Exercise 17
Let a partition of $n$ have Ferrers diagram with Durfee square of size $k$, meaning that the largest square subdiagram is $k\times k$.
TAOCP 7.2.1.4 Exercise 18
Let $t=r+s$.
TAOCP 7.2.1.4 Exercise 19
Let F(a,b;u,v)=\sum_{k,l\ge 0} u^k v^l z^{kl} \frac{(z-az)(z-az^2)\cdots(z-az^k)}{(1-z)(1-z^2)\cdots(1-z^k)} \frac{(z-bz)(z-bz^2)\cdots(z-bz^l)}{(1-z)(1-z^2)\cdots(1-z^l)}.
TAOCP 7.2.1.4 Exercise 20
Let F(a,b;u,v)=\sum_{k,l\ge 0} u^k v^l z^{kl} \frac{(z-az)(z-az^2)\cdots(z-az^k)}{(1-z)(1-z^2)\cdots(1-z^k)} \frac{(z-bz)(z-bz^2)\cdots(z-bz^l)}{(1-z)(1-z^2)\cdots(1-z^l)}.
TAOCP 7.2.1.4 Exercise 21
Let F(a,b;u,v)=\sum_{k,l\ge 0} u^k v^l z^{kl} \frac{(z-az)(z-az^2)\cdots(z-az^k)}{(1-z)(1-z^2)\cdots(1-z^k)} \frac{(z-bz)(z-bz^2)\cdots(z-bz^l)}{(1-z)(1-z^2)\cdots(1-z^l)}.
TAOCP 7.2.1.4 Exercise 22
Let $E(q)=\prod_{m\ge 1}(1-q^m).$ Euler’s pentagonal number theorem gives $E(q)=\sum_{k\in \mathbb{Z}} (-1)^k q^{k(3k-1)/2}.$ Let $S(q)=\sum_{n\ge 1} \sigma(n) q^n.$
TAOCP 7.2.1.4 Exercise 23
Let E(z)=\prod_{k=1}^{\infty}(1-z^k), \qquad P(z)=\frac{1}{E(z)}=\sum_{n\ge 0} p(n)z^n.
TAOCP 7.2.1.4 Exercise 24
Let E(z)=\prod_{k=1}^{\infty}(1-z^k), \qquad P(z)=\frac{1}{E(z)}=\sum_{n\ge 0} p(n)z^n.
TAOCP 7.2.1.4 Exercise 25
Let P(q)=\prod_{k=1}^{\infty}(1-q^k)^{-1}, \qquad q=e^{-t}, \quad t>0.
TAOCP 7.2.1.4 Exercise 26
Let $f(x)=e^{-x^{2}/n}, \qquad n>0.$ The Poisson summation formula in the form used in TAOCP states that for sufficiently rapidly decreasing $f$, $\sum_{k=-\infty}^{\infty} f(k)=\sum_{m=-\infty}^{\inf...
TAOCP 7.2.1.4 Exercise 27
Let $f(x)=e^{-x^{2}/n}, \qquad n>0.$ The Poisson summation formula in the form used in TAOCP states that for sufficiently rapidly decreasing $f$, $\sum_{k=-\infty}^{\infty} f(k)=\sum_{m=-\infty}^{\inf...
TAOCP 7.2.1.4 Exercise 28
Let $A_k(n)$ denote the Hardy–Ramanujan–Rademacher coefficient defined in equation (34) of Section 7.
TAOCP 7.2.1.4 Exercise 29
Let $A_k(n)$ denote the Hardy–Ramanujan–Rademacher coefficient defined in equation (34) of Section 7.
TAOCP 7.2.1.4 Exercise 30
Let $m \ge 1$ and $n \ge 0$.
TAOCP 7.2.1.4 Exercise 31
Let $\left| \begin{matrix} n \ k \end{matrix} \right|$ denote the number of partitions of $n$ into exactly $k$ parts, equivalently the number of partitions of $n$ whose Ferrers diagram has $k$ rows.
TAOCP 7.2.1.4 Exercise 32
Let $p(m)$ denote the number of partitions of $m$ in the sense of Section 7.
TAOCP 7.2.1.4 Exercise 33
Let $S(n,m)$ denote the number of set partitions of ${1,\dots,n}$ into $m$ parts, so $S(n,m)=\left|\begin{matrix} n \ m \end{matrix}\right|$ in Knuth’s notation.
TAOCP 7.2.1.4 Exercise 34
Let $S(n,m)$ denote the number of set partitions of ${1,\dots,n}$ into $m$ parts, so $S(n,m)=\left|\begin{matrix} n \ m \end{matrix}\right|$ in Knuth’s notation.
TAOCP 7.2.1.4 Exercise 35
The Erdős–Lehner distribution (43) is the limiting distribution for the normalized random variable arising from the largest part (equivalently, the number of parts) of a random partition of $n$.
TAOCP 7.2.1.4 Exercise 36
The Erdős–Lehner distribution (43) is the limiting distribution for the normalized random variable arising from the largest part (equivalently, the number of parts) of a random partition of $n$.
TAOCP 7.2.1.4 Exercise 37
Let $\lambda = (\lambda_1 \ge \lambda_2 \ge \cdots)$ and $\mu = (\mu_1 \ge \mu_2 \ge \cdots)$ be partitions of the same integer $n$ such that $\lambda \preceq \mu$ in the sense of majorization, that i...
TAOCP 7.2.1.4 Exercise 38
Let $f_{l,m}(n)$ denote the number of partitions of $n$ having exactly $m$ parts and largest part equal to $l$.
TAOCP 7.2.1.4 Exercise 39
Let $f_{l,m}(n)$ denote the number of partitions of $n$ having exactly $m$ parts and largest part equal to $l$.
TAOCP 7.2.1.4 Exercise 40
Let $f_{l,m}(n)$ denote the number of partitions of $n$ having exactly $m$ parts and largest part equal to $l$.
TAOCP 7.2.1.4 Exercise 41
Let $f_{l,m}(n)$ denote the number of partitions of $n$ having exactly $m$ parts and largest part equal to $l$.
TAOCP 7.2.1.4 Exercise 42
Let $f_{l,m}(n)$ denote the number of partitions of $n$ having exactly $m$ parts and largest part equal to $l$.
TAOCP 7.2.1.4 Exercise 43
Let $f_{l,m}(n)$ denote the number of partitions of $n$ having exactly $m$ parts and largest part equal to $l$.
TAOCP 7.2.1.4 Exercise 44
Let $f_{l,m}(n)$ denote the number of partitions of $n$ having exactly $m$ parts and largest part equal to $l$.
TAOCP 7.2.1.4 Exercise 45
Let $p(n)$ denote the partition function.
TAOCP 7.2.1.4 Exercise 46
Let $S$ be a multiset of positive integers, and write its distinct values in increasing order as 1 \le b_1 < b_2 < \cdots < b_t, with multiplicities $m_1, m_2, \ldots, m_t$.
TAOCP 7.2.1.4 Exercise 47
Let $p(m)$ denote the number of integer partitions of $m$, with $p(0)=1$.
TAOCP 7.2.1.4 Exercise 48
Let $p(n)$ be the partition function.
TAOCP 7.2.1.4 Exercise 49
Let $p(n)$ be the partition function.
TAOCP 7.2.1.4 Exercise 50
The statement of Exercise 7.
TAOCP 7.2.1.4 Exercise 51
The statement of Exercise 7.
TAOCP 7.2.1.4 Exercise 52
The statement of Exercise 7.
TAOCP 7.2.1.4 Exercise 53
Let $a_1 \ge a_2 \ge \cdots \ge a_{32} \ge 1$ with $a_1 + \cdots + a_{32} = 100$.
TAOCP 7.2.1.4 Exercise 54
Let $a_1 \ge a_2 \ge \cdots \ge a_{32} \ge 1$ with $a_1 + \cdots + a_{32} = 100$.
TAOCP 7.2.1.4 Exercise 55
Let $\alpha = a_1 a_2 \dots a_k$ be a partition of $n$ and define the dominance order $\alpha \succeq \beta$ as in the exercise.
TAOCP 7.2.1.4 Exercise 56
Let $\lambda = (\lambda_1 \ge \lambda_2 \ge \cdots \ge 0)$ and $\mu = (\mu_1 \ge \mu_2 \ge \cdots \ge 0)$ be partitions of the same integer $n$, and assume $\lambda \preceq \mu$ in the majorization or...
TAOCP 7.2.1.4 Exercise 57
Let $\lambda = (\lambda_1 \ge \lambda_2 \ge \cdots \ge 0)$ and $\mu = (\mu_1 \ge \mu_2 \ge \cdots \ge 0)$ be partitions of the same integer $n$, and assume $\lambda \preceq \mu$ in the majorization or...
TAOCP 7.2.1.4 Exercise 58
Let F_\alpha(x_1,\dots,x_m)=\frac{1}{m!
TAOCP 7.2.1.4 Exercise 59
The solution does not address the stated problem.
TAOCP 7.2.1.4 Exercise 60
The solution does not address the stated problem.
TAOCP 7.2.1.4 Exercise 61
A partition of $n$ is a nonincreasing sequence a_1 \ge a_2 \ge \cdots \ge a_m \ge 1,\qquad a_1+\cdots+a_m=n.
TAOCP 7.2.1.4 Exercise 62
Let $\mathcal{P}(n,m)$ denote the set of partitions $\alpha = a_1 \ge a_2 \ge \cdots$ of $n$ with largest part $a_1 \le m$.
TAOCP 7.2.1.4 Exercise 63
Solution to TAOCP 7.2.1.4 Exercise 63.
TAOCP 7.2.1.4 Exercise 64
Let $\lambda = (\lambda_1 \ge \lambda_2 \ge \cdots)$ and $\mu = (\mu_1 \ge \mu_2 \ge \cdots)$ be partitions of the same integer $n$.
TAOCP 7.2.1.4 Exercise 65
Let $m=\prod_{p} p^{E_p}$ be the prime factorization of $m$, where each $E_p\ge 0$.
TAOCP 7.2.1.4 Exercise 66
Let $P$ be a poset on ${1,\dots,m}$ with relation $\prec$, relabeled so that $j \prec k \Rightarrow j \le k$.
TAOCP 7.2.1.4 Exercise 67
Let the perfect partition be a multiset with distinct values $v_1 < v_2 < \cdots < v_t$, where each value $v_i$ occurs with multiplicity $b_i-1 \ge 0$.
TAOCP 7.2.1.4 Exercise 68
Let the perfect partition be a multiset with distinct values $v_1 < v_2 < \cdots < v_t$, where each value $v_i$ occurs with multiplicity $b_i-1 \ge 0$.
TAOCP 7.2.1.4 Exercise 69
We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
TAOCP 7.2.1.4 Exercise 70
We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
TAOCP 7.2.1.4 Exercise 71
We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
TAOCP 7.2.1.4 Exercise 72
We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
TAOCP 7.2.1.4 Exercise 73
We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.