Cartesian Product of Sets Without Repeated Elements

Abstract In many applications, like database management systems, is very useful to have an expression to compute the cardinality of cartesian product of k sets without repeated elements; we designate this problem as T ( k ) . The value of | T ( k ) | is upper-bounded by the multiplication of cardinalities of the sets. As long as we have searched, it has not been reported a general expression to compute T ( k ) using cardinalities of the intersections of sets, this is the main topic of this paper. Given three sets with indices { 0 , 1 , 2 } , C i is the cardinality of one set, C i , j ( i j ) and C i , j , l ( i j l ) are respectively the cardinalities of the intersections of 2 and 3 sets, then the searched formulas for T ( k ) are: T ( 1 ) = C 0 ; T ( 2 ) = C 0 C 1 - C 0 , 1 ; T ( 3 ) = C 0 C 1 C 2 - ( C 0 , 1 C 2 + C 0 , 2 C 1 + C 1 , 2 C 0 ) + 2 C 0 , 1 , 2 . In this paper, we prove formulas for computing T ( k ) and its specialization when a set is contained in the next sets. For this purpose, we will use concepts like partitions of the integer k in v parts, Bell numbers, Stirling numbers of the first kind and Stirling numbers of the second kind. Additionally, we present a complexity analysis for the computation of T ( k ) .