Further explanation needed with combinatorics(hackerearth aryan-and-consulting-sessions)?

Question

I am new to combinatorics problems and trying to understand how to solve this problem, I understand that nC2 is finding the numbers where order matters, but after that I have no idea how to proceed further in the math problem. Please explain further, no code needed. https://www.hackerearth.com/practice/math/combinatorics/inclusion-exclusion/practice-problems/algorithm/aryan-and-consulting-sessions-0e0656ab/

Answer 1

Let students are graph vertices, possible pairs are edges. This graph is complete K_n, number of edges is p = n*(n-1)/2 (nC2 as you wrote)

We need to find number of edge covers for this graph.

I wanted to count numbers of edge covers containing from (p+1)/2 to p edges, but seems values are too big and this is rather complex problem.

But we can find formula for counting overall quantity of edge covers for complete graph K_n here in OEIS

 a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n, k)*2^binomial(k, 2)

You also need to calculate binomial coefficients modulo m