Relations · step 9 of 13

Counting relations with a given property

A relation on an n-element set is a subset of the n² ordered pairs, so there are 2^(n²) of them. Imposing a property fixes or links some of those independent choices: reflexivity forces the n diagonal entries to 1, symmetry ties (a,b) to (b,a). Every count in this area comes from deciding which choices remain free.

Practise counting relations with a given property free → All Relations subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Split the pairs into diagonal and off-diagonalThere are n diagonal pairs and n² − n off-diagonal ones, which form (n² − n)/2 unordered couples.
Fix what the property forcesReflexive: diagonal all 1, leaving 2^(n²−n). Irreflexive: diagonal all 0, same count.
Count the free choices for coupled pairsSymmetric: each of the (n² − n)/2 couples is in or out together, giving 2^n · 2^((n²−n)/2). Antisymmetric: each couple has 3 options — neither, one way, or the other — giving 2^n · 3^((n²−n)/2).
Combine properties by intersecting constraintsReflexive AND symmetric: diagonal forced, couples free — 2^((n²−n)/2).

Worked example

How many relations on a 3-element set are (a) reflexive, (b) symmetric, (c) both?

n = 3 gives 9 pairs: 3 diagonal, 6 off-diagonal forming 3 couples.
(a) Reflexive: 3 diagonal entries forced to 1, the other 6 free → 2⁶ = 64.
(b) Symmetric: 3 diagonal free (2³) and 3 couples free (2³) → 8 · 8 = 64.
(c) Both: diagonal forced, 3 couples free → 2³ = 8.

Answer. 64 reflexive, 64 symmetric, and 8 that are both reflexive and symmetric.

Where marks get dropped

These are the specific errors that cost credit on counting relations with a given property questions — QED's rubric penalises each of them separately.

Counting off-diagonal pairs instead of couples for symmetry. There are 6 ordered off-diagonal pairs but only 3 independent choices.
Using 2 options per couple for antisymmetry. There are 3: neither, (a,b) only, or (b,a) only — both is forbidden.
Trying to count transitive relations with a formula. No closed form exists; for n = 3 there are 171, found by enumeration.

Practise this until it is automatic

Unlimited fresh questions

QED generates new counting relations with a given property problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Relations mastery is tracked so you know when this is exam-ready.

Counting relations with a given property — frequently asked questions

Why 3^((n²−n)/2) for antisymmetric relations?

Each unordered couple {a,b} independently takes one of three states, since having both directions is banned. Multiply by 2^n for the unconstrained diagonal.

How many equivalence relations are there on an n-set?

The Bell number Bₙ, because equivalence relations correspond exactly to partitions. For n = 3 that is 5, far fewer than the 64 symmetric relations.

Is there a formula for transitive relations?

No known closed form. The counts (1, 2, 13, 171, 3994, …) are computed by search and catalogued in the OEIS.

The rest of Relations

Properties of relations, composition, and representations. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make counting relations with a given property exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →