TAOCP 7.2.1.3: Generating All Combinations
Section 7.2.1.3 exercises: 111/111 solved.
Section 7.2.1.3. Generating All Combinations
Exercises from TAOCP Volume 4 Section 7.2.1.3: 111/111 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [M23] | math-medium | solved | 7m27s |
| 2 | [16] | medium | solved | 7m35s |
| 3 | ▶ [21] | medium | solved | 5m23s |
| 4 | [16] | medium | solved | 4m55s |
| 5 | ▶ [20] | medium | solved | 3m37s |
| 6 | [M22] | math-medium | solved | 4m44s |
| 7 | [22] | medium | solved | 9m38s |
| 8 | [M23] | math-medium | solved | 4m55s |
| 9 | [M26] | math-hard | solved | 4m40s |
| 10 | ▶ [21] | medium | solved | 3m58s |
| 11 | [19] | medium | solved | 14m58s |
| 12 | [HM32] | hm-hard | solved | 5m34s |
| 13 | [25] | medium | solved | 6m27s |
| 14 | [26] | hard | solved | 15m18s |
| 15 | [M22] | math-medium | solved | 6m44s |
| 16 | [M21] | math-medium | solved | 18m06s |
| 17 | [HM25] | hm-medium | solved | 6m52s |
| 18 | ▶ [20] | medium | solved | 8m52s |
| 19 | [21] | medium | solved | 12m17s |
| 20 | [M20] | math-medium | solved | 7m28s |
| 21 | [M22] | math-medium | solved | 9m30s |
| 22 | [M23] | math-medium | solved | 8m29s |
| 23 | [M23] | math-medium | solved | 10m45s |
| 24 | ▶ [M25] | math-medium | solved | 7m30s |
| 25 | [M35] | math-hard | solved | 7m21s |
| 26 | [26] | hard | solved | 25m37s |
| 27 | ▶ [25] | medium | solved | 4m56s |
| 28 | [M21] | math-medium | solved | 4m16s |
| 29 | ▶ [M28] | math-hard | solved | 21m24s |
| 30 | [M32] | math-hard | solved | 5m18s |
| 31 | [M23] | math-medium | solved | 4m54s |
| 32 | ▶ [M32] | math-hard | solved | 5m15s |
| 33 | [HM33] | hm-hard | solved | 5m07s |
| 34 | [M32] | math-hard | solved | 4m57s |
| 35 | [M26] | math-hard | solved | 9m50s |
| 36 | ▶ [M21] | math-medium | solved | 5m06s |
| 37 | ▶ [27] | hard | solved | 5m03s |
| 38 | [26] | hard | solved | 13m25s |
| 39 | [M21] | math-medium | solved | 4m03s |
| 40 | [M22] | math-medium | solved | 5m16s |
| 41 | [M27] | math-hard | solved | 5m04s |
| 42 | [HM34] | hm-hard | solved | 4m08s |
| 43 | [20] | medium | solved | 7m32s |
| 44 | ▶ [M21] | math-medium | solved | 6m59s |
| 45 | [32] | hard | solved | 7m39s |
| 46 | ▶ [33] | hard | solved | 5m51s |
| 47 | [26] | hard | solved | 13m59s |
| 48 | [M21] | math-medium | solved | 7m46s |
| 49 | [HM23] | hm-medium | solved | 14m55s |
| 50 | ▶ [HM25] | hm-medium | solved | 6m30s |
| 51 | [25] | medium | solved | 7m20s |
| 52 | [M37] | math-project | solved | 7m32s |
| 53 | [M46] | math-research | solved | 28m21s |
| 54 | [M40] | math-project | solved | 20m27s |
| 55 | ▶ [33] | hard | solved | 12m37s |
| 56 | [M49] | math-research | solved | 8m12s |
| 57 | ▶ [22] | medium | solved | 8m07s |
| 58 | [20] | medium | solved | 14m33s |
| 59 | [M25] | math-medium | solved | 3m53s |
| 60 | [23] | medium | solved | 15m41s |
| 61 | [32] | hard | solved | 5m12s |
| 62 | ▶ [M27] | math-hard | solved | 5m12s |
| 63 | [M41] | math-project | solved | 20m11s |
| 64 | ▶ [M30] | math-hard | solved | 19m32s |
| 65 | [M40] | math-project | solved | 7m53s |
| 66 | ▶ [22] | medium | solved | 16m44s |
| 67 | [46] | research | solved | 42m36s |
| 68 | [M01] | math-simple | solved | 10m34s |
| 69 | ▶ [M22] | math-medium | solved | 16m44s |
| 70 | [M25] | math-medium | solved | 15m55s |
| 71 | [M20] | math-medium | solved | 15m08s |
| 72 | ▶ [M22] | math-medium | solved | 6m29s |
| 73 | [M23] | math-medium | solved | 19m45s |
| 74 | [M21] | math-medium | solved | 6m27s |
| 75 | [M20] | math-medium | solved | 27m21s |
| 76 | [M20] | math-medium | solved | 13m43s |
| 77 | ▶ [M26] | math-hard | solved | 20m02s |
| 78 | [M22] | math-medium | solved | 20m34s |
| 79 | [M23] | math-medium | solved | 12m05s |
| 80 | [HM26] | hm-hard | solved | 2m01s |
| 81 | ▶ [M27] | math-hard | solved | 2m50s |
| 82 | [HM31] | hm-hard | solved | 4m32s |
| 83 | [HM46] | hm-research | solved | 4m38s |
| 84 | [HM27] | hm-hard | solved | 5m19s |
| 85 | [HM21] | hm-medium | solved | 12m23s |
| 86 | [M20] | math-medium | solved | 20m |
| 87 | [M21] | math-medium | solved | 16m04s |
| 88 | [M20] | math-medium | solved | 5m25s |
| 89 | [16] | medium | solved | 28m33s |
| 90 | [M22] | math-medium | solved | 7m50s |
| 91 | [M24] | math-medium | solved | 6m21s |
| 92 | [M28] | math-hard | solved | 8m08s |
| 93 | [M25] | math-medium | solved | 17m07s |
| 94 | [M20] | math-medium | solved | 24m47s |
| 95 | [17] | medium | solved | 7m37s |
| 96 | ▶ [M22] | math-medium | solved | 15m57s |
| 97 | ▶ [M26] | math-hard | solved | 35m22s |
| 98 | [30] | hard | solved | 17m17s |
| 99 | [M25] | math-medium | solved | 37m22s |
| 100 | ▶ [M30] | math-hard | solved | 4m51s |
| 101 | [M25] | math-medium | solved | 4m52s |
| 102 | [HM35] | hm-hard | solved | 12m05s |
| 103 | ▶ [M38] | math-project | solved | 4m53s |
| 104 | [M41] | math-project | solved | 4m51s |
| 105 | [M20] | math-medium | solved | 8m41s |
| 106 | [M21] | math-medium | solved | 4m43s |
| 107 | [22] | medium | solved | 10m47s |
| 108 | [M31] | math-hard | solved | 4m02s |
| 109 | [M31] | math-hard | solved | 19m |
| 110 | ▶ [26] | hard | solved | 17m14s |
| 111 | ▶ [M26] | math-hard | solved | 26m01s |
TAOCP 7.2.1.3 Exercise 1
Let $r_s,\dots,r_0$ satisfy t = r_s + \cdots + r_1 + r_0,\qquad 0 \le r_j \le m_j \quad (s \ge j \ge 0).
TAOCP 7.2.1.3 Exercise 2
Let $r_s,\dots,r_0$ satisfy t = r_s + \cdots + r_1 + r_0,\qquad 0 \le r_j \le m_j \quad (s \ge j \ge 0).
TAOCP 7.2.1.3 Exercise 3
Let $m_0,\dots,m_s$ and $t$ be fixed nonnegative integers, and let $C(m_0,\dots,m_s;t)$ denote the set of all bounded compositions r_0+\cdots+r_s=t,\qquad 0\le r_j\le m_j\ \ (0\le j\le s).
TAOCP 7.2.1.3 Exercise 4
Let $m_0,\dots,m_s$ and $t$ be fixed nonnegative integers, and let $C(m_0,\dots,m_s;t)$ denote the set of all bounded compositions r_0+\cdots+r_s=t,\qquad 0\le r_j\le m_j\ \ (0\le j\le s).
TAOCP 7.2.1.3 Exercise 5
Let $m_0,\dots,m_s$ and $t$ be fixed nonnegative integers, and let $C(m_0,\dots,m_s;t)$ denote the set of all bounded compositions r_0+\cdots+r_s=t,\qquad 0\le r_j\le m_j\ \ (0\le j\le s).
TAOCP 7.2.1.3 Exercise 6
Let $(a_{ij})$ be an $m\times n$ contingency table with row sums $r_i=\sum_{j=1}^n a_{ij}, \quad 1\le i\le m,$ and column sums $c_j=\sum_{i=1}^m a_{ij}, \quad 1\le j\le n,$ with $\sum_{i=1}^m r_i=\sum...
TAOCP 7.2.1.3 Exercise 7
An $(s,t)$-combination in dual form is a strictly decreasing sequence $b_s > b_{s-1} > \cdots > b_1 \ge 0,$ where ${b_1,\dots,b_s}$ are exactly the positions of the $0$’s in a binary string of length...
TAOCP 7.2.1.3 Exercise 8
An $(s,t)$-combination in dual form is a strictly decreasing sequence $b_s > b_{s-1} > \cdots > b_1 \ge 0,$ where ${b_1,\dots,b_s}$ are exactly the positions of the $0$’s in a binary string of length...
TAOCP 7.2.1.3 Exercise 9
An $(s,t)$-combination in dual form is a strictly decreasing sequence $b_s > b_{s-1} > \cdots > b_1 \ge 0,$ where ${b_1,\dots,b_s}$ are exactly the positions of the $0$’s in a binary string of length...
TAOCP 7.2.1.3 Exercise 10
An $(s,t)$-combination in dual form is a strictly decreasing sequence $b_s > b_{s-1} > \cdots > b_1 \ge 0,$ where ${b_1,\dots,b_s}$ are exactly the positions of the $0$’s in a binary string of length...
TAOCP 7.2.1.3 Exercise 11
A World Series scenario in the sense of exercise 10 is a sequence of games between $A$ and $N$ that stops when one side reaches four wins.
TAOCP 7.2.1.3 Exercise 12
Let $[n]={1,2,\dots,n}$ and let $\mathcal{A}$ be a family of $r$-subsets of $[n]$ such that for all $\alpha,\beta\in\mathcal{A}$ one has $\alpha\cap\beta\neq\varnothing$.
TAOCP 7.2.1.3 Exercise 13
Let $\alpha$ be the $t$-combination $c_t \cdots c_1$ with $n > c_t > \cdots > c_1 \ge 0$, viewed as the $t$-element set ${c_1,\dots,c_t} \subseteq {0,1,\dots,n-1}$.
TAOCP 7.2.1.3 Exercise 14
Let $n = s + t$ and consider a binary string $a_{n-1}\dots a_0$ representing an $(s,t)$-combination, where exactly $t$ entries are $1$.
TAOCP 7.2.1.3 Exercise 15
Let $A$ be a family of $t$-combinations, and let $\partial A$ denote its shadow, the family of all $(t-1)$-combinations contained in members of $A$.
TAOCP 7.2.1.3 Exercise 16
Algorithm L lists the $t$-combinations $c_t \dots c_2 c_1$ of ${0,1,\dots,n-1}$ in lexicographic order, starting from $c_j = j-1$ for $1 \le j \le t$.
TAOCP 7.2.1.3 Exercise 17
Write $N$ in binary form N = (a_m a_{m-1}\dots a_0)_2 = \sum_{i=0}^m a_i 2^i.
TAOCP 7.2.1.3 Exercise 18
Write $N$ in binary form N = (a_m a_{m-1}\dots a_0)_2 = \sum_{i=0}^m a_i 2^i.
TAOCP 7.2.1.3 Exercise 19
The binomial tree $T_n$ used in this section has $2^n$ nodes, each node corresponding to a binary string of length $n$, and $T_\infty$ is the limiting structure in which nodes correspond to all finite...
TAOCP 7.2.1.3 Exercise 20
Let $G$ be a graph with $m = 10^6$ edges, and let $K_t(G)$ denote the number of $t$-cliques in $G$.
TAOCP 7.2.1.3 Exercise 21
The exercise cannot be completed as stated because the statement of “the alternating combination law (30)” is not included in the provided material.
TAOCP 7.2.1.3 Exercise 22
Let the degree-$t$ combinatorial representation (57) of $N$ be written in the form N = \binom{c_t}{t} + \binom{c_{t-1}}{t-1} + \cdots + \binom{c_1}{1}, where
TAOCP 7.2.1.3 Exercise 23
Let $\mathcal{A}$ be a family of $s$-combinations and $\mathcal{B}$ a family of $t$-combinations, both subsets of $U={0,1,\dots,n-1}$ with $n\ge s+t$.
TAOCP 7.2.1.3 Exercise 24
Let $\mathcal{A}$ be a family of $s$-combinations and $\mathcal{B}$ a family of $t$-combinations, both subsets of $U={0,1,\dots,n-1}$ with $n\ge s+t$.
TAOCP 7.2.1.3 Exercise 25
Let $\mathcal{A}$ be a family of $s$-combinations and $\mathcal{B}$ a family of $t$-combinations, both subsets of $U={0,1,\dots,n-1}$ with $n\ge s+t$.
TAOCP 7.2.1.3 Exercise 26
Let the ternary reflected Gray code on $n$ digits be the sequence of all $n$-tuples $a = a_{n-1}\dots a_1a_0,\qquad a_i \in \{0,1,2\},$ constructed in the standard reflected recursive way, so consecut...
TAOCP 7.2.1.3 Exercise 27
Let the degree-$,(t-1),$ combinatorial representation (57) of a positive integer $N$ be written in the form N = \binom{n_t}{t} + \binom{n_{t-1}}{t-1} + \cdots + \binom{n_v}{v}, \qquad n_t > n_{t-1} >...
TAOCP 7.2.1.3 Exercise 28
Let the degree-$,(t-1),$ combinatorial representation (57) of a positive integer $N$ be written in the form N = \binom{n_t}{t} + \binom{n_{t-1}}{t-1} + \cdots + \binom{n_v}{v}, \qquad n_t > n_{t-1} >...
TAOCP 7.2.1.3 Exercise 29
Let a string $\alpha$ consist of symbols from ${+, -, 0}$ with exactly $t$ zeros and $s$ signs, where each nonzero symbol is either $+$ or $-$.
TAOCP 7.2.1.3 Exercise 30
Let $\kappa_t(N)$ denote the function defined in Section 7.
TAOCP 7.2.1.3 Exercise 31
Let $\kappa_t(N)$ denote the function defined in Section 7.
TAOCP 7.2.1.3 Exercise 32
Let $\mathcal{F}(N,t)$ denote a family of $N$ distinct $t$-combinations, and let $\kappa_t(N)$ be the extremal quantity defined in Section 7.
TAOCP 7.2.1.3 Exercise 33
Let $\mathcal{F}(N,t)$ denote a family of $N$ distinct $t$-combinations, and let $\kappa_t(N)$ be the extremal quantity defined in Section 7.
TAOCP 7.2.1.3 Exercise 34
Let $\mathcal{F}(N,t)$ denote a family of $N$ distinct $t$-combinations, and let $\kappa_t(N)$ be the extremal quantity defined in Section 7.
TAOCP 7.2.1.3 Exercise 35
Let $n = s + t$.
TAOCP 7.2.1.3 Exercise 36
Let $n = s + t$.
TAOCP 7.2.1.3 Exercise 37
Let $n = s + t$.
TAOCP 7.2.1.3 Exercise 38
An $(s,t)$-combination is represented in this section as a strictly decreasing sequence $c_t > c_{t-1} > \cdots > c_1 \ge 0,$ with $c_j \in {0,1,\dots,n-1}$ and $n=s+t$, satisfying condition (3).
TAOCP 7.2.1.3 Exercise 39
Let $\kappa_t$ be the function defined in the section, with inverse $\mu_t$ in the sense that M \ge \mu_t N \quad \Longleftrightarrow \quad \kappa_t(M) \ge N, for $t \ge 2$.
TAOCP 7.2.1.3 Exercise 40
For real $x \ge t-1$, define the generalized binomial coefficients \binom{x}{t} = \frac{x(x-1)\cdots(x-t+1)}{t!
TAOCP 7.2.1.3 Exercise 41
For real $x \ge t-1$, define the generalized binomial coefficients \binom{x}{t} = \frac{x(x-1)\cdots(x-t+1)}{t!
TAOCP 7.2.1.3 Exercise 42
For real $x \ge t-1$, define the generalized binomial coefficients \binom{x}{t} = \frac{x(x-1)\cdots(x-t+1)}{t!
TAOCP 7.2.1.3 Exercise 43
Fix an integer $t \ge 1$.
TAOCP 7.2.1.3 Exercise 44
Fix an integer $t \ge 1$.
TAOCP 7.2.1.3 Exercise 45
Let $n = s + t$ and let $\mathcal{A}$ be a family of $t$-combinations of ${0,1,\dots,n-1}$.
TAOCP 7.2.1.3 Exercise 46
Let $n = s + t$ and let $\mathcal{A}$ be a family of $t$-combinations of ${0,1,\dots,n-1}$.
TAOCP 7.2.1.3 Exercise 47
Let $[n]={0,1,\dots,n-1}$ and let $\binom{[n]}{t}$ denote the set of all $t$-combinations.
TAOCP 7.2.1.3 Exercise 48
Let $[n]={0,1,\dots,n-1}$ and let $\binom{[n]}{t}$ denote the set of all $t$-combinations.
TAOCP 7.2.1.3 Exercise 49
Let $q$ be a primitive $m$th root of unity, so $q^m=1$ and $q^j\neq 1$ for $1\le j<m$.
TAOCP 7.2.1.3 Exercise 50
The Takagi function is defined for $0 \le x \le 1$ by \tau(x)=\sum_{k=1}^{\infty}\int_{0}^{x} r_k(t)\,dt, \qquad r_k(t)=(-1)^{\lfloor 2^k t\rfloor}.
TAOCP 7.2.1.3 Exercise 51
The Takagi function is defined for $0 \le x \le 1$ by \tau(x)=\sum_{k=1}^{\infty}\int_{0}^{x} r_k(t)\,dt, \qquad r_k(t)=(-1)^{\lfloor 2^k t\rfloor}.
TAOCP 7.2.1.3 Exercise 52
The Takagi function is defined for $0 \le x \le 1$ by \tau(x)=\sum_{k=1}^{\infty}\int_{0}^{x} r_k(t)\,dt, \qquad r_k(t)=(-1)^{\lfloor 2^k t\rfloor}.
TAOCP 7.2.1.3 Exercise 53
The function $\tau(x)$ in Section 7.
TAOCP 7.2.1.3 Exercise 54
The proposed solution does not address the exercise.
TAOCP 7.2.1.3 Exercise 55
Let $T=\binom{2t-1}{t}$.
TAOCP 7.2.1.3 Exercise 56
Let $T=\binom{2t-1}{t}$.
TAOCP 7.2.1.3 Exercise 57
Let $T=\binom{2t-1}{t}$.
TAOCP 7.2.1.3 Exercise 58
Let $n = s + t$ as in equation (1) of Section 7.
TAOCP 7.2.1.3 Exercise 59
Let $n = s + t$ as in equation (1) of Section 7.
TAOCP 7.2.1.3 Exercise 60
Let the index set be ${0,1,\dots,s}$ with variables $r_s,\dots,r_0$ and constraints $0 \le r_j \le m_j$ for $s \ge j \ge 0$, together with r_s + \cdots + r_0 = t.
TAOCP 7.2.1.3 Exercise 61
The operators in this exercise are those introduced earlier in Section 7.
TAOCP 7.2.1.3 Exercise 62
The operators in this exercise are those introduced earlier in Section 7.
TAOCP 7.2.1.3 Exercise 63
Let $(a_{ij})$ be an $m\times n$ contingency table with fixed row sums $\sum_{j=1}^n a_{ij}=r_i \quad (1\le i\le m)$ and column sums $\sum_{i=1}^m a_{ij}=c_j \quad (1\le j\le n),$ where $\sum_i r_i=\s...
TAOCP 7.2.1.3 Exercise 64
A configuration is a length-$n=s+t$ word over ${0,1,\ast}$ containing exactly $s$ digits $0,1$ and exactly $t$ asterisks $\ast$.
TAOCP 7.2.1.3 Exercise 65
Let the $2 \times 2 \times 3$ torus be the Cartesian product $C_2 \times C_2 \times C_3,$ so its elements are triples $(i,j,k)$ with $i \in {0,1}$, $j \in {0,1}$, $k \in {0,1,2}$, and addition is take...
TAOCP 7.2.1.3 Exercise 66
Let a canonical basis $(\alpha_1,\ldots,\alpha_t)$ be represented as an ordered $t$-tuple of distinct elements of ${1,\ldots,n}$.
TAOCP 7.2.1.3 Exercise 67
Let $S(n,t,r)$ denote the set of Ising configurations from exercise 13 with parameters $n,t,r$ and with the additional restriction $a_0=0$.
TAOCP 7.2.1.3 Exercise 68
Let $\alpha$ be a $t$-combination, so $\alpha$ is a $t$-element subset of ${0,1,\dots,n-1}$.
TAOCP 7.2.1.3 Exercise 69
Let $A$ be a set of $t$-combinations of ${0,1,\dots,n-1}$.
TAOCP 7.2.1.3 Exercise 70
Let $\mathcal{A}$ be a set of $t$-combinations and let $|\mathcal{A}| = N$.
TAOCP 7.2.1.3 Exercise 71
Let $G$ be a simple graph with $m=10^6$ edges, and let $K_t(G)$ denote the number of $t$-cliques in $G$.
TAOCP 7.2.1.3 Exercise 72
Theorem W is proved in Section 7.
TAOCP 7.2.1.3 Exercise 73
Let $U$ denote the set underlying the multicombinations (92).
TAOCP 7.2.1.3 Exercise 74
Corollary C establishes that an $(s,t)$-combination can be represented equivalently as a binary string $a_{n-1}\dots a_1a_0$ with $t$ ones, as a decreasing sequence $c_t>\cdots>c_1$, as the complement...
TAOCP 7.2.1.3 Exercise 75
The representation (57) expresses a positive integer $N$ in degree-$t$ combinatorial form by selecting an index $v$ such that \binom{n}{t} > N \ge \binom{n}{t} - \binom{v}{t}, and then writing $N$ as...
TAOCP 7.2.1.3 Exercise 76
The function $\kappa_t N$ arises from the combinatorial number system in which an integer $N$ is written uniquely in the form N = \binom{n_t}{t} + \binom{n_{t-1}}{t-1} + \cdots + \binom{n_v}{v}, with...
TAOCP 7.2.1.3 Exercise 77
For a positive integer $N$, write its $t$-binomial representation \kappa_t N = \binom{n_t}{t} + \binom{n_{t-1}}{t-1} + \cdots + \binom{n_1}{1}, where $n_t > n_{t-1} > \cdots > n_1 \ge 0$ is the unique...
TAOCP 7.2.1.3 Exercise 78
Let $\kappa_t$ denote the function defined in Section 7.
TAOCP 7.2.1.3 Exercise 79
Write the unique representation of an integer $X \ge 0$ in the $t$-binomial number system as X = \binom{x_t}{t} + \binom{x_{t-1}}{t-1} + \cdots + \binom{x_1}{1}, where $x_t > x_{t-1} > \cdots > x_1 \g...
TAOCP 7.2.1.3 Exercise 80
Fix integer $t \ge 1$ and $N \ge 0$.
TAOCP 7.2.1.3 Exercise 81
The exercise, as stated here, cannot be solved because its mathematical content has been omitted.
TAOCP 7.2.1.3 Exercise 82
We use the standard representation, which follows directly from the definition of the Rademacher functions.
TAOCP 7.2.1.3 Exercise 83
Let $\tau:[0,1]\to\mathbb{R}$ be the Takagi function.
TAOCP 7.2.1.3 Exercise 84
A simplicial complex on an $n$-element vertex set is an order ideal in the Boolean lattice, so if a set is in the complex then all of its subsets are also in the complex.
TAOCP 7.2.1.3 Exercise 85
Let $T=\binom{2t-1}{t}$ and write $x=N/T$.
TAOCP 7.2.1.3 Exercise 86
The solution does not address the stated problem at all.
TAOCP 7.2.1.3 Exercise 87
The solution does not address the stated problem at all.
TAOCP 7.2.1.3 Exercise 88
The solution does not address the stated problem at all.
TAOCP 7.2.1.3 Exercise 89
Let the $2\times 2\times 3$ torus be the Cartesian product T = \mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_3, so each element is a triple $(x,y,z)$ with $x,y \in {0,1}$ and $z \in {0,1,2}$, wit...
TAOCP 7.2.1.3 Exercise 90
Algorithm H generates all integer partitions $a_1 \ge \cdots \ge a_m \ge 1$ of $n$ by maintaining a weakly decreasing sequence whose entries are positive and whose sum is always $n$.
TAOCP 7.2.1.3 Exercise 91
Algorithm H generates all integer partitions $a_1 \ge \cdots \ge a_m \ge 1$ of $n$ by maintaining a weakly decreasing sequence whose entries are positive and whose sum is always $n$.
TAOCP 7.2.1.3 Exercise 92
Let $a_1 \ge a_2 \ge \cdots \ge a_m \ge 1$ be a partition of $n$ into $m$ parts that is optimally balanced, meaning $|a_i-a_j|\le 1$ for all $1\le i,j\le m$.
TAOCP 7.2.1.3 Exercise 93
Let $n \ge m \ge 1$ and let $a_1 \ge a_2 \ge \cdots \ge a_m \ge 1$ be a partition of $n$ such that $|a_i - a_j| \le 1$ for all $i,j$.
TAOCP 7.2.1.3 Exercise 94
Let $U$ denote the set of all multicombinations under consideration in Corollary C, represented in the form $c_4c_3c_2c_1$ with $3 \ge c_4 \ge c_3 \ge c_2 \ge c_1 \ge 0.$ The hint specifies that withi...
TAOCP 7.2.1.3 Exercise 95
Let $U$ denote the set of all multicombinations under consideration in Corollary C, represented in the form $c_4c_3c_2c_1$ with $3 \ge c_4 \ge c_3 \ge c_2 \ge c_1 \ge 0.$ The hint specifies that withi...
TAOCP 7.2.1.3 Exercise 96
Let F_n(z)=\prod_{j=0}^{n-1}(1+z+\cdots+z^{s_j}), so that
TAOCP 7.2.1.3 Exercise 97
Let $C$ be a simplicial complex on a fixed vertex set $V$ with $|V|=4$.
TAOCP 7.2.1.3 Exercise 98
Let $[n]={1,2,\dots,n}$.
TAOCP 7.2.1.3 Exercise 99
A clutter on the ground set $[n]={0,1,\dots,n-1}$ is an antichain in the Boolean lattice: if $\alpha,\beta\in C$ and $\alpha\subseteq\beta$, then $\alpha=\beta$.
TAOCP 7.2.1.3 Exercise 100
Let $(a_{ij})$ be an $m\times n$ contingency table with nonnegative integer entries, row sums $r_i=\sum_{j=1}^n a_{ij},$ and column sums $c_j=\sum_{i=1}^m a_{ij},$ with $\sum_{i=1}^m r_i=\sum_{j=1}^n...
TAOCP 7.2.1.3 Exercise 101
Let $(a_{ij})$ be an $m\times n$ contingency table with nonnegative integer entries, row sums $r_i=\sum_{j=1}^n a_{ij},$ and column sums $c_j=\sum_{i=1}^m a_{ij},$ with $\sum_{i=1}^m r_i=\sum_{j=1}^n...
TAOCP 7.2.1.3 Exercise 102
Let $I \subseteq \mathbb{C}[x_1,\dots,x_s]$ be a homogeneous polynomial ideal.
TAOCP 7.2.1.3 Exercise 103
Let $n=s+t$ and let the ground positions be ${0,1,\dots,n-1}$.
TAOCP 7.2.1.3 Exercise 104
Let $n=s+t$ and let the ground positions be ${0,1,\dots,n-1}$.
TAOCP 7.2.1.3 Exercise 105
Let the universal cycle be $a_0,a_1,\dots,a_{L-1}$, indexed cyclically modulo $L$, over the alphabet ${0,1,\dots,n-1}$.
TAOCP 7.2.1.3 Exercise 106
Let $G_{s,t}$ denote the graph whose vertices are all subcubes of length $s+t$ having $s$ digits in ${0,1}$ and $t$ asterisks, with edges given by the transformations $\ast 0 \leftrightarrow 0\ast$, $...
TAOCP 7.2.1.3 Exercise 107
Let $G$ be the multigraph whose vertices are ${0,1,2,3,4,5,6}$ and whose edges are the $28$ dominoes of the double-six set, namely one edge between $i$ and $j$ for each $0 \le i \le j \le 6$, includin...
TAOCP 7.2.1.3 Exercise 108
Let $G$ be the multigraph whose vertices are ${0,1,2,3,4,5,6}$ and whose edges are the $28$ dominoes of the double-six set, namely one edge between $i$ and $j$ for each $0 \le i \le j \le 6$, includin...
TAOCP 7.2.1.3 Exercise 109
Let the canonical bases be represented in the form $(\alpha_1,\dots,\alpha_t)$ as in exercise 12, where each $\alpha_i$ is a binary string of length $n$ with exactly one distinguished position equal t...
TAOCP 7.2.1.3 Exercise 110
Fix $n,t,r$.
TAOCP 7.2.1.3 Exercise 111
Let $[n]={1,2,\dots,n}$ and let $\mathcal{A}$ be a family of $r$-subsets of $[n]$ such that for all $\alpha,\beta\in\mathcal{A}$ one has $\alpha\cap\beta\neq\varnothing$.