In the hint f(n) = f(n-1)+(n-1)*f(n-2) is explained but when we take the new number as single we have to consider all the combinations that are possibles from n-1 friends
which is( f(n-1) + combinations of n-1 friends having no single ) so in case of even no n-1 will be odd so we can’t have all paired up so it will be same but if n is odd n-1 will be even so we will have to calculate the other term for odd n
Doubt in friends pairing hint
@tilakparth123 Its a little tough to understand what you are saying but I will try to explain the hint given.
lets say f(n) is the total number of arrangements we have for n people. Now we have to solve for n+1.
Case 1 :
when n+1 th friend stays single, in that case total permutations is f(n) because you can simply add this friend to all the arrangements done before without disturbing them.
Case 2:
when you decide to pair n+1 th friend with someone, now he can choose from n friends and everytime he chooses a friend the remaining n-1 friends can be arranged in f(n-1) ways without the loss of generality.
so arrangements in this case are n*f(n-1);
Therefore f(n+1)=f(n)+(n)*f(n-1).
It doesn’t matter if n is odd or even, this equation is formed without the loss of generality.
So start with f(1)=1, f(2)= 2 as base cases and run the formula for remaining.
I am saying in case 1 when you add just f(n) you are missing cases
for eg when n=3 the cases in which 3 is single are {1,2},3 and {1},{2},{3} and for n=2 the single case are {1}{2} so if I take the case 1 I will miss the case{1,2},3
And also when n=2 there is only one case possible {1,2}
No there are two cases here, both can pair up or stay single.
You see we are adding both these cases. We are adding all the cases for n=2 when 3rd is single.
Its not like we are taking only those cases in which 2 is single, we are considering all permutations for 2.
f(2) is all cases for 2.
Thanks, I misread the question, I thought I have to find the no of ways in which one person is single but they were asking total ways possible