A combinatorics quiz

Let's consider the connexion between two persons from the mothers' side and count the possibilities to express it. E.g., if the connexion is only 1 generation, then there is only 1 possibility to express it:

  1. the mother.

If the connexion is 2 generations, then there are 2 possibilities to express it:

  1. the mother of the mother
  2. the grandmother.

If the connexion is 3 generations, then there are 4 possibilities to express it:

  1. the mother of the mother of the mother
  2. the grandmother of the mother
  3. the mother of the grandmother
  4. the great-grandmother.

If the connexion is 4 generations, then there are 7 possibilities to express it:

  1. the mother of the mother of the mother of the mother
  2. the mother of the mother of the grandmother
  3. the mother of the grandmother of the mother
  4. the grandmother of the mother of the mother
  5. the grandmother of the grandmother
  6. the mother of the great-grandmother
  7. the great-grandmother of the mother.

Now, if the connexion is 100 generations, how many possibilities are there to express it by using only the words "mother", "grandmother", "great-grandmother", "the" and "of"?

Calculate the same for 1000 generations. Can you have the answer in less than 10 seconds? (10'' of computer calculations)

Here is my answer.

Update:

Damn it! I have just guessed an algorithm, that can calculate this in linear time and in less that 1 sec! Can you guess it too? ;o)

Here is my second answer.

Leave a Reply

Your email address will not be published. Required fields are marked *