Competition problem — Combinatorics

Library / /149 of 860

Combinatorics Difficulty 4.9 AIME Find the answer

Compute $\sum_{n_{60}=0}^{2} \sum_{n_{59}=0}^{n_{60}} \cdots \sum_{n_{2}=0}^{n_{3}} \sum_{n_{1}=0}^{n_{2}} \sum_{n_{0}=0}^{n_{1}} 1$

Your answer

A number or a short expression. Spacing and $ signs are ignored.

Solution

The given sum counts the number of non-decreasing 61-tuples of integers $\left(n_{0}, \ldots, n_{60}\right)$ from the set $\{0,1,2\}$ . Such 61-tuples are in one-to-one correspondence with strictly increasing 61-tuples of integers $\left(m_{0}, \ldots, m_{60}\right)$ from the set $\{0,1,2, \ldots, 62\}$ : simply let $m_{k}=n_{k}+k$ . But the number of such $\left(m_{0}, \ldots, m_{60}\right)$ is almost by definition $\binom{63}{61}=\binom{63}{2}=1953$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.