# counting all 1 to n-ary relations on a set size m

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.

• 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$? Sep 16 '20 at 3:01

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}$$