Friends pairing problem

#1

how to reach to the recurrence relation.not getting any intution…can anyone explain the problem

#2

@S18LPC-OL0078
According to the problem, suppose you have N friends. Let f(N) be the number of ways N friends can go to a party.For the last friend or the Nth friend, you have 2 options

  1. Last friend or Nth friend will go in a pair. So for the Nth friend you need to choose a friend from N-1 friends to form a pair. So f(N) will depend upon (N-1)C1 f(N-2)
  2. Last friend or Nth friend will go single/alone. So f(N) will depend upon f(N-1)

So the recurrence relation will be like this:
f(N)=f(N-1) + (N-1)C1 * f(N-2)

1 Like
#3

not getting 1st option reccurence…have you used combination property?

#4

why (n-1) …we can directly write f(n-2)

#5

f(N-1) in the equation is for the case when the Nth person chooses to go alone. Because when he chooses to go alone the number of ways will simply depend on remaining N-1 friends
But if he chooses to go in a pair, he will have to choose one friend from N-1 remaining friends .By permutation and combination it will be (N-1)C1. And now the number of ways will depend on remaining N-2 friends ie f(N-2)

#6

code not accepting …saying wrong answer

#7

code link - https://ide.codingblocks.com/s/178178

#8

@S18LPC-OL0078 https://ide.codingblocks.com/s/178196
Check now if it works. I have changed the data type to long long int as for larger values of n…the answer will be very large.

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.