TY  - JOUR
T1  - Cartesian product of sets without repeated elements
AU  - Torres-Jimenez, Jose
AU  - Lara-Alvarez, Carlos
AU  - Cobos-Lozada, Carlos
AU  - Blanco-Rocha, Roberto
AU  - Cardenas-Castillo, Alfredo
JO  - Information Sciences
VL  - 570
SP  - 517
EP  - 525
PY  - 2021
DA  - 2021/05/13/
SN  - 0020-0255
DO  - https://doi.org/10.1016/j.ins.2021.05.010
UR  - https://www.sciencedirect.com/science/article/pii/S0020025521004564
KW  - Cartesian product of sets
KW  - Integer partitions
KW  - Set partitions
KW  - Bell numbers
KW  - Stirling numbers of the first kind
KW  - Stirling numbers of the second kind
AB  - 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}, Ci is the cardinality of one set, Ci,j (i<j) and Ci,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)=C0; T(2)=C0C1-C0,1; T(3)=C0C1C2-(C0,1C2+C0,2C1+C1,2C0)+2C0,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).
ER  -