MathDB

Number of n-tuples with given condition

Source: 2016 KMO Senior #4

November 12, 2016

combinatorics

Problem Statement

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}

.

Back to Problems View on AoPS