Question of the Day (03-Apr-12) Views : 1392 Rated 4.7 by 3 Users   Let f(n, k) denote the number of ways in which the set S = {1, 2, 3, 4,… n} can be partitioned into k non-empty subsets. For example, f(3, 2) = 3 since we can partition {1, 2, 3} into 2 subsets in 3 ways: {1, 2}{3}; {1, 3}{2} and {2, 3}{1}.  Similarly f(4, 2) = 7 since there are 7 ways to partition {1, 2, 3, 4} into 2 sets: {1, 2}{3, 4}; {1, 3}{2, 4}; {1, 4}{2, 3}; {1, 2, 3}{4}; {1, 2, 4}{3}; {1, 3, 4}{2}; {1}{2, 3, 4}. We assume that f(0, 0) = 1. What is the value of f(7, 4) if f(6, 3) = 90 and f(6, 4) = 65? -----------------------

 Consider two kinds of ways in which {1, 2, 3,…, 7} can be divided into 4 subsets:

A. {7} is one of the four sets and there are three other sets. E.g. {1}{5, 3, 2}{4, 6}{7}

B. 7 occurs with some other number(s) in one of the sets e.g. {1, 6}{4}{3, 5}{2, 7}

Now, the number of ways of type A are equal to the number of ways of dividing {1, 2, 3,…, 6} into 3 subsets.

The number of ways of type B are equal to the number of ways of dividing {1, 2, 3,…, 6} into 4 subsets multiplied by 4 (since we could ‘attach’ 7 to any of the four sets).

∴ f(7, 4) = f(6, 3) + 4f(6, 4)

In general, f(n, k) follows the recursion f(n, k) = k ×  f(n– 1, k) + f(n – 1, k – 1)

∴ f(7, 4) = 90 + 4 × 65 = 350