How many Combination-Schemes?Given a set K with a commutative, associative binary operation ⋅ , and given a set of n distinct elements of K, how many ways are there of combining the n elements into a single product? Suppose the 'number of ways' is an. Consider the first few cases: n=1 Only one element in the set: no combination to be done; we already have the 'product of n elements'. There is only one way of doing nothing! So a1 = 1. n=2 How many ways of combining two elements? Just one: the product is a ⋅ b, which is the same as b ⋅ a. So a2 = 1. n=3 Things get mildly interesting. We can't combine all three elements in a single act of combination, because the given operation is binary: it combines just two elements. So we have to do it step by step. We must pick two elements out of the set, on which to perform the first act of combination. The order of the elements doesn't matter. The number of ways of picking two elements out of a set of three is three. The remaining element gets combined with the result of the first combination. Overall, there are three ways of combining three elements: x = a⋅(b⋅c), x = b⋅(a⋅c), x = c⋅(a⋅b) So a3 = 3. n=4 At this point it pays to look at the inverse of the combination process, i.e. at the process of splitting a pile of 4 elements into two piles, to be followed by the further splitting of all piles that contain more than one element, until we have four piles, each consisting of just one element. So, the first act of splitting splits the pile of four either into a pile of one and a pile of three, or into two piles of two. There are four ways of splitting 4 into 1+3 (choose which element gets split off on its own); three ways of splitting 4 into 2+2. The 7 possible splittings are a|bcd , b|acd , c|abd , d|abc , ab|cd , ac|bd , ad|bc In the first 4 cases, the pile of three then requires further splitting. In each case there are a3 ways of doing it. In the remaining 3 cases, each pair requires further splitting, but there is only one way of spltting a pair (a2=1). In sum, we get \[ \dpi{130} a_4 = 4 a_1.a_3 + 3 a_2.a_2 = 12 + 3 = 15 \] n=5 Again consider the first act of splitting. Five can be split into 1+4 (5 ways); or into 2+3 (10 ways). In the first case, the pile of 4 must be further split, which can be done in a4 ways; in the second, the pile of 2 can be split in a2 ways (= one way), the pile of 3 in a3 ways. Thus \[ \dpi{130} a_5 = 5 a_1.a_4 + \frac{5.4}{1.2} a_2.a_3 = 75 + 30 = 105 \] n=6 a6 is given by the formula \[ \dpi{130} a_6 = 6\, a_1.a_5 + \frac{6.5}{1.2}\, a_2.a_4 + {\textstyle\frac{1}{2}}\, \frac{6.5.4}{1.2.3} a_3.a_3= 630 + 225 + 10.3.3 = 945 \] Here 6.5/1.2 is the number of ways of selecting a pair of elements out of six; and (6.5.4)/(1.2.3) is the number of ways of selecting a set of three elements out of six (6 ways of choosing the first element, 5 ways of choosing the second, 4 ways of choosing the third; but this will give 6 times too many choices, because we don't care about the order of the three elements). The factor of ½ comes in because while 20 is indeed the number of ways of choosing 3 elements out of 6, the number of ways of splitting the 6 into 3+3 is only half that, because each splitting will come up twice as all the triples are enumerated. Time to take stock, and contemplate the sequence we are growing:
I expect you will be able to see the pattern. (Check: according to the pattern, one would expect a0 to be -1.[:)]) When you have it, see if you can work out the reason for it. For help, proceed to Part II. back to Boolean Algebras |