Search code examples
algorithmmathpuzzle

Number of ways of taking `N` candies

I have a problem and I don't know how I can start to solve it. Do you know someone a formula, algorithm or type of problems like this?

I have only number N, N candies, and I need to count the number of ways of taking N candies, but except the first candy taken, the candy taken must be adjacent to one of previous candies taken before. For example if N = 3 there are 4 ways of taking:

  • Taking candy number 1 first; then candy 2, 3.
  • Taking candy number 2 first; then 1, 3.
  • Taking candy number 2 first; then 3, 1.
  • Taking candy number 3 first; then candy 2, 1.
Solution

  • The number of ways for n candies is the sum of the n-1th row of pascal's triangle.