Concrete Mathematics: A Foundation for Computer Science, Second Edition

6.1 2314, 2431, 3241, 1342, 3124, 4132, 4213, 1423, 2143, 3412, 4321.

6.2 , because every such function partitions its domain into k nonempty subsets, and there are m^k ways to assign function values for each partition. (Summing over k gives a combinatorial proof of (6.10).)

6.3 Now d_k+1 ≤ (center of gravity) – = 1 – + (d₁ + · · · + d_k)/k. This recurrence is like (6.55) but with 1 – in place of 1; hence the optimum solution is d_k+1 = (1 – )H_k. This ...