Stars and Bars (AIME / USAJMO / AMO)

Proof-style AIME / USAJMO / AMO statements — develop a full argument; type only the final answer.

Proof track: treat each problem as a full olympiad writeup on paper. Here you only enter the final answer (integer or short expression).

Easy Medium Hard AIME / USAJMO / AMO

Stars and Bars: core idea

Bijections and generating functions.

Example problem: hint and answer

**(Proof track.)** Prove that the number of positive integer solutions to $x_1+\cdots+x_k=n$ with $x_1\le\cdots\le x_k$ equals the number of partitions of $n$ into exactly $k$ parts. Using your proof, evaluate that number for $n=15$ , $k=5$ . Enter the integer.

Hint: Standard partition listing / Ferrers duality. Answer: 30.

Practice (9 problems — type your answers)

No proof submission required — answers only.

1. **(Proof track.)** Prove a bijection between nonnegative solutions of $y_1+2y_2+\cdots+m y_m=n$ and partitions of $n$ with parts at most $m$ . For $n=12$ , $m=4$ , how many such partitions are there?
2. **(Proof track.)** Using inclusion-exclusion, prove a closed form for the number of positive solutions to $x_1+\cdots+x_5=20$ with each $x_i\le 6$ . Enter that number.
3. **(Proof track.)** Prove that the number of lattice paths $(0,0)\to(n,n)$ with steps $(1,0),(0,1)$ not rising above $y=x$ is the Catalan number $C_n$ . Enter $C_8$ .
4. **(Proof track.)** Prove that the number of ways to choose $k$ elements from $\{1,\ldots,n\}$ with no two consecutive equals $\binom{n-k+1}{k}$ . For $n=25$ , $k=6$ , enter the value.
5. **(Proof track.)** Show that the number of compositions of $n$ with parts in $\{1,2\}$ is $F_{n+1}$ . Enter the number of such compositions of $12$ .
6. **(Proof track.)** Prove via generating functions that the number of nonnegative solutions to $x+2y+3z=30$ equals the coefficient of $x^{30}$ in $1/((1-x)(1-x^2)(1-x^3))$ . Enter that coefficient.
7. **(Proof track.)** Using Möbius inversion on the lattice of positive integers under divisibility, prove a formula for the number of $k$ -tuples of positive integers summing to $n$ with gcd $1$ . For $k=4$ , $n=12$ , enter that count.
8. **(Proof track.)** Prove that surjections $[n]\to[k]$ number $k!\{n\atop k\}=\sum_{i=0}^{k}(-1)^{k-i}\binom{k}{i}i^n$ . Enter the number of surjections $[7]\to[3]$ .
9. **(Proof track.)** Establish the hockey-stick identity $\sum_{i=r}^{n}\binom{i}{r}=\binom{n+1}{r+1}$ combinatorially. Using it, evaluate $\sum_{i=3}^{10}\binom{i}{3}$ .