Even A Odd B

Probability Level 4

An alphabet with two letters $A$ and $B$ has two rules for creating words:

$1.$ Any $A$ must be part of a string containing an even number of $A$ 's.

$2.$ Any $B$ must be part of a string of containing an odd number of $B$ 's.

For example, two six-letter words could be $BBBAAB$ and $AAAAAA$ but $ABABBB$ would not be valid.

How many valid $20$ letter words ending in $B$ are there?

The answer is 1035.

1 solution

Jeremy Galvagni
Jun 13, 2018

$W(n,A)$ represents the number of $n$ letter words ending with $A$ , $W(n,B)$ likewise. $W(n)=(X,Y)$ where $X=W(n,A)$ , $Y=W(n,B)$

Some small words: $W(1)=(0,1)$ because the only valid word is $B$ .

$W(2)=(1,0)$ because the only valid word is $AA$

$W(3)=(1,2$ ). Valid words are $BAA$ , $AAB$ , $BBB$ .

One recursive formula: $W(n,A)=W((n-2),A)+W(n-2),B)$ because you can add $AA$ to the end of any word to make a new word ending in an even number of $A$ .

Another recursive formula: $W(n,B)=W((n-2),B)+W(n-1),A$ ) because you can add $BB$ to the end of a word already ending with an odd number of $B$ or you can add a single $B$ to a word ending with $A$ .

Now we can just make a table to solve

$n$	$A$	$B$	$A+B$
1	0	1	1
2	1	0	1
3	1	2	3
4	1	1	2
5	3	3	6
6	2	4	6
7	6	5	11
8	6	10	16
9	11	11	22
10	16	21	37
11	22	27	49
12	37	43	80
13	49	64	113
14	80	92	172
15	113	144	257
16	172	205	377
17	257	316	573
18	377	462	839
19	573	693	1266
20	839	$\boxed{1035}$	1874

Incidentally, the $A+B$ column is this sequence so an alternate way of solving is to take $a(20)-a(18)=1874-839=\boxed{1035}$

Even A Odd B

The answer is 1035.

1 solution

0 pending reports