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)
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?