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.

Don't expect an efficient algorithm. This is the problem of counting the number of independent sets in an undirected graph. This problem is #P-complete [1,2], so there is unlikely to be any effective algorithm that works for arbitrary graphs.

See https://cstheory.stackexchange.com/q/10700/5038 for techniques you could use.

[1] The complexity of counting cuts and of computing the probability that a graph is connected, J. Scott Provan and Michael O. Ball, SIAM J. Computing, 12:4.

[2] The complexity of counting in sparse, regular, and planar graphs, Salil P. Vadhan, SIAM J. Computing, 31:2(398--427).

StackExchange Computer Science Q#140820, answer score: 7