Combinations and Exclusions

[S@NSIS]

Hi all,
Can anyone help me with this little problem!??

I have a group of four objects A,B,C and D. Dependant on various circumstances, certain pairs of these objects cannot be combined with each other. I need to be able to calculate how many groups (combinations) can be made (of varying numbers) when exclusions are applied.

What I mean is, when there is no exclusions and everything can be combined, I can make the following combination groups:

Singles(4): A, B, C, D
Doubles(6): AB, AC, AD, BC, BD, CD
Trebles(4): ABC, ABD, ACD, BCD
4-Folds(1): ABCD

Now, If say A & B could not be combined in any group then I would be left with:

Singles(4): A, B, C, D
Doubles(5): AC, AD, BC, BD, CD
Trebles(1): ACD, BCD
4-Folds(0):

So, what I am looking for is some equation that takes how mny exclusions I have and then calculates how many combinations within each group I would be left with.

Any help will be appreciated
Thanks

S@NSIS

[Illuminator]

N = set size
K = size of subsets
X = size of exclusion group

C(A, B) = A! / B!(A-B)!

Then with exclusions

Number of Elements = C(N, K) - C(N-X, K-X) when K-X >= 0
Note this will only work when you are excluding one group of x items

Example 1:
N = 4 (A, B, C, D)
K = 2 (pairs)
X = 2 (AB exlusion)
Number of Elements = C(4, 2) - C(2, 0) = 6 - 1 = 5

Example 2:
N = 4 (A, B, C, D)
K = 3 (Triples)
X = 2 (AB exlusion)
Number of Elements = C(4, 3) - C(2, 1) = 4 - 2 = 2

Example 3:
N = 4 (A, B, C, D)
K = 4 (Quads)
X = 2 (AB exlusion)
Number of Elements = C(4, 4) - C(2, 2) = 1 - 1 = 0

[S@NSIS]

Thanks Illuminator,

That helps a lot

S@NSIS

[Breax]

you may use probability
every objects will be either on or off
so, probability A & B appears together is (1/2) * (1/2) = 1/4

let's say # can be either on or off
0 is off
letter is on

combination of ABCD exclude AB## is (1-(1/4))*(2^4) = 12
if you want to omit the combination without any object 0000,
then you get 12-1=11


using this method, you may put more exclusion
e.g. ABCDE exclude AB###, ###DE, A#C## and #BCD#
so you will have
combination #####=2^5=32
1) AB###=(1/2)*(1/2)*32=8
2) A#C##=(1/2)*(1/2)*32=8
3) ###DE=(1/2)*(1/2)*32=8
4) #BCD#=(1/2)*(1/2)*(1/2)*32=4
--------
28



5) 1) intersect 2) = ABC## = (1/2)*(1/2)*(1/2)*32=4
6) 1) intersect 3) = AB#DE = (1/2)*(1/2)*(1/2)*(1/2)*32=2
7) 1) intersect 4) = ABCD# = (1/2)*(1/2)*(1/2)*(1/2)*32=2
8) 2) intersect 3) = A#CDE = (1/2)*(1/2)*(1/2)*(1/2)*32=2
2) intersect 4) = ABCD#
9) 3) intersect 4) = #BCDE = (1/2)*(1/2)*(1/2)*(1/2)*32=2
-------
12


10) 5) intersect 6) = ABCDE = 1
11) 5) intersect 7) = ABCD# = 2
5 n 8 , 5 n 9 , 6 n 7 , 6 n 8 , 6 n 9 , 7 n 8 , 7 n 9 , 8 n 9 = 10)
--------
3
12) 10) n 11) = ABCDE = 1

Allowed combination =( 32 - 28 + 12 - 3 + 1) = 14
Omitting 00000 = 14-1 = 13, that are
A, B, C, D, E (5 singles)
AD , AE , BC, BD, BE, CD, CE (7 doubles)
BCE (1 triple)

This is all i can do, but i don't know how to program this. another way i think you may generate all the combination, for each check whether
it violance the exclusion, add one to counter if the combination is allowed.