For a positive integer $n$, $S_n$ is the set of positive integer $n$-tuples $(a_1,a_2, \cdots ,a_n)$ which satisfies the following. (i). $a_1=1$. (ii). $a_{i+1} \le a_i+1$. For $k \le n$, define $N_k$ as the number of $n$-tuples $(a_1, a_2, \cdots a_n) \in S_n$ such that $a_k=1, a_{k+1}=2$. Find the sum $N_1 + N_2+ \cdots N_{k-1}$.
Problem
Source: 2016 KMO Senior #4
Tags: combinatorics
Hypernova
12.11.2016 12:02
Recurrence Relation helps here.
khyeon
02.01.2017 08:47
catalan number..
Hypernova
05.01.2017 18:06
Hypernova wrote: Recurrence Relation helps here. The recurrence relation is exactly the Catalan number's recurrence relation.
rkm0959
27.02.2018 18:02
Lol how did I not solve this problem We will work with $b_i= i-a_i$. Obviously $\{a_i\}$ and $\{b_i\}$ are tied with an one-to-one correspondence. We will have $b_1=0$ and $b_i \ge b_{i-1}$, and $b_i \le i-1$. Now it's trivial that we can correspond $\{b_i\}$ with a catalan-like walk! Also, $a_k=1$ and $a_{k+1}=2$ is equivalent with $b_k=k-1$ and $b_{k+1}=k-1$. Look at this as a part of a walk to get $$N_k = C_{k-1} ( C_{n-k+1}- C_{n-k})$$Now it's trivial (using catalan recurrence) that the answer is $C_{n+1}-2C_{n}$