Count all binary relations

Question

A binary relation on a set \$X\$ is simply a subset \$S \subseteq X \times X\$; in other words, a relation is a collection of pairs \$(x,y)\$ such that both \$x\$ and \$y\$ are in \$X\$. The number of different relations grows quickly with the size of the set: if \$X\$ contains \$n\$ elements, there are \$2^{n^2}\$ binary relations on \$X\$.

This challenge will have you computing the number of binary relations subject to certain constraints, listed here:

• A binary relation is called "reflexive" if \$(x,x) \in S\$ for all \$x \in X\$.

• A binary relation is called "irreflexive" if \$(x,x) \not\in S\$ for all \$x \in X\$.

• A binary relation is called "symmetric" if whenever \$(x,y) \in S\$, then \$(y,x) \in S\$.

• A binary relation is called "asymmetric" if whenever \$(x,y) \in S\$, then \$(y,x) \not\in S\$.

• A binary relation is called "transitive" if whenever \$(x,y) \in S\$ and \$(y,z) \in S\$ then \$(x,z) \in S\$.

• A binary relation is called "antitransitive" if whenever \$(x,y) \in S\$ and \$(y,z) \in S\$ then \$(x,z) \not\in S\$.

Challenge

The goal of this code-golf challenge is to write a function that takes in a nonnegative integer \$n\$, and some subset of the six conditions above in any reasonable format*, and returns the number of binary relations on the set \$\{1,2,\dots,n\}\$ satisfying all of the conditions in the aforementioned subset.

Brute-force strategies are okay, but your code should be able to handle all \$n \leq 4\$ on TIO.

Test Data

n | conditions                         | number of binary relations
--+------------------------------------+-------------------------
0 | {reflexive, antitransitive}        | 1
3 | {reflexive, antitransitive}        | 0
3 | {}                                 | 512
3 | {antitransitive}                   | 39 
4 | {antitransitive}                   | 921
4 | {reflexive, irreflexive}           | 0
4 | {symmetric, asymmetric}            | 1
4 | {transitive, antitransitive}       | 87
4 | {reflexive, symmetric, transitive} | 15
4 | {symmetric, transitive}            | 52
4 | {asymmetric, antitransitive}       | 317

Example

For \$n = 3\$, there are \$39\$ antitransitive relations, as shown by the illustration below. (Strictly speaking, the illustration shows unlabeled relations.)

0. There is \$1\$ empty relation.
1. There are \$6\$ relations consisting of just one pair.
2. There are \$3 + 3 + 6 + 3\$ relations consisting of two pairs.
3. There are \$6 + 6 + 2\$ relations consisting of three pairs.
4. There are \$3\$ relations consisting of four pairs.

---

* For example, you could take the conditions as a list like [False, False, True, False, False, True], with each position referring to the particular condition. As another example, you could take a set of strings like {"transitive", "asymmetric"}.

Answer 1

APL (Dyalog Extended), ⁹⁹ 93 bytes

r←0∊0 0⍉⊢
R←r~
s←⊢≢⍉
S←1∊⊢∧⍉
t←0∊⊢≥∨.∧⍨
T←1∊⊢∧∨.∧⍨
{×⍵:+/∧⌿~(⍺,'0'){(⍎⍺)⊣⍵}\⍵-⍛↑∘⊤¨,⍳⍵⍴2*⍵⋄1}

Try it online!

-5 bytes thanks to @ovs for spotting R←r~, and -1 by taking the boolean negation of the intermediate results.

Takes the condition as a string, using the abbreviation as follows:

r: reflexive
R: irreflexive
s: symmetric
S: asymmetric
t: transitive
T: antitransitive

For example, reflexive + symmetric + transitive is given as 'rst' and "no condition" is given as ''.

How it works (before golfing)

⍝ Each of rRsStT takes an adjacency matrix and determines if the condition is met

⍝ reflexive: the diagonal is all ones
r←∧/0 0⍉⊢
⍝ irreflexive: the diagonal is all zeros
R←∧/0 0⍉~
⍝ symmetric: transpose is equal to self
s←⊢≡⍉
⍝ antisymmetric: each position in self and transpose cannot be both ones
S←~1∊⊢∧⍉
⍝ transitive: self includes the transitive square of self
t←~0∊⊢≥∨.∧⍨
⍝ antitransitive: each position in self and transitive square cannot be both ones
T←~1∊⊢∧∨.∧⍨

⍝ main function
{×⍵:+/∧⌿(⍺,'≡'){(⍎⍺)⍵}\⍵-⍛↑∘⊤¨,⍳⍵⍴2*⍵⋄1}  ⍝ ⍵: n, ⍺: conditions
{×⍵: ... ⋄1}  ⍝ Take 0 as a special case, always returning 1
,⍳⍵⍴2*⍵       ⍝ Generate all length-n vectors of 0..2^n-1
⍵-⍛↑∘⊤¨       ⍝ Convert them to n×n binary matrices
(⍺,'≡')       ⍝ Add a default function that always returns 1 to the list of conditions
{...}\        ⍝ Take outer product of conditions and matrices...
 (⍎⍺)⍵        ⍝ Eval the condition function and apply it to the matrix
+/∧⌿          ⍝ Count the matrices which satisfy all the conditions

Answer 2

JavaScript (Node.js), 182 bytes

A slower but significantly shorter version suggested by @tsh.

Expects (n)(m), where n is a BigInt and m is a list of constraints among:

IRREFLEXIVE = 0, REFLEXIVE = 1, ANTISYMMETRIC = 2,
SYMMETRIC = 3, ANTITRANSITIVE = 4, TRANSITIVE = 5

n=>m=>eval("g=(c,x=n)=>x?c(--x)&g(c,x):1;h=(x,y)=>!(k>>x+n*y&1n);for(t=0,k=1n<<n*n;k--;)t+=m.every(q=>g(x=>g(y=>g(z=>[h(x,x)^q,h(x,y)|h(y,x)^q%2,h(x,y)|h(y,z)|h(x,z)^q%2][q>>1]))))")

Try it online! (part 1)
Try it online! (part 2)

---

JavaScript (Node.js), 215 bytes

Expects (n)(m), where n is a BigInt and m is a bit-mask describing which constraints are enabled, using a combination of:

IRREFLEXIVE    = 1
REFLEXIVE      = 2
ANTISYMMETRIC  = 4
SYMMETRIC      = 8
ANTITRANSITIVE = 16
TRANSITIVE     = 32

n=>m=>{g=(c,x=n)=>x?c(--x)&g(c,x):1;h=(x,y)=>!(k>>x+n*y&1n);for(t=0,k=1n<<n*n;k--;)t+=![x=>h(x,x)^q,0,x=>g(y=>h(x,y)|h(y,x)^q),0,x=>g(y=>g(z=>h(x,y)|h(y,z)|h(x,z)^q)),0].some((c,j)=>m>>j&!g((q=j&1)?C:C=c));return t}

Try it online!

Notes:

• To get a much faster version, replace the first bitwise & with &&.
• Using BigInts is slower and slightly longer, but allows this code to work for any n in theory.

Formatted and commented

n => m => {
  // helper function to test whether c(x) is true for all x in [0 .. n - 1]
  g = (c, x = n) => x ? c(--x) & g(c, x) : 1;

  // helper function to test if (x, y) is *not* in S
  h = (x, y) => !(k >> x + n * y & 1n);

  // we use k = 2 ** n² - 1 to k = 0 to describe all possible binary relations
  // (k is essentially a flatten binary matrix of size n x n)
  for(t = 0, k = 1n << n * n; k--;)
    // increment t if ...
    t +=
      // ... the following tests are all falsy
      ![
        // irreflexive (q = 0) / reflexive (q = 1)
        x => h(x, x) ^ q, 0,

        // antisymmetric (q = 0) / symmetric (q = 1)
        x => g(y => h(x, y) | h(y, x) ^ q), 0,

        // antitransitive (q = 0) / transitive (q = 1)
        x => g(y => g(z => h(x, y) | h(y, z) | h(x, z) ^ q)), 0
      ]
      .some((c, j) =>
        // return true if the constraint is set ...
        m >> j &
        // ... and the test fails
        !g((q = j & 1) ? C : C = c)
      );
  return t
}

Answer 3

Python 3, 319 bytes

Expects to be called as f(n, m), where m is a bitmask of which conditions are required, in the same order as the question.

r=lambda x:x and r(x[1:])+[x[:1]+a for a in r(x[1:])]or[[]]
f=lambda n,c:(lambda z:n==0 or sum(1for a in map(set,r([(x,y)for x in z for y in z]))if not(lambda g,h,i:(g<=a)+(a-g==a)*2+(h==a)*4+(a-h==a)*8+(i|a==a)*16+(a-i==a)*32)(set(zip(z,z)),{(q,b)for(b,q)in a},{(d,c)for(d,b)in a for(l,c)in a if l==b})&c^c))(range(n))

Try it online!

Answer 4

Python 3.8 (pre-release), 188 bytes

lambda n,Q:sum(all([m[x*n+x]^q,(b:=m[x*n+y])+m[y*n+x]^q-1,b*m[y*n+z]<=m[x*n+z]^q%2][q//2]for q in Q for x,y,z in p(*3*[range(n)]))for m in p(*n*n*[[0,1]]))
from itertools import*;p=product

Try it online!

Function receives two arguments. The first one is the size of set \$X\$. The second one is a list describe properties all relations should fit. while use 0~5 for reflexive, irreflexive, symmetric, antisymmetric, transitive, antitransitive. For example, f(4, [0, 2, 4]) find the number of relations on set with 4 elements which is reflexive, symmetric, and transitive.

for matrix in itertools.product([0,1], repeat=n*n) # all possible relations
for arguments in itertools.product(range(n), repeat=3) # all x, y, z combinations
for q in Q # all properties need to follow

---

Python 3.8 (pre-release), 205 bytes

lambda n,Q:sum(all([x:=k%n,m[x*n+x]^q,y:=k//n%n,(b:=m[x*n+y])+m[y*n+x]^q-1,z:=k//n//n,b*m[y*n+z]<=m[x*n+z]^q%2][q|1]for q in Q for k in R(n**3))for m in[[i>>j&1for j in R(n*n)]for i in R(2**n**2)])
R=range

Try it online!

Here is another version without import itertools.

Save 2 bytes, thanks to caird coinheringaahing

Answer 5

Charcoal, 121 bytes

ＩＬΦＥＸ²×θθ⎇θ⪪﹪÷ιＸ²…⁰×θθ²θυ∧∨§η⁰⬤ι§λμ∧∨§η¹¬⊙ι§λμ∧∨§η²⬤ι⬤λ⁼ν§§ιξμ∧∨§η³¬⊙ι⊙λ∧ν§§ιξμ∧∨§η⁴⬤ι⬤⌕Ａλ¹⬤⌕Ａ§ιν¹§λπ∨§η⁵¬⊙ι⊙λ∧ν⊙§ιξ∧π§λρ

Try it online! Link is to verbose version of code, which contains 17 consecutive )s, which might be a record for me in Charcoal. Takes input as n and an array of six integers where 0 means that the constraint is to be enforced. This is technically a 1-liner, but at 121 bytes it's too wide for me to format the explanation that way, so I'll pretend it isn't. Explanation:

ＩＬΦ

Print the length of matching values...

ＥＸ²×θθ⎇θ⪪﹪÷ιＸ²…⁰×θθ²θυ

... generated by iterating over all \$ 2^{n^2} \$ relations and turning them into an \$ n \$ by \$ n \$ binary matrix (except when \$ n \$ is 0, in which case just iterate the predefined empty array), where...

∧∨§η⁰⬤ι§λμ

... if the first constraint is to be enforced then check that the main diagonal only contains 1s; and...

∧∨§η¹¬⊙ι§λμ

... if the second constraint is to be enforced then check that the main diagonal does not contain a 1; and...

∧∨§η²⬤ι⬤λ⁼ν§§ιξμ

... if the third constraint is to be enforced then check that the matrix equals its transpose; and...

∧∨§η³¬⊙ι⊙λ∧ν§§ιξμ

... if the fourth constraint is to be enforced then check that the matrix does not contain a 1 where its transpose does; and...

∧∨§η⁴⬤ι⬤⌕Ａλ¹⬤⌕Ａ§ιν¹§λπ

... if the fifth constraint is to be enforced then check that wherever the matrix contains a 1 and the row of that 1s column contains a 1 then the original row also contains a 1 in the second 1's column, and...

∨§η⁵¬⊙ι⊙λ∧ν⊙§ιξ∧π§λρ

... if the sixth constraint is to be enforced then check that that the matrix does not contain three 1s where two are in the same row, two are in the same column and the other row and column index are the same.