[21]

(a) Compute the number of different integer functions h defined on 0, 1,...k for some k ≤ n − log n satisfying h(0) ≤ n and h(i) + i is nonincreasing.

(b) Conclude that the number in Item

(a) is far greater than the number of x’s of length n and complexity k ≤ n − log n.

Comments. Hint for Item (a): The function h(i) starts for k = 0 at some nonnegative value ≤ n. Here δ0 = n − h(0) can be viewed as the first decrease. At every increment of i, the function h(i) can decrease one or more units δi ≥ 1. There are k increments. The sum total is n. Hence we consider n−k units that can be partitioned into k+1 nonnegative integer summands. For every k there are n k

such partitions. Hence there are

n−log n k=0 n k

≥ 2n−1 ways to partition as asked in Item (a). All strings x of length n and complexity k ≥ n − log n have structure functions hx roughly following the diagonal L(i) = n − i. The number of x’s of length n with complexity k ≤ n − log n is at most 2n−K(n)−log n+O(1) by Theorem