# Number of combinations without given pairs

Given a set of elements {e1, e2, ... en}, a set of pairs of these elements (each element may be present in several pairs) and a number k.

I need to count how many combinations of size k exist which not include any pair?

For example: if there only one pair {e1, e2} result in number of all combinations without elements e1 and e2. It may be counted in constant time: $$C^k_n - C^{k-2}_{n-2}$$

This task can be solved with the naive algorithm on python:

def combinations_without_pairs(elements, pairs, k):
def iterable_len(iterable):
return sum(1 for _ in iterable)

def not_include_pairs(combination):
for pair in pairs:
if pair[0] in combination and pair[1] in combination:
return False
return True

return iterable_len(filter(not_include_pairs, itertools.combinations(elements, k)))


But this algorithm is ineffective: it requires iterating over each element combination and each pair.

Is there any way to solve this problem with better complexity? At least reduce the impact of a big count of elements and pairs?

I want to find an algorithm with the lowest time complexity.