MathDB
Recursion

Source: 2015 AIME 2 Problem 10

March 26, 2015
probability

Problem Statement

Call a permutation a1,a2,…,ana_1,a_2,\ldots,a_n quasi-increasing if ak≤ak+1+2a_k\le a_{k+1}+2 for each 1≤k≤n−11\le k\le n-1. For example, 5432154321 and 1425314253 are quasi-increasing permutations of the integers 1,2,3,4,51,2,3,4,5, but 4512345123 is not. Find the number of quasi-increasing permutations of the integers 1,2,…,71,2,\ldots,7.
Back to ProblemsView on AoPS