PUMaC 2013 · 组合（B 组） · 第 6 题

PUMaC 2013 — Combinatorics (Division B) — Problem 6

[ 6 ] An integer sequence a , a , . . . , a has a = 0, a ≤ 10 and a − a ≥ 2 for 1 ≤ i < n . 1 2 n 1 n i +1 i How many possibilities are there for this sequence? The sequence may be of any length.

解析

[ 6 ] An integer sequence a , a , . . . , a has a = 0, a ≤ 10 and a − a ≥ 2 for 1 ≤ i < n . 1 2 n 1 n i +1 i How many possibilities are there for this sequence? The sequence may be of any length. Solution Suppose K counts the number of sequences with a ≤ d . There are K sequences d n d − 2 with a = d and K with a < d , so we have K = K + K . Lovely; we find K = 1, n d − 1 n d d − 1 d − 2 0 K = 1, and from there get K = 2, K = 3, K = 5, K = 8, K = 13, K = 21, K = 34, 1 2 3 4 5 6 7 8 K = 55, and K 0 = 89. So the answer is 89. 9 1