0
$\begingroup$

I'm writing a program to analyze the maximum unique sequences of data in a string, given certain sets of two can be interpreted in two ways. There's a bit of math that I can't figure out, I've written it here as a brainteaser:

N people are standing in a line, shoulder to shoulder. Each person can hold hands only with the person on either side of them, the ordering of the line cannot be rearranged. Each person can only hold hands with one other person at a time. The people on the ends of the line only have one person with whom they can hold hands, while the people in the middle can hold hands with the person on either side of them. Given N people in a line, write a formula to generalize the number of unique ways the people in the line can hold hands. Assume that nobody holding hands is possible.

For example, PPP could be arranged in the following ways:

P P P (nobody holding hands)

PP P

P PP

This is reminiscent of the handshake problem, but it's distinct in that the person at the end of the line cannot shake hands with the person at the beginning of the line - he can only shake hands with the persons next to him.

Is there a class of formulas or algorithms that deal with this type of problem, where you are looking for combinations, but cannot reorganize the dataset at all? If not, can anyone give me pointers in the right direction or solve this brain teaser outright?

$\endgroup$
  • $\begingroup$ To add to Mike's answer, I want to respond to your question regarding facing "this type of problem". I would say the type is combinatorial, and I am also trying to improve my skill in this field. Most combinatorial problems can be tackled with an understanding of: strings, permutations, inclusion-exclusion, recurrence relations, and generating functions. This is more of a toolbox than a "class of formulas", but that is sort of the point with combinatorial problems. Part of the puzzle is picking the right tool. $\endgroup$ – A.E Sep 4 '14 at 16:16
5
$\begingroup$

Let $a_n$ be the number of ways the line of n people are holding hands. I think it makes sense for $a_0=1$ (an empty set with no one holding hands) and $a_1=1$. If you're not comfortable defining $a_0$, it should be easy to see that $a_2=2$.

Start with the front of the line. Either the first person is holding hands with no one or the first and second people are holding hands. The rest of the line follows the same rules. Therefore, we have $a_n=a_{n-1}+a_{n-2}$.

This recurrence equation should look extremely familiar to you.

$\endgroup$
  • 1
    $\begingroup$ This problem is very similar to the one that motivated the earliest known discussion of this recurrence. The sequence was discussed by several Hindu mathematicians around 1300 years ago in connection with the number of ways of composing an N-syllable line of poetry from words of either 1 or 2 syllables. Here the 1 and 2-syllable words correspond to people who are not holding hands, or to pairs of hand-holders. $\endgroup$ – MJD Sep 4 '14 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.