0
$\begingroup$

So i have a certain problem:

There are n students at an acquaintance party, that haven't known each other before that night. How many ways are there to befriend, if every student get's at least one friend.

SO i'm thinking of using inclusion-exclusion principle. But am not sure how to calculate it. Any help would be appreciated.

$\endgroup$
1
$\begingroup$

We can use simple undirected graphs to solve this problem. Numbers of ways to befriend n students is equal numbers of different simple undirected graphs with n vertices. If every student get's at least one friend, we must subtract the case when exist student which get's no friends. In graf that means that exist isolated vertex. So we have to get numbers of different simple undirected graphs with isolated vertex (with n vertices).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.