A394620 Number of relations on an n-set that are reflexive but neither symmetric nor transitive.

0, 0, 0, 32, 3692, 1040662, 1073499732, 4398034879588, 72057593126717266, 4722366482737665468684, 1237940039285336113473278324, 1298074214633706869286981025283434, 5444517870735015415339687387042391616408, 91343852333181432387729999605431391414560798788

Offset

0,4

Links

Table of n, a(n) for n=0..13.

Des MacHale and Peter MacHale, Relations on Sets, The Mathematical Gazette, Vol. 97, No. 539 (July 2013), pp. 224-233 (10 pages).

Formula

a(n) = 2^(n*(n-1)) - 2^(n*(n-1)/2) - A000798(n) + A000110(n).

Example

For n = 3: the set [3] = {1, 2, 3} has 3^2 - 3 = 6 off-diagonal pairs.
Total reflexive relations: 2^6 = 64.
Reflexive and symmetric: 2^3 = 8.
Reflexive and transitive (preorders): A000798(3) = 29.
Equivalence relations: B3 = 5.
By inclusion-exclusion: a(3) = 64 - 8 - 29 + 5 = 32.

Crossrefs

Sequence in context: A222053 A264126 A304401 * A328275 A291829 A248075

Adjacent sequences: A394617 A394618 A394619 * A394621 A394622 A394623

Keyword

nonn,easy

Author

Firdous Ahmad Mala, Mar 26 2026

Status

approved