Friends pairing problem doubt

#1

why we multiply (n-1)c1 with f(n-2) ?

#2

hi @divesh2000 f(n-2) is the case where you choose to go with a friend. now there are n people currently, one of them is you, so you can choose 1 friend in (n-1) C 1 ways, so we multiply f(n-2) with (n-1)C1

#3

Please make this more clear

#4

suppose,person 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)
why we multiplying this?
clear this doubt with example

#5

@divesh2000 n-1 friends me se choose kara, and the subproblem reduces to n-2 friends, so we call function for f(n-2).

lets take an example
n = 4
either he can go alone or he can take one of his friends
so 4th person, can choose from 3 friends, in 3C1 ways. After he chooses a friend, now n-2. ie 2 people are remaining, so we find answer for f(2)
He has 3 friends and he can choose any of them, this is why all 3 get separate cases so we have to multiply n-1C1 with f(n-2)
We are talking about people here, they are not identical so each person will get a separate case.
for eg friend #4 can choose friend #3, #2, or #1. He has 3C1 ways to do it. Each case will lead to a separate case.

like
4+1 go together -> subproblem -> (2,3)
4+2 -> (1,3)
4+3 -> (1,2)

So we have to add the answer for all 3 cases. Instead of adding 3 times, we simply multiply it with 3.

I hope I have made it clear now

1 Like
#6

Thank you so much for clearing my doubt

1 Like
#7

@divesh2000 dont forget to mark your doubt as resolved :slight_smile:

#8

Sure,i will marked as resolved. :blush:

1 Like