Combinatorics With Relations

The twelvefold way offers a framework for counting functions, under various conditions which can be expressed as n-fold Cartesian Products of the function's domain, function, and codomain attributes. Using this twelvefold way table (which actually has $$16$$ entries) as an example, we could structure the various counting problems as:

$$\{$$domain elements are distinguishable, domain elements are indistinguishable$$\} \times \{$$function is left unique, function is not left unique$$\} \times \{$$function is right total, function is not right total$$\} \times \{$$codomain elements are distinguishable, codomain elements are indistinguishable$$\}$$

The bijective cases are sometimes dropped, yielding the number $$12$$, but we'll keep them.

Is it possible to relax the conditions that make the function a function, namely right uniqueness and left totality, and count general relations? The new structure of counting problems would be:

$$\{$$domain elements are distinguishable, domain elements are indistinguishable$$\} \times \{$$relation is right unique, relation is not right unique$$\} \times \{$$relation is left total, relation is not left total$$\} \times \{$$relation is left unique, relation is not left unique$$\} \times \{$$relation is right total, relation is not right total$$\} \times \{$$codomain elements are distinguishable, codomain elements are indistinguishable$$\}$$

Are there attempts to collect formulas for and study these new cases where the relation may not be a function? If so, what is known about them? If not, is it because it has been shown that such cases have no applications?

• Interesting question. I do not know of any such listings, but that just means it's at least relatively obscure. Maybe it would be best to pick a particular entry, compute some terms, and see if you get OEIS hits. Aug 19 '20 at 10:09

I haven't seen any attempts to do so, probably because there would be 64 entries in the table. Another reason they don't show up much is because we don't usually care much for uniqueness or totality in relation counting, we usually care more about stuff like symmetry, anti-symmetry, and transitivity. But, as I have nothing better to do, I'll give it a go here!

So the first thing to notice that we can switch all the rights with lefts, and the formulas should hold, so we in fact only need 48 cases.

I'll sort these into $$3$$ different $$4\times4$$ tables, one for each distinguishable/indistinguishable combo. This gives even more symmetry in the all distnguishable/indistingushable tables so we actually only require $$36$$ entries. Thus, a catchy title for this might be "The $$36$$-fold Way"

Time to count relations between nonempty sets $$|X|=n$$ and $$|Y|=m$$ (subsets of $$X\times Y$$).

First table, everything is distinguishable, and $$S(n,m)$$ are the Stirling Numbers of the second kind:

$$\begin{array}{c|cccc} \text{left}^{\large{\text{right}}} & \text{none} & \text{unique} & \text{total} & \text{both} \\ \hline \text{none} & 2^{nm} & \sum_{k=0}^m \binom{m}{k}n^k=(n+1)^m& (2^{n}-1)^m& n^m \\ \text{unique} &-& \sum_{k=0}^{\min(n,m)} \binom{m}{k}\frac{n!}{(n-k)!}&\sum_{k=m}^n \binom{n}{k}m!S(k,m) & m!\binom{n}{m} \\ \text{total} &-&-&\sum_{k=1}^{n}(-1)^{n-k}\binom{n}{k}(2^k-1)^m& n!S(m,n)\\ \text{both} &-&-&-& \begin{cases}n! & n=m\\0 & n\neq m \end{cases} \\ \end{array}$$

An alternative for the $$n!S(m,n)$$'s: we could use PIE to count this as $$\sum_{k=1}^n (-1)^{n-k}\binom{n}{k}k^m$$, but this would require a double summation, which I'd rather not have in my tables if I can help it.

One application of this could be counting the number of ways $$n$$ people can participate in $$m$$ clubs. Then right totality for example would mean each club has at least one member.

Warning: Past this point, stuff gets weird, as clubs or people become indistinguishable. It also gets hard to count, as there are many different symmetries which can make things indistingushable. Thus, I have not filled out most of these others currently, but I'll try to update these over time, and would appreciate help in the comments!:

Left is distinguishable, right is not: $$\begin{array}{c|cccc} \text{left}^{\large{\text{right}}}& \text{none} & \text{unique} & \text{total} & \text{both} \\ \hline \text{none}&&\sum_{k=0}^m \binom{k+n-1}{k}&&\binom{m+n-1}{m}\\ \text{unique}&&\sum_{k=0}^m\binom{n}{k}&&\binom{n}{m}\\ \text{total}&&\sum_{k=n}^m\binom{k-1}{k-n}&&\binom{m-1}{m-n} \\ \text{both}& \sum_{k=0}^{m}S(n,k)& \begin{cases} 1 & n\leq m\\ 0 & n < m \end{cases}& S(n,m)& \begin{cases} 1 & n=m \\ 0 & n\neq m \end{cases} \end{array}$$

And finally, everything is indistinguishable: $$\begin{array}{c|cccc} \text{left}^{\large{\text{right}}}& \text{none} & \text{unique} & \text{total} & \text{both} \\ \hline \text{none}&&&&\sum_{k=1}^n \pi(m,k)\\ \text{unique}&-&\min(n,m)&\pi(n-m,m)&\begin{cases} 1 & n=m \\ 0 & n\neq m \end{cases}\\ \text{total}&-&-&&\pi(m,n)\\ \text{both}&-&-&-&\begin{cases} 1 & n=m \\ 0 & n\neq m \end{cases} \end{array}$$ Where $$\pi(m,n)$$ is the number of ways to partition $$m$$ into at $$n$$ (possibly empty!) parts.