Counting the Number of Elements of a Set.

Probability Level 5

Define sets $A_i =\{i, i+1\}$ and $B_i=\{A_1, A_2,.....,A_i\}.$

$F_i$ is the set of all possible sets that can be formed by taking union of one or more elements of $B_i$ . For example, $F_2 =\{A_1, A_2, A_1\cup A_2\}.$

Find the number of distinct elements of $F_{15}$ .

The answer is 5841.

1 solution

Patrick Corn
Oct 1, 2014

Let $f_n = |F_n|$ . The number of elements of $F_{n+1}$ that contain $n+2$ is $f_{n+1}-f_n$ . There are two ways this can be done: either we add $n+2$ to an element of $F_n$ containing $n+1$ , or we add $\{ n+1, n+2 \}$ to an element of $F_{n-2}$ or the empty set.

This gives the recurrence $f_{n+1}-f_n = (f_n-f_{n-1}) + (f_{n-2}+1)$ , which simplifies to $f_{n+1} = 2f_n - f_{n-1} + f_{n-2} + 1.$

Starting with $f_0 = 0$ , $f_1 = 1$ , $f_2 = 3$ and iterating gives $f_{15} = \fbox{5841}$ .

You can see http://oeis.org/A077855 for more information.

Counting the Number of Elements of a Set.

The answer is 5841.

1 solution

0 pending reports