Counting by Correspondence
Paths from to that never go above number : reflect each bad path across after its first touch to get a bijection with all paths to .
A bijection is a proof when both the map and its inverse are described and shown to land in the right set; "reflect" must come with "and the reflected path ends at , and reflecting again recovers the original". Catalan numbers count triangulations, parenthesizations, and non-crossing matchings by the same recurrence — an answer of or is a strong hint that Catalan is behind it.
Non-attacking rook placements on an board are permutations; forbidding the main diagonal gives derangements , and forbidding neighbors around a circle of people gives a matching count by inclusion–exclusion over the cycle's edges: with .
Inclusion–exclusion over a STRUCTURED family (the edges of a cycle, the diagonal cells) needs the count of pairwise-compatible forbidden objects — for a cycle that is the number of -matchings, a Lucas-number-like quantity. Write the general term, compute separately, and only then assemble the alternating sum.
Subsets of whose size equals their minimum number : sum over , a shallow diagonal of Pascal's triangle. Subsets with no two consecutive elements number .
Two proofs to know: the diagonal identity by Pascal's rule (both sides satisfy the Fibonacci recurrence), and the tiling bijection (squares and dominoes). When a count comes out Fibonacci, one of these is the intended proof.
The medial triangle is the image of under the homothety at the centroid with ratio ; the anticomplementary triangle (lines through each vertex parallel to the opposite side) has ratio and four times the area. Tangent circles are homothetic from their tangency point with ratio .
A homothety sends lines to parallel lines, circles to circles, and scales every length by and every area by . Locating its center — a centroid, a tangency point, an intersection of common tangents — is the whole problem; the ratio then reads off any pair of corresponding lengths.
How many sequences of H's and T's have every prefix containing at least as many H's as T's?
.