# Tuples in cartesian product without duplicates

I have $n$ sets $S_1,\ldots,S_n$ and I would like to count the number of tuples $(i_1,\ldots,i_n)\in S_1\times\cdots\times S_n$ such as $i_h\neq i_k$ $\forall h,k\in \{1,\ldots, n\}$. Is there a smarter way to compute this other than computing the cartesian product and excluding all the tuples with duplicates?

• What do we know about $S_i \cap S_j$? Jul 2, 2015 at 12:36
• Nothing, in general... I guess a "general formula", if existent, would involve computing those intersections in some way Jul 2, 2015 at 12:45
• Are you interested in a formula (for theoretical purposes) or an algorithm that you actually want to run? Jul 2, 2015 at 12:56
• I already have implemented the naive algorithm (i.e., compute all the tuples in the cartesian product and exclude the ones with duplicates), I was wondering if there's a smarter way to do it Jul 2, 2015 at 13:00
• You could generate them (recursively) without the duplicates. For example when you put $i$ in position $1$, you have $(i, ?, ?, ..., ?)$. Before adding any other elements, you remove $i$ from $S_{2}...S_{n}$. Then recurse with the shorter tuple to fill out. Jul 2, 2015 at 13:34

Assign each element $x\in\cup S_k$ to a "type" $T_x$ according to which sets $S_k$ it belongs to, i.e. two elements have the same type iff they belong to exactly the same sets $S_k$. Form sets $U_k=\{T_x\mid x\in S_k\}$ of types and consider all tuples $(t_1,\ldots,t_n)\in U_1\times\cdots\times U_n$ (without the restriction $t_h\neq t_k$). Each such tuple represents
$$\prod_m\binom{\left|T_m\right|}{k_m}$$
of the tuples to be counted, where $k_m$ is the number of times $T_m$ occurs in $(t_1,\ldots,t_n)$.