Template:Number of relations

Number of n-element binary relations of different types

Elem­ents	Any	Transitive	Reflexive	Symmetric	Preorder	Partial order	Total preorder	Total order	Equivalence relation
0	1	1	1	1	1	1	1	1	1
1	2	2	1	2	1	1	1	1	1
2	16	13	4	8	4	3	3	2	2
3	512	171	64	64	29	19	13	6	5
4	65,536	3,994	4,096	1,024	355	219	75	24	15
n	2n2		2n(n−1)	2n(n+1)/2			∑n k=0 k!S(n, k)	n!	∑n k=0 S(n, k)
OEIS	Template:OEIS link	Template:OEIS link	Template:OEIS link	Template:OEIS link	Template:OEIS link	Template:OEIS link	Template:OEIS link	Template:OEIS link	Template:OEIS link

Note that S(n, k) refers to Stirling numbers of the second kind.

Template documentation

Editors can experiment in this template's sandbox (create | mirror) and testcases (create) pages.
Subpages of this template.