# Number of combinations with restrictions for specific pairs

I have the following problem. Assume that I have $$20$$ different variables, some pairs of which are correlated. The aim is to calculate the number of possible models with, for example, $$5$$ variables, but the subsets must not have any of these correlated pairs. So, firstly, all the possible combinations will be $$\frac{n!}{k!(n-k)!}.$$ The variables which are correlated is known a priori (e.g. $$6$$ out of the $$20$$). I suppose I must use the inclusion-exlusion principle. Any idea?

• Are the correlated pairs disjoint? – Rob Pratt Jul 14 at 4:50
• No they are not. – john Jul 15 at 6:49
• Then yes, inclusion-exclusion would be a useful approach. You can also think of your problem as counting independent sets in a graph where each node is a variable and each edge indicates that the pair of variables is correlated. – Rob Pratt Jul 15 at 11:50

If there are $$n$$ pairs of correlated variables, one can choose a set of $$K$$ uncorrelated variables out of $$N$$ in the following way:
$$\sum_{k=0}^{\text{min}(n,K)}\binom nk \binom {N-2n}{K-k}2^k,$$ where $$\binom nk$$ stays for the number of ways to choose the $$k$$ correlated pairs out of $$n$$, $$\binom {N-2n}{K-k}$$ for the number of ways to choose the rest $$K-k$$ variables out of the uncorrelated ones, and $$2^k$$ - for the number of ways to choose a set of correlated variables out of $$k$$ pairs.
• $k$ is just a summation index which runs from $0$ to min($n,K$), in your example from $0$ to $6$. – user Feb 26 at 14:19