find the number of all possible combinations with conflicts -

i trying solve optimization problem, first have find number of possible combinations of n elements considering conflicts. possible example be:

elements: {1,2,3,4} conflicts: {1,2},{3,4}

the term "conflict" means numbers belong same conflict set must not allocated same combination. conflict sets not disjoint , elements in each conflict set two.

until found how possible combinations can calculated, 2^n.

thank you.

the conflict sets can modeled edges in graph. asking number of independent vertex sets in graph

an independent vertex set of graph g subset of vertices such no 2 vertices in subset represent edge of g - http://mathworld.wolfram.com/independentvertexset.html

the above link refers called independence polynomial can used count such things -- though useful if conflict graph has nice structure. general problem of determining number of independent sets known #p-complete (see https://en.wikipedia.org/wiki/sharp-p-complete definition of complexity class) there little chance question has simple answer. markov-chain techniques have been applied approximate number in cases. see http://www.researchgate.net/publication/221590282_approximately_counting_up_to_four_(extended_abstract)