1
$\begingroup$

I am trying to count all possible relations on a set $S$ whose cardinality is $m$. The relations can vary from $1$ to $n$-ary relations where $n > m$. For example if $S = \{a, b, c\}$ and if $n = 4$, then both $(a)$ and $(a,a,a,a)$ are to be counted as well as $(a,b,c)$ and $(c, b, a)$ etc.

I know the number of ordered pairs is the cardinality of the cartesian product: $$ |S \times S| = m^2$$

The number of combinations of binary relations on a set is the size of the powerset of the cartesian product: $$|\mathcal P(S \times S)| = 2^{|S|^2} = 2^{m^2}$$

And I've read on Quora that the number of $n$-ary relations are the number of subsets of the $n$-fold cartesian product:

$$|\mathcal P(\underbrace{S\times S \times\cdots \times S}_{n\text{ times}} )| = 2^{|S|^n} = 2^{m^n}$$

What I am asking is a formula to count the number $1$-ary, $2$-ary... etc up to $n$-ary relations definable on a set size $m$.

My intuition is that the solution is something like the powerset of the union of the $n$-fold cartesian products from $1$ to $n$:

$$|\mathcal P(\{S\} \cup \{S \times S\} \cup \{S \times S \times S\} \cup \cdots \cup \{\underbrace{S\times S \times\cdots \times S}_{n\text{ times}}\})|$$.

If this is right can I count size of the set of all relations $R$ as something like: $$ \left| \bigcup_{?}^{?}\prod_{i=1}^n S_i \right| \stackrel{?}=\sum_{i=1}^n m^i$$

and the total number of subsets of R as $2^R$?

Is this right? I'm unsure how to convert this into a formula in terms $m$ and $n$. I am also unsure if the method I am using is the correct one. Or if this method misses any relations or double counts them? I apologize if I am using notation incorrectly. I am teaching myself set theory and started to wonder what the answer to this question is.

$\endgroup$
  • $\begingroup$ Can $(a)$ and $(a,a)$ be present in the same relation, for example? Or is each particular relation solely $k$-ary for some $1\le k\le n$? $\endgroup$ – Greg Martin Sep 16 at 3:01
0
$\begingroup$

As Greg Martin suggested in his comment, if $k \neq k'$, the sets of $k$-ary and $k'$-ary relations are disjoint. It follows that the number of $1$ to $n$-ary relations on a set of size $m$ is $$ S(m,n) = \sum_{i=1}^n 2^{m^i} $$ There is no close form for this sum. However, it is easy to write the result in binary (which would make any computer happy...). For instance, $S(2,4) = 2^2 + 2^4 + 2^8 + 2^{16}$ can be writen in binary as \begin{array}{ccccccccccccccccccccccc} \color{red}{\scriptsize{16}}& \scriptsize{15}& \scriptsize{14}& \scriptsize{13}& \scriptsize{12}& \scriptsize{11}& \scriptsize{10}& \scriptsize{9}& \color{red}{\scriptsize{8}}& \scriptsize{7}& \scriptsize{6}& \scriptsize{5}& \color{red}{\scriptsize{4}}& \scriptsize{3}& \color{red}{\scriptsize{2}}& \scriptsize{1}& \scriptsize{0}\\ 1&0&0&0&0&0&0&0&1&0&0&0&1&0&1&0&0 \end{array}

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.