recursion help appreciated During the first expedition to Mars, linguists discov

Question

recursion help appreciated

During the first expedition to Mars, linguists discovercd that the Martian language can be written with the familiar Roman alphabet, which has 21 consonants (b, c, d, f, g, h, j, k, t, m, n, p, q, r, s, t, v, W, X, y, z) and 5 vowels (a, e, i, o, u). All Martian nouns begin with a consonant, followed by one or more vowel consonant pairs. However, no consonant can appear more than once in a single noun, and no vowel can appear more than once in a single noun. Ior example, vux, diyok, and Zobalatt are possible Martian nouns, but x, vuv, grok, d yik and zezelal are not. IIow Inany Martian nouns are nnssible? Your answer must be a number More recent expeditions to Mars have cast doubt on whether the Martian language can really be written with exactly 21 consonants and 5 vowels. Suppose that Martian can be written with c consonants and v vowels where c v Express the number of possible Martian nouns in terms of c and Your answer must be an expression, but it need not be in closed form. for a pattern in your answer to question 2

Explanation / Answer

2Q Ans)Given that,

               Vowels = {a,e,i,o,u}

               Consonants = {b, c, d, f, g, h, j, k, l, m, n, p, q, r, s, t, v, w, x, y, z}

The conditions of forming noun are as follows

            a. All nouns must begin with consonant, followed by one or more vowel- consonant pair.

            b. No vowel or consonant can appear more than once in a noun.

Thus the possible nouns will be in the below forms.

            1. CP1                                      =          21*(5*20) (Possible combinations)      =2100

            2. CP1P2                                           =          21*(5*20)*(4*19)                                  =159600

3. CP1P2P3 =          21*(5*20)*(4*19)*(3*18)                      =8618400

4. CP1P2P3P4 =          21*(5*20)*(4*19)*(3*18)*(2*17)            =293025600

5. CP1P2P3P4P5 =            21*(5*20)*(4*19)*(3*18)*(2*17)*(1*16)=4688409600

Where C = one of the symbol from consonants set

            Pi = ith vowel – consonant pair.

Therefore total nouns following the above two conditions = 2100 + 159600 + 8618400 + 293025600 + 4688409600 = 4990215300

But Given that, the nouns { x, vuv, grok, diyik, zezelah} are not nouns.

Actually these words x, vuv, grok, diyik, zezelah are not following the above mentioned conditions.

So the total number of possible nouns are 4990215300.

------------------------------------------------------------------------------------------------------------------------------------------

3. Ans) Given that, there are c number of consonants,

                                                v number of vowels.

Let F(c,v) be a function representing number of nouns possible with c consonants, and v vowels

Thus by observing the above question’s answer.

The number of possible nouns possible = F(c,v) = c * (v*[c-1]) * G(v-1,c-2)

Where G(a,b) = 1+ (a*b) * G(a-1,b-1) when a!=1 and b!=1

                        = 1 + (a*b)                   when a=1 or b = 1.

Here G(a,b) is a recursive function.

This function is actually adding the combination’s of new vowel – consonant pairs recursively.

For example, Let C = 21 and V = 5

Thus F( 21, 5) = 21 * (5*20) * G(4,19)

                        = 21*(5*20) * (1 + (4*19)*G(3,18))

                        = 21*(5*20)*(1+(4*19)(1+3*18*G(2,17)))

                        = 21*(5*20)*(1+(4*19)(1+3*18*(1+2*17*G(1,16))))

                        = 21*(5*20)*(1+(4*19)(1+3*18*(1+2*17*(1+1*16))))

                        = 21*(5*20)*(1+(4*19)(1+3*18*(1+2*17*17)))

                        = 21*(5*20)*(1+(4*19)(1+3*18*579))

                        = 21*(5*20)*(1+76*31267)

                        = 21*(5*20)*(2376293)

                        =4990215300

Hence Prooved.

Thus the below function F(c,v) is the required function.

F(c,v) = c * (v*[c-1]) * G(v-1,c-2)

Where G(a,b) = 1+ (a*b) * G(a-1,b-1) when a!=1 and b!=1

= 1 + (a*b)                   when a=1 or b = 1.

This function can also be written as c*(v*(c-1)) * {1+(v-1)*(c-2)*{1+(v-2)*(c-3){....... //not recommended by me... :)

If you got any doubt, Feel free to comment on it.

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.