# Counting combinations of tuples with restrictions

• Dec 14th 2009, 04:59 PM
snapcall
Counting combinations of tuples with restrictions
Given 3 identical sets of 2-tuples containing integers with repetition, i.e. (x,x) or (x,y), is it possible to count the number of (tuple1, tuple2, tuple3) combinations (where tuple1, tuple2, and tuple3 are selected with repetition) that contain 3 or more occurrences of an integer, e.g. ((x,x),(x,y),(x,y)) would be one, without enumerating all possible (tuple1, tuple2, tuple3) combinations?

For example, suppose we are given 3 identical sets of tuples:
S1: {(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),( 3,4),(4,4)}
S2: {(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),( 3,4),(4,4)}
S3: {(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),( 3,4),(4,4)}

I have created a program to enumerate all possible (t1, t2, t3) combinations, where t1 is in S1, t2 is in S2, and t3 is in S3, such that t1 = t2 = t3 is valid (combinations with repetition), and it reported that there are 164 combinations containing 3 or more occurrences of an integer.

I believe it might help to think of all possible (tuple1, tuple2, tuple2) isomorphisms that contain more than 3 occurrences of an integer (please correct me if I made a mistake):
- ((x,x),(x,x),(x,x))
- ((x,x),(x,x),(x,y))
- ((x,x),(x,x),(y,y))
- ((x,x),(x,x),(y,z))
- ((x,x),(x,y),(y,z))
- ((x,x),(x,y),(z,z))
- ((x,x),(x,y),(z,t))
- ((x,x),(x,y),(y,y))
- ((x,y),(x,y),(x,y))
- ((x,y),(x,y),(x,z))
- ((x,y),(x,z),(x,t))

However, I'm not really sure where to go from here (Worried).