Question

Discrete Math

An AZ is a string of English letters with the property that every ‘a’ in the string precedes every ‘z’ in the string.

For example, each of these strings is an AZ:

bedazzled

organize

paparazzo

zipper (we don’t promise a appears)

cassette (we don’t promise z appears)

monkey (we don’t promise any a or z appears at all)

None of these strings is an AZ:

za

razzmatazz

arizona

lizard

Find a recurrence and appropriate initial conditions for the number of AZzes of length n, n ≥ 0.

Give a brief justification why your recurrence is correct. (I’m not looking for a proof, but you do need to explain yourself.) For your initial conditions, use as many as you need, but no more.

Answer 1

Assuming that strings are made out of 26 Lower case latin alphabets. Any possible AZ string can be one of the 4 types from the following :-

1. String with 0 'a' and 0 'z' Eg : - weryufg

2. String with atleast 1 'a' and 0 'z' Eg :- khabgaaxy

3. String with atleast 1 'z' and 0 'a' Eg :- pxyzktzzce

4. String with atleast 1 'a' followed by atleast 1 'z' Eg : - xyakbaayzzztopzi

Hence , to find number of AZes of length n , we need to find the sum of the number of strings of Type1, Type2 , Type3 and Type 4.

Let the number of strings of Type i of length be N be denoted by S_N[i] . Following Base case can be derieved.

Base Case : -

N = 1

S₁[1] = 24 (all letters except 'a' and 'z')

S₁[2] = 1 (Since length is 1 and we need atleast one 'a'. Hence only 'a')

S₁[3] = 1 (Since length is 1 and we need atleast one 'z'. Hence only 'z')

S₁[4] = 0 (Since length is 1 and we need atleast one 'a' and atleast 1 'z'. Hence it is impossible)

Recurrence Relation

N > 1

1. N letters except 'a' and 'z' means N-1 letters except 'a' and 'z' and 24 remaining choices for the Nth position

Hence , S_N[1] = 24 * S_N-1[1]

2. N letters with atleast 1 'a' and 0 'z' means N-1 letters with atleast 1 'a' and 0 'z' and there are 25 valid letters (all letters except 'z' ) for the Nth position.

N letters with atleast 1 'a' and 0 'z' means N-1 letters with 0 'a' and 0 'z' and the Nth letter is 'a'

Hence , S_N[2] = 25 * S_N-1[2] + S_N-1[1]

3. N letters with atleast 1 'z' and 0 'z' means N-1 letters with atleast 1 'z' and 0 'z' and there are 25 valid letters (all letters except 'z' ) for the Nth position.

N letters with atleast 1 'a' and 0 'z' means N-1 letters with 0 'a' and 0 'z' and the Nth letter is 'z'

Hence , S_N[3] = 25 * S_N-1[3] + S_N-1[1]

4. N letters with atleast 1 'a' and atlleast 1 'z' means N-1 letters with atleast 1 'a' and 1 'z' and there are 25 valid letters (all letters except 'a' ) for the Nth position. {It is necessary to not include 'a' beause all a must preceed all z}.

N letters with atleast 1 'a' and atlleast 1 'z' also means N-1 letters with atleast 1 'a' and 0 'z' and the Nth position is filled by 'z'

Hence ,S_N[4] = 25 * S_N-1[4] + S_N-1[2]