1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Are the correlated pairs disjoint? $\endgroup$ – Rob Pratt Jul 14 at 4:50
  • $\begingroup$ No they are not. $\endgroup$ – john Jul 15 at 6:49
  • $\begingroup$ 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. $\endgroup$ – Rob Pratt Jul 15 at 11:50
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Exactly this question I have addressed in my answer, which gives the number of all possible combinations with no two variables from the same correlated pair included. $\endgroup$ – user Feb 26 at 13:58
  • $\begingroup$ $k$ is just a summation index which runs from $0$ to min($n,K$), in your example from $0$ to $6$. $\endgroup$ – user Feb 26 at 14:19

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.