Skip to content
CampusPrep
CS-302 · Discrete Structure/Quick Revision Short Notes

Discrete Structure (CS-302) - Unit 5 Short Notes

How unit 5 is examined

Posets, Hasse diagrams and lattices (with their proofs) plus counting and recurrences; the marks sit in Hasse diagrams, lattice proofs, inclusion-exclusion, generating functions and recurrence solving.

Introduction, ordered set

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>A poset is a set $A$ with a reflexive, antisymmetric and transitive relation $\le$; it is a chain if every two elements are comparable.</mark>

Key points.

  1. Antisymmetric means $a\le b$ and $b\le a$ give $a=b$; elements are comparable if $a\le b$ or $b\le a$, and 2, 3 are not under divisibility.
  2. A maximal (minimal) element has nothing strictly above (below) it; a greatest (least) element is above (below) every element.
  3. The least upper bound (lub) is the smallest upper bound of a subset, and the greatest lower bound (glb) is defined dually.

Asked: [7 marks] (Jun 2020) Write short notes: i) Posets ii) Lattices iii) Permutation and combination

Hasse diagram of partially ordered set

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>A Hasse diagram is the diagram of a finite poset in which each element is a dot, only covering pairs are joined by upward lines, and loops and transitive edges are omitted.</mark> $b$ covers $a$ if $a<b$ and no $c$ has $a<c<b$.

Key points.

  1. Direction is shown by height alone, so lines carry no arrows and the smaller element is always lower.
  2. Reflexive loops and transitive edges are never drawn: if $a<b<c$ there is no direct line from $a$ to $c$.
  3. Minimal elements have no line going down, maximal elements no line going up.
  4. $D_n$ has 1 at the bottom and $n$ at the top; $P(A)$ has $\emptyset$ at the bottom, $A$ at the top, $2^{|A|}$ elements, and $\binom nk$ dots on level $k$.

Example. $A=\{2,3,6,12,24,36\}$ under divisibility. Cover pairs: 2-6, 3-6, 6-12, 6-36, 12-24; pairs like $2|12$ are transitive and dropped. Minimal: 2, 3. Maximal: 24, 36.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-01" viewBox="0 0 338 338" width="338" height="338" role="img" aria-label="Hasse diagram of {2,3,6,12,24,36} under divisibility"><style>#dsfig-u5-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-01 .t{fill:#16181D;font-weight:500}#dsfig-u5-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-01 .dot{fill:#16181D}#dsfig-u5-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-01 .ah{fill:#454C5A}#dsfig-u5-01 .ah.hi{fill:#2340B8}#dsfig-u5-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-01 .e{stroke:#B1B7C3}html.dark #dsfig-u5-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-01 .t{fill:#E6E8ED}html.dark #dsfig-u5-01 .t.inv{fill:#0F1115}html.dark #dsfig-u5-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-01 .dot{fill:#E6E8ED}html.dark #dsfig-u5-01 .ann{fill:#8FA3FF}html.dark #dsfig-u5-01 .lbl{fill:#858D9C}html.dark #dsfig-u5-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-01 .ah{fill:#B1B7C3}html.dark #dsfig-u5-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah13" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh13" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M96.4,284.6 L155.6,225.4"/><path class="e" d="M241.6,284.6 L182.4,225.4"/><path class="e" d="M153.2,201.5 L55.8,136.5"/><path class="e" d="M184.8,201.5 L282.2,136.5"/><path class="e" d="M40,107 L40,59"/><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">24</text><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">12</text><circle class="n" cx="298" cy="126" r="18"/><text class="t" x="298" y="126" dy=".35em" text-anchor="middle">36</text><circle class="n" cx="169" cy="212" r="18"/><text class="t" x="169" y="212" dy=".35em" text-anchor="middle">6</text><circle class="n" cx="83" cy="298" r="18"/><text class="t" x="83" y="298" dy=".35em" text-anchor="middle">2</text><circle class="n" cx="255" cy="298" r="18"/><text class="t" x="255" y="298" dy=".35em" text-anchor="middle">3</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Hasse diagram of {2,3,6,12,24,36} under divisibility</figcaption></figure>

Example. $D_{36}=\{1,2,3,4,6,9,12,18,36\}$. $\{1,2,3,6,9,18\}$ is the same drawing without 4, 12, 36. $D_{45}=\{1,3,5,9,15,45\}$ has edges 1-3, 1-5, 3-9, 3-15, 5-15, 9-45, 15-45.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-02" viewBox="0 0 510 424" width="510" height="424" role="img" aria-label="Hasse diagram of D36"><style>#dsfig-u5-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-02 .t{fill:#16181D;font-weight:500}#dsfig-u5-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-02 .dot{fill:#16181D}#dsfig-u5-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-02 .ah{fill:#454C5A}#dsfig-u5-02 .ah.hi{fill:#2340B8}#dsfig-u5-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-02 .e{stroke:#B1B7C3}html.dark #dsfig-u5-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-02 .t{fill:#E6E8ED}html.dark #dsfig-u5-02 .t.inv{fill:#0F1115}html.dark #dsfig-u5-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-02 .dot{fill:#E6E8ED}html.dark #dsfig-u5-02 .ann{fill:#8FA3FF}html.dark #dsfig-u5-02 .lbl{fill:#858D9C}html.dark #dsfig-u5-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-02 .ah{fill:#B1B7C3}html.dark #dsfig-u5-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah14" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh14" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M239.2,373.5 L141.8,308.5"/><path class="e" d="M270.8,373.5 L368.2,308.5"/><path class="e" d="M112.6,284.6 L53.4,225.4"/><path class="e" d="M141.8,287.5 L239.2,222.5"/><path class="e" d="M368.2,287.5 L270.8,222.5"/><path class="e" d="M397.4,284.6 L456.6,225.4"/><path class="e" d="M53.4,198.6 L112.6,139.4"/><path class="e" d="M239.2,201.5 L141.8,136.5"/><path class="e" d="M270.8,201.5 L368.2,136.5"/><path class="e" d="M456.6,198.6 L397.4,139.4"/><path class="e" d="M141.8,115.5 L239.2,50.5"/><path class="e" d="M368.2,115.5 L270.8,50.5"/><circle class="n" cx="255" cy="40" r="18"/><text class="t" x="255" y="40" dy=".35em" text-anchor="middle">36</text><circle class="n" cx="126" cy="126" r="18"/><text class="t" x="126" y="126" dy=".35em" text-anchor="middle">12</text><circle class="n" cx="384" cy="126" r="18"/><text class="t" x="384" y="126" dy=".35em" text-anchor="middle">18</text><circle class="n" cx="40" cy="212" r="18"/><text class="t" x="40" y="212" dy=".35em" text-anchor="middle">4</text><circle class="n" cx="255" cy="212" r="18"/><text class="t" x="255" y="212" dy=".35em" text-anchor="middle">6</text><circle class="n" cx="470" cy="212" r="18"/><text class="t" x="470" y="212" dy=".35em" text-anchor="middle">9</text><circle class="n" cx="126" cy="298" r="18"/><text class="t" x="126" y="298" dy=".35em" text-anchor="middle">2</text><circle class="n" cx="384" cy="298" r="18"/><text class="t" x="384" y="298" dy=".35em" text-anchor="middle">3</text><circle class="n" cx="255" cy="384" r="18"/><text class="t" x="255" y="384" dy=".35em" text-anchor="middle">1</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Hasse diagram of D36</figcaption></figure>

Example. $P(\{a,b,c,d\})$: 16 subsets, levels of $1,4,6,4,1$ nodes, $x$ joined to $y$ when $y$ is $x$ plus one element. For $\{a\}$ it is a 2-chain, $\{a,b\}$ a diamond, $\{a,b,c\}$ a cube (8 nodes).

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-03" viewBox="0 0 603 424" width="603" height="424" role="img" aria-label="Hasse diagram of (P(A), subset) for A={a,b,c,d}; e is the empty set"><style>#dsfig-u5-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-03 .t{fill:#16181D;font-weight:500}#dsfig-u5-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-03 .dot{fill:#16181D}#dsfig-u5-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-03 .ah{fill:#454C5A}#dsfig-u5-03 .ah.hi{fill:#2340B8}#dsfig-u5-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-03 .e{stroke:#B1B7C3}html.dark #dsfig-u5-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-03 .t{fill:#E6E8ED}html.dark #dsfig-u5-03 .t.inv{fill:#0F1115}html.dark #dsfig-u5-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-03 .dot{fill:#E6E8ED}html.dark #dsfig-u5-03 .ann{fill:#8FA3FF}html.dark #dsfig-u5-03 .lbl{fill:#858D9C}html.dark #dsfig-u5-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-03 .ah{fill:#B1B7C3}html.dark #dsfig-u5-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah15" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh15" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M274.2,50.6 L121.9,118.3"/><path class="e" d="M282.4,60.8 L244.9,110.8"/><path class="e" d="M313.6,60.8 L351.1,110.8"/><path class="e" d="M321.8,50.6 L474.1,118.3"/><path class="e" d="M93.1,141.2 L51.4,196.8"/><path class="e" d="M112.3,143.3 L135.4,194.7"/><path class="e" d="M122.4,132.3 L331.7,205.7"/><path class="e" d="M216.1,133.7 L57.4,204.3"/><path class="e" d="M236.3,144.8 L243.6,193.2"/><path class="e" d="M251.2,132.9 L435.1,205.1"/><path class="e" d="M344.8,132.9 L160.9,205.1"/><path class="e" d="M347.2,137.3 L261.7,200.7"/><path class="e" d="M379.9,133.7 L538.6,204.3"/><path class="e" d="M475.3,135.8 L365.8,202.2"/><path class="e" d="M483.7,143.3 L460.6,194.7"/><path class="e" d="M502.9,141.2 L544.6,196.8"/><path class="e" d="M53.4,225.4 L112.6,284.6"/><path class="e" d="M57.6,219.1 L237.4,290.9"/><path class="e" d="M139.5,230.6 L129.7,279.4"/><path class="e" d="M160.6,219.6 L323.6,290.4"/><path class="e" d="M230.9,223 L141.5,287"/><path class="e" d="M264.1,218.8 L452.3,291.2"/><path class="e" d="M335.5,224.8 L269.1,285.2"/><path class="e" d="M347.7,230.9 L342.9,279.1"/><path class="e" d="M435.4,219.6 L272.4,290.4"/><path class="e" d="M456.5,230.6 L466.3,279.4"/><path class="e" d="M538.4,219.1 L358.6,290.9"/><path class="e" d="M542.6,225.4 L483.4,284.6"/><path class="e" d="M143,306.5 L281,375.5"/><path class="e" d="M263.5,315 L289.5,367"/><path class="e" d="M332.5,315 L306.5,367"/><path class="e" d="M453,306.5 L315,375.5"/><rect class="n" x="273" y="25" width="50" height="30" rx="15"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">abcd</text><circle class="n" cx="104.5" cy="126" r="18"/><text class="t" x="104.5" y="126" dy=".35em" text-anchor="middle">abc</text><circle class="n" cx="233.5" cy="126" r="18"/><text class="t" x="233.5" y="126" dy=".35em" text-anchor="middle">abd</text><circle class="n" cx="362.5" cy="126" r="18"/><text class="t" x="362.5" y="126" dy=".35em" text-anchor="middle">acd</text><circle class="n" cx="491.5" cy="126" r="18"/><text class="t" x="491.5" y="126" dy=".35em" text-anchor="middle">bcd</text><circle class="n" cx="40" cy="212" r="18"/><text class="t" x="40" y="212" dy=".35em" text-anchor="middle">ab</text><circle class="n" cx="143.2" cy="212" r="18"/><text class="t" x="143.2" y="212" dy=".35em" text-anchor="middle">ac</text><circle class="n" cx="246.4" cy="212" r="18"/><text class="t" x="246.4" y="212" dy=".35em" text-anchor="middle">ad</text><circle class="n" cx="349.6" cy="212" r="18"/><text class="t" x="349.6" y="212" dy=".35em" text-anchor="middle">bc</text><circle class="n" cx="452.8" cy="212" r="18"/><text class="t" x="452.8" y="212" dy=".35em" text-anchor="middle">bd</text><circle class="n" cx="556" cy="212" r="18"/><text class="t" x="556" y="212" dy=".35em" text-anchor="middle">cd</text><circle class="n" cx="126" cy="298" r="18"/><text class="t" x="126" y="298" dy=".35em" text-anchor="middle">a</text><circle class="n" cx="255" cy="298" r="18"/><text class="t" x="255" y="298" dy=".35em" text-anchor="middle">b</text><circle class="n" cx="341" cy="298" r="18"/><text class="t" x="341" y="298" dy=".35em" text-anchor="middle">c</text><circle class="n" cx="470" cy="298" r="18"/><text class="t" x="470" y="298" dy=".35em" text-anchor="middle">d</text><circle class="n" cx="298" cy="384" r="18"/><text class="t" x="298" y="384" dy=".35em" text-anchor="middle">e</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Hasse diagram of (P(A), subset) for A={a,b,c,d}; e is the empty set</figcaption></figure>

Example. $A=\{4,5,6,7\}$ with $\le$: $R$ has 10 pairs (loops $(4,4)\dots(7,7)$ and $(4,5),(4,6),(4,7),(5,6),(5,7),(6,7)$); the digraph has all 10 arcs, the Hasse diagram is the chain 4-5-6-7. $\{0,2,5,10,11,15\}$ under usual $\le$ is the chain 0-2-5-10-11-15.

Answer frame. Open with the definition and covering; list elements and cover pairs; draw levels with the smallest element at the bottom; state minimal and maximal elements; close with "loops and transitive edges are omitted".

Asked: [7 marks] (Dec 2020, Nov 2022, Jun 2024, Jun 2025) $A=\{2,3,6,12,24,36\}$, $x\le y$ if $x$ divides $y$: draw Hasse diagram, find minimal and maximal elements Asked: [7 marks] (May 2019, Jun 2020, Jun 2024) Hasse diagram of $(P(A),\subseteq)$, $A=\{a,b,c,d\}$ Asked: [7 marks] (Nov 2022, Jun 2024, Jun 2025) Hasse diagram of divisors of 36 (and 45); what is a Hasse diagram, draw it for $\{1,2,3,6,9,18\}$ Asked: [7 marks] (May 2019, Jun 2023) Hasse diagram of $\le$ on $\{0,2,5,10,11,15\}$ Asked: [7 marks] (Jun 2023) $A=\{4,5,6,7\}$, $R$ is $\le$: directed graph and Hasse diagram Asked: [7 marks] (Jun 2024) Hasse diagrams of $(P(A),\subseteq)$ for $A=\{a\},\{a,b\},\{a,b,c\},\{a,b,c,d\}$ Asked: [14 marks] (Nov 2018, May 2019) Short notes: Binomial theorem, Multinomial coefficient, Lattices, Hasse diagrams

Isomorphic ordered set

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>Two posets are isomorphic if there is a bijection $f$ with $a\le b \iff f(a)\le f(b)$, so their Hasse diagrams have the same shape.</mark>

Key points.

  1. An isomorphism preserves the number of elements and the cover pairs.
  2. To prove it, list the elements, give the bijection and check that every cover edge maps to a cover edge.
  3. $D_{12}=\{1,2,3,4,6,12\}$, $D_{18}=\{1,2,3,6,9,18\}$: take $1\to1,\ 3\to2,\ 2\to3,\ 6\to6,\ 4\to9,\ 12\to18$; the seven covers of $D_{12}$ map exactly onto the seven covers of $D_{18}$.
  4. $D_{20}=\{1,2,4,5,10,20\}$ has six elements and the same cover pattern (map $1,2,3,4,6,12\to1,2,5,4,10,20$), so in fact $D_{12}\cong D_{18}\cong D_{20}$; non-isomorphism needs a different size, as $D_{16}$ (5) or $D_{30}$ (8).

Pitfall: Do not claim $D_{20}\not\cong D_{12}$ from element count; both have 6 elements and equal structure.

Asked: [7 marks] (Dec 2023) $D_{12}$ and $D_{18}$ are isomorphic lattices; none is isomorphic to $D_{20}$

Well ordered set

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>A poset is well ordered if it is totally ordered and every non-empty subset has a least element; the well-ordering principle says every non-empty set of positive integers has a least element.</mark>

Key points.

  1. Every well-ordered set is a chain, since any two elements form a subset with a least element.
  2. $(\mathbb{N},\le)$ is well ordered but $(\mathbb{Z},\le)$ is not.
  3. A semigroup $(S,*)$ is a non-empty set with a closed associative operation; a monoid is a semigroup with an identity element. Example: $(\mathbb{N},+)$ is a semigroup, $(\mathbb{N}\cup\{0\},+)$ is a monoid with identity 0.
  4. A lattice is a poset in which every pair has a lub and a glb. Example: $(D_{12},|)$ or $(P(A),\subseteq)$, with join = union and meet = intersection.
  5. Truth table of $P\to q$:
$P$ $q$ $P\to q$
T T T
T F F
F T T
F F T

Answer frame. Answer each part in two lines, definition then example; for $P\to q$ draw the four-row table.

Asked: [14 marks] (Nov 2019) i) What is well ordering principle? ii) Define semi groups and monoids. iii) Define a lattice, give example. iv) Truth table for $P\to q$

Properties of lattices

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>A lattice is a poset $(L,\le)$ in which every pair $a,b$ has a unique least upper bound $a\vee b$ (join) and a unique greatest lower bound $a\wedge b$ (meet).</mark>

Key points.

  1. Idempotent ($a\vee a=a$), commutative and associative laws hold for both $\vee$ and $\wedge$.
  2. Absorption: $a\vee(a\wedge b)=a$ and $a\wedge(a\vee b)=a$; also $a\le b \iff a\vee b=b \iff a\wedge b=a$.
  3. Duality: swapping $\le,\vee,\wedge$ with $\ge,\wedge,\vee$ turns each true statement into a true one.
  4. Isotone: $a\le b$ gives $a\vee c\le b\vee c$ and $a\wedge c\le b\wedge c$.
  5. Distributive: $a\wedge(b\vee c)=(a\wedge b)\vee(a\wedge c)$ (and its dual); modular: $a\le c\Rightarrow a\vee(b\wedge c)=(a\vee b)\wedge c$. Distributive implies modular.
  6. A lattice is distributive iff it has no sublattice isomorphic to the diamond $M_3$ or the pentagon $N_5$; a sublattice is closed under $\vee$ and $\wedge$.
  7. Every finite lattice $L=\{a_1,\dots,a_n\}$ is bounded: $1=a_1\vee\dots\vee a_n$ is its unique greatest element and $0=a_1\wedge\dots\wedge a_n$ its unique least, existing by associativity and induction; uniqueness holds as lub and glb are unique.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-04" viewBox="0 0 338 338" width="338" height="338" role="img" aria-label="Diamond M3, not distributive; also the Jun 2020 lattice"><style>#dsfig-u5-04 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-04 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-04 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-04 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-04 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-04 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-04 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-04 .t{fill:#16181D;font-weight:500}#dsfig-u5-04 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-04 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-04 .dot{fill:#16181D}#dsfig-u5-04 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-04 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-04 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-04 .ah{fill:#454C5A}#dsfig-u5-04 .ah.hi{fill:#2340B8}#dsfig-u5-04 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-04 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-04 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-04 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-04 .e{stroke:#B1B7C3}html.dark #dsfig-u5-04 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-04 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-04 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-04 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-04 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-04 .t{fill:#E6E8ED}html.dark #dsfig-u5-04 .t.inv{fill:#0F1115}html.dark #dsfig-u5-04 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-04 .dot{fill:#E6E8ED}html.dark #dsfig-u5-04 .ann{fill:#8FA3FF}html.dark #dsfig-u5-04 .lbl{fill:#858D9C}html.dark #dsfig-u5-04 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-04 .ah{fill:#B1B7C3}html.dark #dsfig-u5-04 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-04 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-04 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-04 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah16" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh16" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M155.6,53.4 L53.4,155.6"/><path class="e" d="M169,59 L169,150"/><path class="e" d="M182.4,53.4 L284.6,155.6"/><path class="e" d="M155.6,284.6 L53.4,182.4"/><path class="e" d="M169,279 L169,188"/><path class="e" d="M182.4,284.6 L284.6,182.4"/><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">1</text><circle class="n" cx="40" cy="169" r="18"/><text class="t" x="40" y="169" dy=".35em" text-anchor="middle">a</text><circle class="n" cx="169" cy="169" r="18"/><text class="t" x="169" y="169" dy=".35em" text-anchor="middle">b</text><circle class="n" cx="298" cy="169" r="18"/><text class="t" x="298" y="169" dy=".35em" text-anchor="middle">c</text><circle class="n" cx="169" cy="298" r="18"/><text class="t" x="169" y="298" dy=".35em" text-anchor="middle">0</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Diamond M3, not distributive; also the Jun 2020 lattice</figcaption></figure>

Proofs.

  • Every chain is distributive: if $b\le c$ then $b\vee c=c$, so LHS $=a\wedge c$, and $a\wedge b\le a\wedge c$ makes RHS $=a\wedge c$. The case $c\le b$ is symmetric.
  • Every chain is modular: let $a\le c$. If $b\le a$ then $b\le a\le c$ and both sides equal $a$. If $a\le b$ then $a\le b\wedge c$, so LHS $=b\wedge c$, and RHS $=b\wedge c$ as $a\vee b=b$.
  • Isotone: $a\le b\le b\vee d$ and $c\le d\le b\vee d$, so $b\vee d$ bounds $a,c$ above and $a\vee c\le b\vee d$. Dually $a\wedge c\le a\le b$ and $a\wedge c\le c\le d$, so $a\wedge c\le b\wedge d$.
  • Cancellation in a distributive lattice ($a\wedge b=a\wedge c$, $a\vee b=a\vee c\Rightarrow b=c$): $$b=b\wedge(a\vee b)=b\wedge(a\vee c)=(b\wedge a)\vee(b\wedge c)=(a\wedge c)\vee(b\wedge c)=(a\vee b)\wedge c=(a\vee c)\wedge c=c.$$
  • Sublattices of $L=\{1,2,3,4,5\}$ with 3 or more elements: $\{1,2,5\},\{1,3,5\},\{1,4,5\}$; $\{1,2,3,5\},\{1,2,4,5\},\{1,3,4,5\}$; and $L$: 7 in all. $\{1,2,3\}$ fails as $2\vee3=5\notin$ it.
  • The Nov 2019 lattice is $M_3$: $a\wedge(b\vee c)=a$ but $(a\wedge b)\vee(a\wedge c)=0$, so it is not distributive.

Answer frame. Open with the definition; for a proof write the chain of equalities naming each law; for a figure test one triple and conclude with $M_3$ or $N_5$ (pentagon 0<a<c<1, 0<b<1).

Asked: [7 marks] (Dec 2024) Distributive lattice: $a\wedge b=a\wedge c$, $a\vee b=a\vee c$ imply $b=c$ Asked: [7 marks] (Nov 2019) Is the lattice in the given Hasse diagram distributive Asked: [7 marks] (Nov 2019) Show that every chain is a distributive lattice Asked: [7 marks] (Dec 2020) Show that every chain is modular Asked: [7 marks] (Jun 2020) All sublattices of $L=\{1,2,3,4,5\}$ with three or more elements Asked: [7 marks] (Dec 2023) Define a lattice; $a\le b$, $c\le d$ give $a\vee c\le b\vee d$, $a\wedge c\le b\wedge d$ Asked: [7 marks] (Jun 2025) Define a lattice; every finite lattice has a unique lub and glb

Bounded and complemented lattices

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. ==A lattice is bounded if it has a least element 0 and a greatest element 1; it is complemented if each $a$ has some $a'$ with $a\wedge a'=0$ and $a\vee a'=1$.==

Key points.

  1. In a distributive lattice the complement of an element, if it exists, is unique; $M_3$ is the non-unique case.
  2. An atom is an element covering 0; a join irreducible element is a non-zero $z$ that is not $x\vee y$ with $x,y<z$, i.e. it covers exactly one element.
  3. A Boolean algebra is a complemented distributive lattice, so it has $2^n$ elements; 5 is not a power of 2, so a 5-element lattice is not Boolean.
  4. Uniqueness of complement: if $b_1,b_2$ both complement $a$, then $b_1=b_1\wedge1=b_1\wedge(a\vee b_2)=(b_1\wedge a)\vee(b_1\wedge b_2)=0\vee(b_1\wedge b_2)=b_1\wedge b_2$; symmetrically $b_2=b_1\wedge b_2$, so $b_1=b_2$.
  5. Equivalence in a distributive complemented lattice: (i)$\Rightarrow$(ii): $a\wedge\bar b\le b\wedge\bar b=0$. (ii)$\Rightarrow$(iii): De Morgan, $\bar a\vee b=\overline{a\wedge\bar b}=1$. (iii)$\Rightarrow$(iv): $\bar b=\bar b\wedge(\bar a\vee b)=\bar b\wedge\bar a$, so $\bar b\le\bar a$. (iv)$\Rightarrow$(i): complement both sides.

Example. Lattice $M$ (Jun 2023). Atoms: $a,b$. Non-zero join irreducibles: $a,b,d$ (each covers one element); $c=a\vee b$ and $1=c\vee d$ are reducible. $M$ is distributive (no $M_3$ or $N_5$) but not complemented: $b$ and $c$ have no complement (only $a,d$ complement each other).

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-05" viewBox="0 0 295 338" width="295" height="338" role="img" aria-label="Lattice M of Jun 2023"><style>#dsfig-u5-05 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-05 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-05 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-05 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-05 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-05 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-05 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-05 .t{fill:#16181D;font-weight:500}#dsfig-u5-05 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-05 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-05 .dot{fill:#16181D}#dsfig-u5-05 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-05 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-05 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-05 .ah{fill:#454C5A}#dsfig-u5-05 .ah.hi{fill:#2340B8}#dsfig-u5-05 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-05 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-05 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-05 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-05 .e{stroke:#B1B7C3}html.dark #dsfig-u5-05 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-05 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-05 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-05 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-05 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-05 .t{fill:#E6E8ED}html.dark #dsfig-u5-05 .t.inv{fill:#0F1115}html.dark #dsfig-u5-05 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-05 .dot{fill:#E6E8ED}html.dark #dsfig-u5-05 .ann{fill:#8FA3FF}html.dark #dsfig-u5-05 .lbl{fill:#858D9C}html.dark #dsfig-u5-05 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-05 .ah{fill:#B1B7C3}html.dark #dsfig-u5-05 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-05 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-05 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-05 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah17" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh17" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M155.6,53.4 L96.4,112.6"/><path class="e" d="M182.4,53.4 L241.6,112.6"/><path class="e" d="M74.5,143 L48.5,195"/><path class="e" d="M96.4,139.4 L155.6,198.6"/><path class="e" d="M241.6,139.4 L182.4,198.6"/><path class="e" d="M53.4,225.4 L112.6,284.6"/><path class="e" d="M160.5,229 L134.5,281"/><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">1</text><circle class="n" cx="83" cy="126" r="18"/><text class="t" x="83" y="126" dy=".35em" text-anchor="middle">c</text><circle class="n" cx="255" cy="126" r="18"/><text class="t" x="255" y="126" dy=".35em" text-anchor="middle">d</text><circle class="n" cx="40" cy="212" r="18"/><text class="t" x="40" y="212" dy=".35em" text-anchor="middle">a</text><circle class="n" cx="169" cy="212" r="18"/><text class="t" x="169" y="212" dy=".35em" text-anchor="middle">b</text><circle class="n" cx="126" cy="298" r="18"/><text class="t" x="126" y="298" dy=".35em" text-anchor="middle">0</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Lattice M of Jun 2023</figcaption></figure>

Answer frame. Open with the definitions; for proofs write the chains of points 4 and 5; for the figure list atoms, irreducibles, then test complements one by one.

Asked: [7 marks] (Dec 2020) Distributive complemented lattice: $a\le b$, $a\wedge\bar b=0$, $\bar a\vee b=1$, $\bar b\le\bar a$ are equivalent Asked: [7 marks] (Jun 2023) Lattice $M$: non-zero join irreducibles and atoms; distributive and complemented? Asked: [7 marks] (Jun 2024) Complement of each element in a Boolean algebra is unique; a lattice with 5 elements is not Boolean

Combinatorics: introduction, permutation and combination

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. ==A permutation is an ordered arrangement, $P(n,r)=\dfrac{n!}{(n-r)!}$, and a combination is an unordered selection, $C(n,r)=\dfrac{n!}{r!\,(n-r)!}$.==

Formula. Repeats $n_1,n_2,\dots$: $\dfrac{n!}{n_1!\,n_2!\cdots}$; circular $(n-1)!$; $P(n,r)=r!\,C(n,r)$. Inclusion-exclusion: $|A\cup B\cup C\cup D|=S_1-S_2+S_3-S_4$ ($S_k$ = sum of all $k$-fold intersections); none of them $=N-$ union.

Key points.

  1. Use permutations when order matters and combinations when it does not; "either ... or" cases add, "and" choices multiply.
  2. "All vowels together": glue them as one block, arrange the block among the others, then arrange inside it.
  3. Multiples of $k$ up to $N$ number $\lfloor N/k\rfloor$; of both $k,m$ number $\lfloor N/\operatorname{lcm}(k,m)\rfloor$.

Example. MATHEMATICS: 11 letters (M2, A2, T2, others 1); vowels A,E,A,I. Block AEAI plus 7 consonants = 8 units with M and T repeated: $\frac{8!}{2!\,2!}=10080$. Inside the block: $\frac{4!}{2!}=12$. Total $10080\times12=\mathbf{120960}$.

Example. 1 to 250 divisible by 2, 3, 5 or 7: $S_1=125+83+50+35=293$; $S_2$ (6,10,14,15,21,35) $=41+25+17+16+11+7=117$; $S_3$ (30,42,70,105) $=8+5+3+2=18$; $S_4$ (210) $=1$. Union $=293-117+18-1=\mathbf{193}$.

Example. 1 to 500 divisible by none of 2,3,5,7: $S_1=587$, $S_2=83+50+35+33+23+14=238$, $S_3=16+11+7+4=38$, $S_4=2$. Union $=587-238+38-2=385$; count $=500-385=\mathbf{115}$.

Example. 1 to 300 with 3, 5, 7: $|A|=100,|B|=60,|C|=42$; pairs $20,14,8$; triple $\lfloor300/105\rfloor=2$. Union $=100+60+42-20-14-8+2=162$; neither $=300-162=\mathbf{138}$. Divisible by 3 only $=100-20-14+2=\mathbf{68}$.

Example. 10 bulbs, 3 defective, 7 good, sample of 4: (i) $C(10,4)=\mathbf{210}$. (ii) $C(7,2)\,C(3,2)=21\times3=\mathbf{63}$. (iii) $C(7,3)C(3,1)+C(7,1)C(3,3)=105+7=\mathbf{112}$.

Answer frame. Open with the formula; define the sets; list $S_1$ to $S_4$; substitute; state the count.

Asked: [7 marks] (Dec 2020, Dec 2024) Integers between 1 and 250 divisible by any of 2, 3, 5, 7 Asked: [7 marks] (Dec 2024) Numbers 1 to 500 divisible by none of 2, 3, 5, 7 Asked: [7 marks] (Dec 2024) 10 bulbs, 3 defective: ways to pick 4; 2 good 2 defective; 3 good 1 defective or 1 good 3 defective Asked: [14 marks] (Jun 2020) Integers 1 to 300 divisible by none of 3, 5, 7; by 3 but not 5 nor 7 Asked: [7 marks] (Jun 2025) Permutations of MATHEMATICS with all vowels together

Binomial theorem

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. ==For a non-negative integer $n$, $(x+y)^n=\sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^{k}$.==

Key points.

  1. The expansion has $n+1$ terms with general term $T_{k+1}=\binom{n}{k}x^{n-k}y^k$.
  2. Coefficients are symmetric, $\binom nk=\binom n{n-k}$, and follow Pascal's rule.
  3. Putting $x=y=1$ gives $\sum\binom nk=2^n$; example $(x+y)^3=x^3+3x^2y+3xy^2+y^3$.

Multinomial coefficients

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. ==The multinomial coefficient $\binom{n}{k_1,\dots,k_m}=\dfrac{n!}{k_1!\cdots k_m!}$ (with $\sum k_i=n$) is the coefficient of $x_1^{k_1}\cdots x_m^{k_m}$ in $(x_1+\dots+x_m)^n$.==

Key points.

  1. It counts arrangements of $n$ objects with $k_1$ of one kind, $k_2$ of another, and so on.
  2. The number of terms in the expansion is $\binom{n+m-1}{m-1}$.
  3. Example: coefficient of $x^2yz$ in $(x+y+z)^4$ is $\frac{4!}{2!\,1!\,1!}=12$.

Recurrence relation and recursive algorithms

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>A recurrence relation expresses $a_n$ in terms of earlier terms such as $a_{n-1},a_{n-2}$; it defines the sequence once initial values are given.</mark>

Key points.

  1. Its order is the gap between the largest and smallest index, so $a_n=a_{n-1}+a_{n-2}$ has order 2, and it needs 2 initial conditions.
  2. A recursive algorithm calls itself on a smaller input, e.g. factorial $a_n=n\,a_{n-1}$ or Tower of Hanoi $T_n=2T_{n-1}+1$.

Linear recurrence relations with constant coefficients

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. ==A linear recurrence with constant coefficients has the form $c_0a_n+c_1a_{n-1}+\dots+c_ka_{n-k}=f(n)$ with constants $c_i$; it is homogeneous when $f(n)=0$.==

Steps. Write the characteristic equation (replace $a_n$ by $r^n$); solve for the roots; distinct roots give $A r_1^n+Br_2^n$, a repeated root gives $(A+Bn)r^n$; use the initial conditions for $A,B$.

Key points.

  1. The characteristic equation of $a_n-a_{n-1}-6a_{n-2}=0$ is $r^2-r-6=0$.
  2. The order equals the number of constants and initial conditions.

Example. $a_n=a_{n-1}+6a_{n-2}$, $a_0=3,a_1=6$: $r^2-r-6=0\Rightarrow r=3,-2$, so $a_n=A3^n+B(-2)^n$. From $A+B=3$ and $3A-2B=6$: $A=\frac{12}5$, $B=\frac35$. $a_n=\frac{12}{5}3^n+\frac35(-2)^n$ (check: $a_1=\frac{36}5-\frac65=6$).

Example. $a_r-7a_{r-1}+10a_{r-2}=0$, $a_0=0,a_1=6$: $x^2-7x+10=0\Rightarrow2,5$; $C_1+C_2=0$, $2C_1+5C_2=6$ give $C_2=2$, $C_1=-2$: $a_r=2\cdot5^r-2\cdot2^r$.

Example (Fibonacci). $f_n=f_{n-1}+f_{n-2}$, $f_0=0,f_1=1$: $r^2-r-1=0\Rightarrow r_{1,2}=\frac{1\pm\sqrt5}2$; $f_0=0,f_1=1$ give $c_1=\frac1{\sqrt5},c_2=-\frac1{\sqrt5}$, so $$f_n=\frac1{\sqrt5}\left[\left(\frac{1+\sqrt5}2\right)^n-\left(\frac{1-\sqrt5}2\right)^n\right].$$

Answer frame. Open with the standard form; characteristic equation and roots; general solution; two initial conditions; final $a_n$.

Asked: [7 marks] (Nov 2018, Jun 2020) Solve $a_n=a_{n-1}+6a_{n-2}$, $a_0=3$, $a_1=6$; solve $a_r-7a_{r-1}+10a_{r-2}=0$, $a_0=0,a_1=6$ Asked: [7 marks] (Nov 2022) Explicit formula for the Fibonacci numbers, $f_n=f_{n-1}+f_{n-2}$, $f_0=0,f_1=1$

Homogeneous solutions

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. ==The homogeneous solution solves the relation with right side 0 and is $a_n^{(h)}=\sum A_ir_i^n$ over the roots of the characteristic equation.==

Key points.

  1. Any linear combination of solutions of a homogeneous relation is again a solution.
  2. To verify, substitute and show the left side is 0: for $a_n=c_12^n+c_24^n$ in $a_n-6a_{n-1}+8a_{n-2}=0$: the $2^n$ part gives $2^n\left(1-3+2\right)=0$ and the $4^n$ part gives $4^n\left(1-\frac32+\frac12\right)=0$, so the sum is 0 for all $c_1,c_2$.

Asked: [7 marks] (Dec 2023) Show that $a_n=c_12^n+c_24^n$ is a solution of $a_n-6a_{n-1}+8a_{n-2}=0$

Particular solutions

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>A particular solution is any one solution of the full relation $f(n)\ne0$, found by assuming a trial form that copies the shape of $f(n)$ and solving for its coefficients.</mark>

Key points.

  1. Trial forms: $f=$ polynomial of degree $d$ gives a polynomial of degree $d$; $f=c\,k^n$ gives $A\,k^n$; if $k$ is a characteristic root multiply the trial by $n$.
  2. Substitute the trial and equate coefficients of like powers. Example: $a_r+5a_{r-1}+6a_{r-2}=3r^2$, trial $Ar^2+Br+C$. Coefficient of $r^2$: $12A=3\Rightarrow A=\frac14$; of $r$: $12B-34A=0\Rightarrow B=\frac{17}{24}$; constant: $12C+29A-17B=0\Rightarrow C=\frac{115}{288}$. Particular solution $a_r^{(p)}=\frac{r^2}4+\frac{17r}{24}+\frac{115}{288}$ (its homogeneous roots are $-2,-3$).

Asked: [7 marks] (May 2019) Determine the particular solution of $a_r+5a_{r-1}+6a_{r-2}=3r^2$

Total solutions

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. ==The total solution is the sum of the homogeneous and the particular solution, $a_n=a_n^{(h)}+a_n^{(p)}$.==

Key points.

  1. The constants in the homogeneous part are found only after adding the particular part, using the initial conditions.
  2. Example: $S(n+1)-2S(n)=4^n$ has $a^{(h)}=A2^n$ and $a^{(p)}=\frac{4^n}2$.
  3. Then $S(0)=1$ gives $A=\frac12$, so $S(n)=\frac{2^n+4^n}2$.

Generating functions

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. ==The generating function of the sequence $a_0,a_1,a_2,\dots$ is $A(x)=\sum_{r\ge0}a_rx^r$, and the sequence is the numeric function whose $r$th term is the coefficient of $x^r$.==

Formula. $\dfrac1{1-ax}=\sum a^rx^r$; $\dfrac{1-x^{n+1}}{1-x}=1+x+\dots+x^n$; $(1+x)^n=\sum\binom nrx^r$; $\dfrac1{(1-x)^n}=\sum\binom{n+r-1}{r}x^r$.

Key points.

  1. Multiplying $A(x)$ by $x^k$ shifts the sequence right by $k$ places, and sums and constant multiples add termwise.
  2. A finite sequence gives a polynomial, which sums to a closed form by the geometric series.
  3. To recover the sequence, simplify, use partial fractions if needed, and expand with the standard series.

Example. $A(z)=\frac{(1+z)^2}{(1+z)^4}=\frac1{(1+z)^2}=(1+z)^{-2}=\sum\binom{r+1}{r}(-z)^r$, so $a_r=(-1)^r(r+1)$: $1,-2,3,-4,\dots$

Example. $G(x)=\frac{x}{1-2x}=x\sum2^nx^n=\sum2^nx^{n+1}$, so $a_n=2^{n-1}$ for $n\ge1$ and $a_0=0$: $0,1,2,4,8,\dots$

Example. Sequence $4,4,4,4,4,4$: $G(x)=4(1+x+\dots+x^5)=\dfrac{4(1-x^6)}{1-x}$. For seven 4's: $\dfrac{4(1-x^7)}{1-x}$.

Complete digraph. A complete digraph on $n$ vertices has a directed edge in both directions between every pair of distinct vertices, so it has $n(n-1)$ edges; example $K_3$ has 3 vertices and 6 arcs.

Answer frame. Open with $A(x)$; rewrite into a standard form; expand and read off the coefficient; close with the first few terms. For the mixed question add two lines on the complete digraph.

Asked: [7 marks] (Jun 2020, Dec 2023) Determine the discrete numeric function for $A(z)=\frac{(1+z)^2}{(1+z)^4}$ Asked: [7 marks] (Dec 2023) Find the sequence having generating function $G(x)=\frac{x}{1-2x}$ Asked: [7 marks] (Dec 2024) Generating function for the sequence 4, 4, 4, 4, 4, 4 (or seven 4's); explain complete digraph

Solution by method of generating functions

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>Solving a recurrence by generating functions means multiplying it by $x^n$, summing over all $n$, solving the resulting equation for $A(x)$ and reading off the coefficient of $x^n$.</mark>

Steps. Multiply by $x^n$ and sum; express each sum through $A(x)$ using the initial values; solve for $A(x)$; split by partial fractions and expand to read the coefficient.

Key points.

  1. $\sum_{n\ge0}a_{n+1}x^n=\frac{A(x)-a_0}{x}$ and $\sum_{n\ge2}a_{n-1}x^n=x\,(A(x)-a_0)$.
  2. Non-homogeneous right sides use $\sum4^nx^n=\frac1{1-4x}$ and $\sum(8K+6)x^K=\frac{8x}{(1-x)^2}+\frac6{1-x}$.

Example. $S(n+1)-2S(n)=4^n$, $S(0)=1$. Multiply by $x^n$ and sum: $\frac{G-1}{x}-2G=\frac1{1-4x}$, so $G(1-2x)=1+\frac{x}{1-4x}=\frac{1-3x}{1-4x}$ and $$G(x)=\frac{1-3x}{(1-2x)(1-4x)}=\frac{1/2}{1-2x}+\frac{1/2}{1-4x}.$$ Hence $S(n)=\mathbf{\tfrac12\,(2^n+4^n)}$: $1,3,10,36,\dots$ (check: $S(1)=2\cdot1+1=3$).

Example. $G(K)-7G(K-1)+10G(K-2)=8K+6$. Sum over $K\ge2$ with $A(x)=\sum G(K)x^K$: $$\big(A-G_0-G_1x\big)-7x\big(A-G_0\big)+10x^2A=\sum_{K\ge2}(8K+6)x^K,$$ and $1-7x+10x^2=(1-2x)(1-5x)$. Partial fractions in $\frac1{1-2x},\frac1{1-5x}$ plus the terms from $\frac{8x}{(1-x)^2}$ and $\frac6{1-x}$ give $$G(K)=C_12^K+C_25^K+2K+8,$$ where $C_1+C_2=G(0)-8$ and $2C_1+5C_2=G(1)-10$ (the part $2K+8$ is the particular solution).

Answer frame. Open with "let $A(x)=\sum a_nx^n$"; write the summed equation; solve for $A(x)$; partial fractions; close with the coefficient and a check.

Asked: [7 marks] (Dec 2024) Solve $G(K)-7G(K-1)+10G(K-2)=8K+6$ using generating function Asked: [7 marks] (Nov 2019) Use generating function to solve $S(n+1)-2S(n)=4^n$ with $S(0)=1$, $n\ge0$

Last-minute revision

  • Hasse diagram: cover pairs only, no loops, no transitive edges, no arrows; $P(A)$ has $2^n$ nodes with $\binom nk$ on level $k$.
  • $A=\{2,3,6,12,24,36\}$: minimal 2, 3, maximal 24, 36.
  • Lattice: every pair has join and meet; every chain is distributive and modular; distributive iff no $M_3$ or $N_5$.
  • Complement is unique in a distributive lattice; Boolean algebra has $2^n$ elements.
  • MATHEMATICS with vowels together: 120960; bulbs: 210, 63, 112.
  • Up to 500 none of 2,3,5,7: 115; up to 250 any: 193; up to 300 neither 3,5,7: 138, only 3: 68.
  • Roots: $3,-2$; $2,5$; Fibonacci $\frac{1\pm\sqrt5}2$.
  • $\frac1{1-ax}\leftrightarrow a^n$; $\frac1{(1+z)^2}\leftrightarrow(-1)^r(r+1)$; $\frac{x}{1-2x}\leftrightarrow2^{n-1}$; $S(n)=\frac12(2^n+4^n)$.

Memory hooks

  • Hasse = skeleton of the order: no loops, no shortcuts, no arrows.
  • Forbidden pair for distributive: $M_3$ diamond and $N_5$ pentagon.
  • Inclusion-exclusion signs: singles plus, pairs minus, triples plus, quadruple minus.
  • Total solution = homogeneous (roots) + particular (guess shaped like the right side).

Coverage checklist

  • Introduction, ordered set: Jun 2020.
  • Hasse diagram of partially, ordered set: all eight Hasse questions and Nov 2018, May 2019 short notes.
  • isomorphic ordered set: Dec 2023.
  • well ordered set: Nov 2019.
  • properties of Lattices: seven questions, Nov 2019 to Jun 2025.
  • bounded and complemented lattices: Dec 2020, Jun 2023, Jun 2024.
  • Combinatorics: Introduction, Permutation and combination: five questions.
  • Binomial Theorem
  • Multimonial Coefficients
  • Recurrence Relation and Generating Function: Introduction to Recurrence Relation and Recursive algorithms
  • Linear recurrence relations with constant coefficients: three questions.
  • Homogeneous solutions: Dec 2023.
  • Particular solutions: May 2019.
  • Total solutions
  • Generating functions: three questions.
  • Solution by method of generating functions: Nov 2019, Dec 2024.
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in