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 mk ways to assign function values for each partition. (Summing over k gives a combinatorial proof of (6.10).)
6.3 Now dk+1 ≤ (center of gravity) – = 1 –
+ (d1 + · · · + dk)/k. This recurrence is like (6.55) but with 1 – in place of 1; hence the optimum solution is dk+1 = (1 – )Hk. This ...
Get Concrete Mathematics: A Foundation for Computer Science, Second Edition now with O’Reilly online learning.
O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.