1
$\begingroup$

Possible Duplicate:
Count Exclusive Partitionings of Points in Circle, Closing Double Recurrence?

We have N fixed points in a circle,numbered 1 to N in clockwise order. We can form closed loop of 2 points or 3 points upto N points (let say it size of loop) i.e. by taking any three points, we can form a triangle or by taking two points, a line can be formed, or by 4 points a square can be formed.

A structure is one, which have unique organised loops.

  • It may have one or more than one closed loops.
  • One structure can have loops of different size.
  • No two loops should cross each other.
  • One point can't share more than one loop in a structure.

For Example, say N=8

Possible structures are:

  • loop (1,2,3) if only occurs, it will be one structure.
  • loop (2,3,4) if only occurs, it will be other structure.
  • loop (1,2,3) and loop (6,7,8) will be other structure.
  • loop (2,4,5,6) loop (7,8) will also be an structure.

loop (1,2,4,5) and loop (3,6,8) can't form structure as both will cross each other.

So for N, how many structures are possible?

  • 0
    @joriki Thanks man, Its exactly what I was looking for.2012-08-03

0 Answers 0