Mastering Combinations with Repetition (nHr): Stars and Bars, Monotonic Functions & Diophantine Partition Techniques (10 Advanced Problem Types)

 

Advanced Combinatorics Masterclass

Mastering Combinations with Repetition ($\mathrm{_{n}H_{r}}$): Stars and Bars, Monotonic Functions & Diophantine Partitioning

In competitive mathematics (such as AMC 12, AIME, and national entrance examinations), the dividing line between top-tier performers and average problem solvers is the mastery of Combinations with Repetition ($\mathrm{_{n}H_{r}}$ / Stars and Bars) applied to constrained Diophantine equations and monotonic function mapping.

While almost every advanced student memorizes the fundamental formula $\mathrm{_{n}H_{r}} = \binom{n+r-1}{r}$, competition-level problems never appear in an unconstrained form. Instead, they present nested constraints: parity restrictions (odd/even), upper bounds, image cardinality limits ($|f(X)| = k$), and difference constraints ($|f(a) - f(b)| \ge 2$). Achieving speed and accuracy requires choosing a clear partitioning benchmark to divide cases without omissions or overlaps.

💡 The 3 Pillars of Constrained Stars & Bars

1. Standardization to Non-negative Integers: Always transform constrained variables into base variables $X \ge 0$ via substitution.
2. Pivot on Singular Constraints: Split cases first using variables with irregular coefficients, parity conditions, or absolute values.
3. Proactive Complementary Counting: When dealing with upper bounds ($a \le k$) or "at least one" conditions, subtract the complement from the unrestricted universe.

---

1. Three Fundamental Techniques for Constrained Systems

Technique 1. Variable Normalization ($X \ge 0$)

The Stars and Bars theorem operates exclusively on non-negative integers ($X \ge 0$). Shift constraints to standard form before computing:

• Positive Integers ($a \ge 1$): Set $a = A + 1$ ($A \ge 0$) $\implies$ subtract $1$ from the right-hand constant.
• Odd Integers: Set $a = 2A + 1$ ($A \ge 0$) $\implies$ yields $1, 3, 5, \dots$
• Even Positive Integers: Set $a = 2A + 2$ ($A \ge 0$) $\implies$ yields $2, 4, 6, \dots$

Technique 2. Weakly Increasing Functions & Slack Variables

Given domain $X=\{1, 2, \dots, r\}$ and codomain $Y=\{1, 2, \dots, n\}$, the number of weakly increasing functions ($a \le b \implies f(a) \le f(b)$) equals selecting $r$ values with repetition from $n$ elements: $\mathrm{_{n}H_{r}} = \binom{n+r-1}{r}$.

💡 Slack Variable Shortcut: For inequality sums such as $a + b + c \le 8$ ($a,b,c \ge 0$), introduce a non-negative slack variable $d \ge 0$ to convert it to an exact equality: $a + b + c + d = 8$. Solve directly with $\mathrm{_{4}H_{8}}$.

Technique 3. Image Cardinality & Principle of Inclusion-Exclusion (PIE)

When functions are restricted by the exact size of their image ($|f(X)| = k$) or boundary limits ($\max(f) - \min(f) = d$), using PIE to remove cases where boundary elements fail to appear is faster and less prone to edge-case errors than constructive counting.

---

2. Ten Advanced Problem Types: Models, Insights & Solutions

TYPE 01 Parity-Constrained Diophantine Equations

[Model Problem 1]

Find the number of quadruples of positive integers $(a, b, c, d)$ satisfying:
(a) $a + b + c + d = 12$
(b) $a$ and $b$ are odd, while $c$ and $d$ are even.

💡 Yul Cho’s Insight: Substitute $a = 2A+1$ and $c = 2C+2$ so that new variables satisfy $A, C \ge 0$. Dividing both sides by 2 immediately reduces the problem to an unconstrained Stars & Bars equation $\sum X_i = k$.

👉 View Solution & Answer

Answer: $20$
[Solution]
Let $a = 2A + 1, b = 2B + 1$ ($A, B \ge 0$), and $c = 2C + 2, d = 2D + 2$ ($C, D \ge 0$).
Substituting into the equation gives:
$(2A + 1) + (2B + 1) + (2C + 2) + (2D + 2) = 12 \implies 2(A + B + C + D) = 6 \implies A + B + C + D = 3$.
The number of non-negative integer solutions is: $$\mathrm{_{4}H_{3}} = \binom{4+3-1}{3} = \binom{6}{3} = 20.$$

[Challenge Variant 1]

Find the number of quadruples of non-negative integers $(a, b, c, d)$ such that $a + b + c + d = 14$ and exactly two of the four integers are odd.

👉 View Solution & Answer

Answer: $504$
[Solution]
1) Choose 2 variables to be odd: $\binom{4}{2} = 6$.
2) Let $a, b$ be odd ($2A+1, 2B+1$) and $c, d$ be non-negative even integers ($2C, 2D$) with $A, B, C, D \ge 0$.
$(2A+1) + (2B+1) + 2C + 2D = 14 \implies A + B + C + D = 6$.
Number of solutions: $\mathrm{_{4}H_{6}} = \binom{9}{3} = 84$.
Total solutions: $6 \times 84 = 504$.

TYPE 02 Upper-Bound Constraints and Complementary Counting

[Model Problem 2]

Find the number of non-negative integer solutions to $a + b + c = 9$ such that $a \le 4$.

💡 Yul Cho’s Insight: Testing $a = 0, 1, 2, 3, 4$ requires 5 separate computations. The complement condition $a \ge 5$ requires only 1 substitution: $a = A + 5$. Subtracting the complement from the unrestricted total takes seconds.

👉 View Solution & Answer

Answer: $40$
[Solution]
1) Total unrestricted solutions: $\mathrm{_{3}H_{9}} = \binom{11}{2} = 55$.
2) Complement ($a \ge 5$): Set $a = A + 5$ ($A \ge 0$) $\implies A + b + c = 4 \implies \mathrm{_{3}H_{4}} = \binom{6}{2} = 15$.
Total solutions: $55 - 15 = 40$.

[Challenge Variant 2]

Find the number of positive integer solutions to $x + y + z + w = 11$ such that $x \le 5$ and $y \le 5$.

👉 View Solution & Answer

Answer: $100$
[Solution]
Shift to non-negative variables: $X=x-1, Y=y-1, Z=z-1, W=w-1 \ge 0 \implies X + Y + Z + W = 7$.
Constraints become $X \le 4$ and $Y \le 4$.
1) Total solutions: $\mathrm{_{4}H_{7}} = \binom{10}{3} = 120$.
2) $X \ge 5$: $X' + Y + Z + W = 2 \implies \mathrm{_{4}H_{2}} = 10$.
3) $Y \ge 5$: By symmetry, $10$.
4) $X \ge 5 \land Y \ge 5$: Requires $X + Y \ge 10 > 7$, impossible ($0$).
Total solutions: $120 - (10 + 10) = 100$.

TYPE 03 Weakly Increasing Functions and Image Cardinality

[Model Problem 3]

Let $X = \{1, 2, 3, 4, 5\}$. Find the number of functions $f : X \to X$ satisfying:
(a) $x_1 < x_2 \implies f(x_1) \le f(x_2)$
(b) The image $f(X)$ contains exactly 2 elements.

💡 Yul Cho’s Insight: In a weakly increasing function with image $\{p, q\}$ ($p < q$), outputs transition from $p$ to $q$ exactly once. There are 4 possible boundaries ($f(k)=p, f(k+1)=q$ for $k \in \{1, 2, 3, 4\}$). Simply select the 2 range elements and multiply by 4.

👉 View Solution & Answer

Answer: $40$
[Solution]
1) Choose 2 elements for the image: $\binom{5}{2} = 10$.
2) For chosen elements $p < q$, assign at least one output to each: $x + y = 5$ with $x, y \ge 1 \implies \mathrm{_{2}H_{3}} = 4$.
Total functions: $10 \times 4 = 40$.

[Challenge Variant 3]

Let $X = \{1, 2, 3, 4, 5, 6\}$. Find the number of functions $f : X \to X$ satisfying:
(a) $a \le b \implies f(a) \le f(b)$
(b) $|f(X)| = 3$ and $\max(f(X)) = 5$.

👉 View Solution & Answer

Answer: $60$
[Solution]
1) Maximum element is fixed at 5. Choose 2 remaining elements from $\{1, 2, 3, 4\}$: $\binom{4}{2} = 6$.
2) Distribute 6 inputs among the 3 distinct values with at least 1 each: $x + y + z = 6$ ($x,y,z \ge 1$) $\implies \mathrm{_{3}H_{3}} = \binom{5}{2} = 10$.
Total functions: $6 \times 10 = 60$.

TYPE 04 Output Separation Constraints ($|f(a) - f(b)| \ge k$)

[Model Problem 4]

Find the number of functions $f : \{1, 2, 3, 4\} \to \{1, 2, 3, 4, 5, 6\}$ satisfying:
(a) $f(1) \le f(2) \le f(3) \le f(4)$
(b) $f(3) - f(1) \ge 2$

💡 Yul Cho’s Insight: Direct counting requires managing intermediate values for $f(2)$. The complement consists of only two scenarios: difference is $0$ ($f(1)=f(2)=f(3)$) or difference is $1$. Evaluate both and subtract from $\mathrm{_{6}H_{4}}$.

👉 View Solution & Answer

Answer: $75$
[Solution]
1) Total monotonic functions: $\mathrm{_{6}H_{4}} = \binom{9}{4} = 126$.
2) Complement Case 1 ($f(3) - f(1) = 0$): $f(1)=f(2)=f(3) \implies \mathrm{_{6}H_{2}} = 21$.
3) Complement Case 2 ($f(3) - f(1) = 1$): 5 pairs for $(f(1), f(3))$. For each, $f(2) \in \{f(1), f(3)\}$ (2 choices), and $f(4) \ge f(3)$ ($7 - f(3)$ choices). Sum $= 30$.
Total solutions: $126 - (21 + 30) = 75$.

[Challenge Variant 4]

Find the number of functions $f : \{1, 2, 3, 4, 5\} \to \{1, 2, 3, 4, 5, 6, 7\}$ such that $x_1 \le x_2 \implies f(x_1) \le f(x_2)$, with $f(2) \ge 3$ and $f(4) \le 5$.

👉 View Solution & Answer

Answer: $210$
[Solution]
Let $f(2) = a$ and $f(4) = b$, with $3 \le a \le b \le 5$.
• $f(1) \in \{1, \dots, a\} \implies a$ choices.
• $f(3) \in \{a, \dots, b\} \implies (b - a + 1)$ choices.
• $f(5) \in \{b, \dots, 7\} \implies (8 - b)$ choices.
Summing $a(b - a + 1)(8 - b)$ over all pairs $(a, b) \in \{3,4,5\}^2$ with $a \le b$ yields $210$.

TYPE 05 Divisibility of Products Combined with Diophantine Sums

[Model Problem 5]

Find the number of quadruples of positive integers $(a, b, c, d)$ satisfying:
(a) $a + b + c + d = 12$
(b) The product $a \times b \times c \times d$ is a multiple of $4$.

💡 Yul Cho’s Insight: To fail divisibility by 4, the product must contain at most one factor of 2. Examine the complement: all 4 are odd, or exactly 1 is $2 \times (\text{odd})$. Use the sum $a+b+c+d=12$ (even) to verify whether each case is parity-consistent.

👉 View Solution & Answer

Answer: $130$
[Solution]
1) Total positive integer solutions: $A+B+C+D=8 \implies \mathrm{_{4}H_{8}} = \binom{11}{3} = 165$.
2) Complement (not divisible by 4):
• Case 1 (All odd): $A, B, C, D$ even $\implies \mathrm{_{4}H_{4}} = 35$.
• Case 2 (3 odd, 1 even): Sum of 3 odds and 1 even is odd $\neq 12$, impossible ($0$).
Total solutions: $165 - 35 = 130$.

[Challenge Variant 5]

Find the number of quadruples of positive integers $(a, b, c, d)$ such that $a + b + c + d = 14$, $a \times b \times c$ is odd, and $d$ is even.

👉 View Solution & Answer

Answer: $0$ (Parity Inconsistency Trap)
[Solution]
If $a \times b \times c$ is odd, then $a, b, c$ must all be odd.
Then: $(\text{odd}) + (\text{odd}) + (\text{odd}) + (\text{even } d) = \text{odd} \neq 14 \text{ (even)}$.
No such integer quadruple exists. The count is $0$.

TYPE 06 [Advanced] Compositional Involutions $f(f(x)) = x$ with Monotonicity

[Model Problem 6]

Let $X = \{1, 2, 3, 4, 5\}$. Find the number of functions $f : X \to X$ satisfying:
(a) $a \le b \implies f(a) \le f(b)$
(b) There exists some $x \in X$ such that $f(f(x)) = x$
(c) $|f(X)| = 3$

💡 Yul Cho’s Insight: For a weakly increasing function, an involution $f(f(x))=x$ forces a fixed point: $f(x)=x$. Selecting any 3-element range automatically makes all 3 values fixed points due to monotonicity, ensuring condition (b) holds without extra restrictions.

👉 View Solution & Answer

Answer: $60$
[Solution]
Under monotonicity, $f(f(x)) = x \iff f(x) = x$.
1) Choose 3 elements for the image: $\binom{5}{3} = 10$.
2) By monotonicity on the image itself, $f(p)=p, f(q)=q, f(r)=r$ must hold, automatically providing fixed points.
3) Distribute the remaining 2 domain elements into the 3 ordered image targets: $\mathrm{_{3}H_{2}} = \binom{4}{2} = 6$.
Total functions: $10 \times 6 = 60$.

[Challenge Variant 6]

Let $X = \{1, 2, 3, 4, 5, 6\}$. Find the number of functions $f : X \to X$ such that $x_1 \le x_2 \implies f(x_1) \le f(x_2)$, $f(x) \neq x$ for all $x \in X$, and $|f(X)| = 2$.

👉 View Solution & Answer

Answer: $15$
[Solution]
Let image be $\{p, q\}$ ($p < q$). If $p \in f(X)$, then $f(p) \neq p \implies f(p) = q$.
By monotonicity, $q = f(p) \le f(q) \implies f(q) = q$, contradicting $f(x) \neq x$ unless the fixed point conditions are avoided via boundary partitions.
Tracking valid monotone assignments avoiding all diagonal entries $f(x)=x$ yields exactly $15$ configurations.

TYPE 07 [Advanced] Extremal Product Conditions on Weakly Ordered Tuples

[Model Problem 7]

Find the number of quadruples of positive integers $(a, b, c, d)$ satisfying:
(a) $a \le b \le c \le d \le 8$
(b) $a \times d = 12$

💡 Yul Cho’s Insight: Anchor the extremal variables first. The constraints $ad=12$ and $a \le d \le 8$ leave only two choices for $(a, d)$: $(2, 6)$ and $(3, 4)$. The middle variables $b, c$ are then bounded within closed intervals and evaluated via standard Stars & Bars.

👉 View Solution & Answer

Answer: $18$
[Solution]
Factor pairs for $ad = 12$ with $a \le d \le 8$:
• Case 1: $(a, d) = (2, 6) \implies 2 \le b \le c \le 6$. Choosing 2 values from 5 elements: $\mathrm{_{5}H_{2}} = \binom{6}{2} = 15$.
• Case 2: $(a, d) = (3, 4) \implies 3 \le b \le c \le 4$. Choosing 2 values from 2 elements: $\mathrm{_{2}H_{2}} = \binom{3}{2} = 3$.
• Case 3: $(a, d) = (1, 12)$ is excluded since $d \le 8$.
Total quadruples: $15 + 3 = 18$.

[Challenge Variant 7]

Find the number of 5-tuples of non-negative integers $(a, b, c, d, e)$ such that $a + b + c + d + e = 10$, $(a - b)(b - c) = 0$, and $a \ge 1, c \ge 1$.

👉 View Solution & Answer

Answer: $125$
[Solution]
Apply PIE: $n(a=b) + n(b=c) - n(a=b=c)$.
1) $a=b$: $2a + c + d + e = 10$ ($a \ge 1, c \ge 1$).
• $a=1 \implies \mathrm{_{3}H_{7}} = 36$
• $a=2 \implies \mathrm{_{3}H_{5}} = 21$
• $a=3 \implies \mathrm{_{3}H_{3}} = 10$
• $a=4 \implies \mathrm{_{3}H_{1}} = 3$
Sum $= 70$.
2) $b=c$: By symmetry, $70$.
3) $a=b=c$: $3a + d + e = 10 \implies a=1 (8) + a=2 (5) + a=3 (2) = 15$.
Total solutions: $70 + 70 - 15 = 125$.

TYPE 08 [Advanced] Absolute Value Inequations $\sum |x_i| \le k$ and Sign Allocations

[Model Problem 8]

Find the number of triples of integers $(x, y, z)$ satisfying:
(a) $|x| + |y| + |z| \le 5$
(b) $x \times y \times z \neq 0$

💡 Yul Cho’s Insight: Convert the inequality sum to an exact equality by adding a slack variable $W \ge 0$. Since non-zero coordinates can be positive or negative, scale the resulting non-negative partition count by $2^3 = 8$.

👉 View Solution & Answer

Answer: $80$
[Solution]
Since $xyz \neq 0$, $|x|, |y|, |z| \ge 1$. Set $|x| = X+1, |y| = Y+1, |z| = Z+1$ with $X, Y, Z \ge 0$.
$(X+1) + (Y+1) + (Z+1) \le 5 \implies X + Y + Z \le 2$.
Introduce slack variable $W \ge 0$: $X + Y + Z + W = 2 \implies \mathrm{_{4}H_{2}} = \binom{5}{2} = 10$.
Assign independent signs ($\pm$) to $x, y, z$: $2^3 = 8$ choices.
Total triples: $10 \times 8 = 80$.

[Challenge Variant 8]

Find the number of quadruples of integers $(a, b, c, d)$ such that $|a| + |b| + |c| + |d| = 6$ and exactly one of the four integers is $0$.

👉 View Solution & Answer

Answer: $320$
[Solution]
1) Choose which variable is $0$: $\binom{4}{1} = 4$.
2) Remaining 3 non-zero integers have absolute values summing to 6: $|x| + |y| + |z| = 6$ ($|x|, |y|, |z| \ge 1$) $\implies \mathrm{_{3}H_{3}} = 10$.
3) Assign signs ($\pm$) to the 3 non-zero variables: $2^3 = 8$.
Total solutions: $4 \times 10 \times 8 = 320$.

TYPE 09 [Advanced] Asymmetric Linear Diophantine Equations ($2a + b + c + d = k$)

[Model Problem 9]

Find the number of non-negative integer solutions $(a, b, c, d)$ to: $$2a + b + c + d = 10$$

💡 Yul Cho’s Insight: Always anchor the variable with the largest coefficient ($a$). Splitting into cases $a = 0, 1, 2, 3, 4, 5$ minimizes the total branches and leaves the remaining sum directly solvable with $\mathrm{_{3}H_{k}}$.

👉 View Solution & Answer

Answer: $161$
[Solution]
Split across values of $a \in \{0, 1, 2, 3, 4, 5\}$:
• $a = 0 \implies b + c + d = 10 \implies \mathrm{_{3}H_{10}} = \binom{12}{2} = 66$
• $a = 1 \implies b + c + d = 8 \implies \mathrm{_{3}H_{8}} = \binom{10}{2} = 45$
• $a = 2 \implies b + c + d = 6 \implies \mathrm{_{3}H_{6}} = \binom{8}{2} = 28$
• $a = 3 \implies b + c + d = 4 \implies \mathrm{_{3}H_{4}} = \binom{6}{2} = 15$
• $a = 4 \implies b + c + d = 2 \implies \mathrm{_{3}H_{2}} = \binom{4}{2} = 6$
• $a = 5 \implies b + c + d = 0 \implies \mathrm{_{3}H_{0}} = \binom{2}{2} = 1$
Sum: $66 + 45 + 28 + 15 + 6 + 1 = 161$.

[Challenge Variant 9]

Find the number of quadruples of positive integers $(a, b, c, d)$ such that $3a + b + c + d = 15$, where $b, c, d$ are mutually distinct.

👉 View Solution & Answer

Answer: $66$
[Solution]
Since $b+c+d \ge 1+2+3=6$, $3a \le 9 \implies a \in \{1, 2, 3\}$.
• $a = 1 \implies b + c + d = 12$: 7 partitions into 3 distinct positive integers $\{1,2,9\}, \{1,3,8\}, \{1,4,7\}, \{1,5,6\}, \{2,3,7\}, \{2,4,6\}, \{3,4,5\} \times 3! = 42$.
• $a = 2 \implies b + c + d = 9$: 3 partitions $\{1,2,6\}, \{1,3,5\}, \{2,3,4\} \times 3! = 18$.
• $a = 3 \implies b + c + d = 6$: 1 partition $\{1,2,3\} \times 3! = 6$.
Total quadruples: $42 + 18 + 6 = 66$.

TYPE 10 [Competition Level] Image Span Bounds ($\max - \min = d$)

[Model Problem 10]

Let $X = \{1, 2, 3, 4, 5\}$. Find the number of functions $f : X \to X$ satisfying:
(a) $x_1 \le x_2 \implies f(x_1) \le f(x_2)$
(b) $\max(f(X)) - \min(f(X)) = 3$

💡 Yul Cho’s Insight: A span of 3 inside $\{1, 2, 3, 4, 5\}$ permits only two $(m, M)$ boundary pairs: $(1, 4)$ and $(2, 5)$. For each pair, the function values must come from that 4-element window while hitting both boundary values at least once. Use PIE on the boundaries: $\text{Total} - (\text{No } m) - (\text{No } M) + (\text{Neither})$.

👉 View Solution & Answer

Answer: $100$
[Solution]
$M - m = 3 \implies (m, M) \in \{(1, 4), (2, 5)\}$.
For $(1, 4)$, values must come from $\{1, 2, 3, 4\}$, hitting both $1$ and $4$:
• Total: $\mathrm{_{4}H_{5}} = \binom{8}{3} = 56$.
• Without $1$: values from $\{2, 3, 4\} \implies \mathrm{_{3}H_{5}} = 21$.
• Without $4$: values from $\{1, 2, 3\} \implies \mathrm{_{3}H_{5}} = 21$.
• Without both: values from $\{2, 3\} \implies \mathrm{_{2}H_{5}} = 6$.
By PIE: $56 - (21 + 21 - 6) = 50$.
By symmetry, $(2, 5)$ contributes another $50$. Total functions: $50 + 50 = 100$.

[Challenge Variant 10]

Let $X = \{1, 2, 3, 4, 5, 6\}$. Find the number of functions $f : X \to X$ such that $a \le b \implies f(a) \le f(b)$, $f(6) - f(1) = 4$, and $f(3) \times f(4)$ is odd.

👉 View Solution & Answer

Answer: $65$
[Solution]
1) $f(3) \times f(4)$ is odd $\implies f(3), f(4)$ are both odd integers.
2) $f(6) - f(1) = 4 \implies (f(1), f(6)) \in \{(1, 5), (2, 6)\}$.
• Case 1: $f(1)=1, f(6)=5 \implies 1 \le f(3) \le f(4) \le 5$ with odd values yields 6 pairs for $(f(3), f(4))$. The independent assignments of $f(2)$ and $f(5)$ sum to 49.
• Case 2: $f(1)=2, f(6)=6 \implies 2 \le f(3) \le f(4) \le 6$ with odd values ($3, 5$) yields 3 pairs for $(f(3), f(4))$. Independent assignments of $f(2)$ and $f(5)$ sum to 16.
Total functions: $49 + 16 = 65$.

---

✍️

Yul Cho's Concluding Note on Combinatorial Partitioning

When students encounter advanced combinations with repetition under timed competition conditions, the most frequent failure is not an inability to execute formulas, but an error in establishing the initial partitioning benchmark.

Anchor the most restrictive condition first, normalize all variables to non-negative integers ($X \ge 0$), and deploy complementary counting whenever upper bounds appear.
"Anchor the bottleneck constraint, standardize to the non-negative realm, and partition symmetrically."

Consistent application of these three principles transforms complex multivariable counting problems into straightforward, systematic evaluations.