next up previous
Next: The Main Calculation Up: Counting snail venom Previous: Example Application 2

Enumerations related to snail venom.

We define a language L to be an arbitrary subset of . Associated to a language we have a power series in two variables b and w where

and is the number of words in L which involve exactly m copies of the letter B and n copies of the letter

(1)
If the language consists of all words which do not involve W then whenever n>0, and for every m since there is exactly one word in the language of length m involving no Thus the power series is

(2)
If the language consists of all words in of length t where t is fixed, then

If we further specify that t=3 to give the language we have

In this case the power series collapse to being a polynomial expression, since all save a finite number of coefficients vanish. Notice that the coefficients here are drawn from a row of Pascal's triangle, and another way of describing is To understand this, think of + as being ``or'' and multiplication (juxtaposition) as being ``and then''. In this sense exactly describes the Each word in is of the form: B or W, then B or W, then B or

(3)
If the language consists of all words where there are no juxtaposed Ws and no juxtaposed Bs then there is one word in of length 0, the empty word, and exactly two words of every other length. Thus

The particular languages of interest in the investigation of snail venom are the ones satisfying the following five conditions.

(i)
The words involve an even number of occurrences of
(ii)
The words begin and end with a letter
(iii)
Words must not contain the subword
(iv)
Words must not contain the subword BBB (i.e. you must not have three consecutive occurrences of
(v)
Suppose a word involves exactly 2k occurrences of the letter B. Label them from the left the Between at least one -th and 2i-th occurrence of B, there must at least two consecutive occurrences of

The language S specified by the first three conditions are all possible words associated with snail venom. The language defined by all five these conditions are the so-called inaccessible words, and are exactly those which do not admit of synthesis by a specific manufacturing process.

The language S is defined by conditions and Let The definition of yields that

or more formally

If you wish to see you many words there are in this language of length 30 and involving 8 occurrences of B (and so 22 occurrences of W) you look at the coefficient of and this is precisely the coefficient of in This can be determined in a trice by almost any computer algebra system (AXIOM, MAPLE, REDUCE etc).

Now we proceed to the main calculation, where we also impose conditions and and are particularly interested in the cases where there are 4, 6 and 8 occurrences of B, and when the word lengths does not happen to exceed 30. This final constraint can be imposed at the very end of the calculations by truncating the appropriate polynomial if necessary.



next up previous
Next: The Main Calculation Up: Counting snail venom Previous: Example Application 2



Geoff C Smith
Tue Jun 9 10:45:46 BST 1998