کارت‌های مطالعه

Recognize the right-scan + carry-from-the-right pattern that computes x+1 in binary.

The subset-of-a-subset identity C(n, r)C(r, k)=C(n, k)C(n-k, r-k) lets you factor a fixed C(n, k) out of any sum over the middle index, after which the leftover collapses to a clean row sum such as 2^(n-k) .

An edge is a bridge exactly when it lies on no cycle, so a bridgeless graph is one in which every edge sits on some cycle.

Every set is strictly smaller than its power set, X < P(X) , so no surjection (and hence no bijection) X → P(X) exists — which is why P(N) = 2^(ℵ_0) > ℵ_0 .

The set of all functions A→ B has cardinality B ^( A ) , and cardinal-exponent identities collapse most "big-looking" function spaces over a countable domain down to the continuum 2^(ℵ_0) .

To keep restricted items apart, seat the unrestricted majority first, then drop the restricted items into the gaps between them.

Countability survives countable unions, finite-subset collections, and surjective images, because ℵ_0·ℵ_0=ℵ_0 and a surjection f:Btwoheadrightarrow A forces A ≤ B .

The number of walks of length k from i to j is the (i,j) entry of A^k ; length- 2 paths come from counting neighbor-pairs per vertex.

A consistent theory with no finite models that is categorical in some infinite cardinal is complete (Los-Vaught); DLO without endpoints and the Rado graph are the textbook examples, both made categorical by Cantor's back-and-forth.

A preceq B holds iff every existential formula with a witness in B already has one in A (Tarski-Vaught), and the union of an elementary chain is an elementary extension of each member.

To count tilings or step-climbing sequences, case on the leftmost piece (or first move): each choice removes a fixed prefix and leaves a smaller instance, turning the count into a linear recurrence.

Translate natural language by pairing ∀ with → and ∃ with ∧ ; remember ∀ distributes over ∧ and ∃ over ∨ (and never the mismatched pairs).

For any set X the Hartogs number ℵ(X) is, provably in ZF alone, the least ordinal that does not inject into X — the engine that turns the Axiom of Choice into the Well-Ordering Theorem.

Size of a union of n sets is the alternating sum over all intersections; sieving by the prime divisors of m counts integers coprime to m .

When vertices are the k -subsets of an n -set and edges encode a fixed intersection size, the graph is automatically regular, and its degree and edge count fall straight out of binomial counting.

An argument is valid (and Γ⊨φ holds) exactly when no interpretation makes all premises true and the conclusion false, so one counterexample is enough to refute it.

Pairwise-distinct edge weights force a single MST; uniqueness fails exactly when some cycle has a non-unique heaviest edge (a tie), so ties — not the cheapest edge — decide the count.

Guess a particular solution shaped like the forcing term (polynomial, exponential, or their product), match coefficients to solve for it, and multiply by a power of n whenever the guess collides with a root of the homogeneous part.

DNF is an OR of ANDs of literals and CNF is an AND of ORs of literals; every propositional formula is logically equivalent to one of each.

Ordinal sum and product are defined by "concatenating" order types and are associative but not commutative — a finite ordinal is absorbed on the left ( n+ω=ω , 2·ω=ω ) yet sticks out on the right ( ω+n>ω , ω· 2>ω ).

Ordinal exponentiation is defined by a supremum at limit stages, so a finite base raised to ω collapses to ω ( 3^ω=ω ), whereas the same expression read as cardinals gives the continuum ( 3^(ℵ_0)=2^(ℵ_0) ).

If n+1 items land in n boxes, some box holds two; generalized, N items force a box with ⌈ N/n ⌉ — the engine behind "smallest forcing n " exam problems via residue/parity coloring.

Being a member of P(A) means being a subset of A : S ∈ P(A) ⇔ S ⊆ A .

When a characteristic root r is repeated with multiplicity m , it contributes (c_0 + c_1 n + … + c_(m-1) n^(m-1)) r^n to the general solution, not just c r^n .

The number of nonnegative integer solutions of x_1+⋯+x_k=n is C(n+k-1, k-1) ; clear lower bounds by shifting variables, and switch to the bars-in-gaps count when objects are ordered.

The number of trailing zeros of n! in base b is the minimum, over the prime powers p^e b , of ⌊ v_p(n!)/e ⌋ , where Legendre's formula gives v_p(n!) = ∑_(i≥ 1) ⌊ n/p^i ⌋ .

For an NP-hard optimization problem, a polynomial-time rho-approximation guarantees a solution within a factor rho of the optimum; the ratio is a monotone worst-case bound (factor c gives every c' >= c for free) and is defined only for optimization, never for decision, problems.

DP applies when an optimal solution is built from optimal solutions of overlapping subproblems; pick a state, write a recurrence, and evaluate it bottom-up (tabulation) or top-down (memoization).

In any flow network the value of a maximum s - t flow equals the capacity of a minimum s - t cut; a flow is maximum exactly when its residual graph has no augmenting path, which is how Ford-Fulkerson finds it.

A problem is NP-complete when it is both in NP and NP-hard; under the assumption P ≠ NP such problems have no polynomial-time algorithm, and we prove hardness by a polynomial-time reduction from a known hard problem like SAT, Knapsack, or TSP.

The arc length of y=f(x) is ∫√(1+(y')^2) dx ; for the catenary y=acosh(x/a) the identity 1+sinh^2=cosh^2 erases the square root, giving length asinh(x_1/a) .

Through any n+1 points with distinct nodes there is a unique polynomial of degree ≤ n ; Lagrange and Newton are two ways to build the same polynomial.

To solve f(x)=0 , iterate x_(n+1)=x_n-(f(x_n))/(f'(x_n)) — each step replaces f by its tangent line and takes its root; near a simple root it doubles the number of correct digits per step.

Integrate by parts to express an integral with exponent n in terms of the same integral with a smaller exponent, building a recurrence you can iterate down to a base case.

A set of connectives is functionally complete if it can express every truth function; ¬, ∧ , ¬, ∨ , and ¬, → all qualify, and the single connectives NAND ( ) and NOR ( downarrow ) each suffice on their own.

Encode a sequence a_0,a_1,… as the coefficients of a power series ∑ a_n x^n , then turn counting and recurrence problems into algebra: multiply to combine choices, and extract [x^n] to read off the answer.

Prove propositional formulas with introduction/elimination rules arranged into a derivation tree, discharging temporary assumptions via → I ; the system is both sound (only valid conclusions follow) and complete (every tautology is derivable).

Two ordered sets have the same order type when an order-preserving bijection links them; a well-order (every non-empty subset has a least element) has a unique ordinal as its order type, so being well-ordered and unbounded above does not make a set look like N .

A poset is a set with a reflexive, antisymmetric, transitive order; under divisibility x preceq y ⇔ x y the integers form a lattice where gcd is the meet and lcm is the join.

The rook polynomial counts non-attacking rook placements on a board with forbidden squares; its top coefficient is the permanent of the allowed-cell matrix.

Every nonzero ordinal is either a successor S(β)=β∪ β =β+1 (it has a largest element / immediate predecessor) or a limit ordinal (nonzero, no maximum, equal to the supremum of everything below it); ω is the first limit ordinal, while ω+1 is a successor.

Collisions are resolved by chaining or open addressing; with load factor α = n/m kept O(1) , search costs expected Θ(1+α) = O(1) under simple uniform hashing.

A linked list trades the array's O(1) random access for O(1) insert/delete at a known node, but pays Θ(n) to search — so binary search never applies, even on a sorted list.

Push 1… n in order and pop at will: the reachable output orders are exactly the 231-avoiding permutations, and there are C_n = C(2n, n)/(n+1) of them.

Trace BFS (queue) and DFS (stack/recursion) deterministically by breaking every tie in alphabetical order — and read off the first/last vertex visited.

Dijkstra finalizes vertices in increasing distance order; each time one is extracted, it relaxes all of that vertex's outgoing edges — so the edge-relaxation sequence is dictated by the extract-min order.

Find the order of the VALUE a loop prints — not its running time — by turning the nested loops into a closed-form sum or product and reading off its leading power.

Pairing geometric and arithmetic means makes one sequence climb and the other fall; AM–GM traps them between each other, so both converge to a shared limit.

The radius of a power series is 1/limsup c_n ^(1/n) — the root test that always works, even when the ratio test fails.

When an equation mixes z with bar z , Re(z) , Im(z) or z , it is not a polynomial — write z = x + iy and solve the real system.

If f is continuous and one-to-one on an interval, it must be strictly increasing or strictly decreasing — and then it maps the interval onto another interval of the same type.

Reflecting the variable across the midpoint of the interval leaves a definite integral unchanged; adding the original to the reflected copy often collapses a hopeless integrand into something trivial.

Any sequence built from a single geometric power rⁿ is decided by where r sits relative to ±1; for aₙ = rⁿ/(rⁿ+1) the limit is 0, ½, or 1 — after first checking the term is even defined.

When the unknown function sits both outside and inside an integral with a variable upper limit, differentiate both sides: the FTC turns the integral into a value of the integrand, collapsing the equation into a solvable ODE.

To find a root of a continuous function, take the supremum of the set where it is still negative — continuity squeezes the value there to exactly zero from both sides.

When a limit has a variable-limit integral ∫_0^x g(t) dt on top of a 0/0 (or ∞/∞ ) quotient, differentiate it with the FTC — its derivative is just g(x) — and the integral disappears.

Replace each piece of a 0/0 quotient by its Maclaurin series, keep terms up to the first surviving power, and read the limit off the leading coefficients.

For continuous nonnegative f on a finite interval, the n-th-root of the integral of fⁿ converges to the maximum of f — so ∫fⁿ grows like (max f)ⁿ.

An equality of two distances in the complex plane is a 'set of equidistant points' — geometrically the perpendicular bisector of the segment joining the two centers.

On an interval the sign of f' gives whether f rises or falls and the sign of f'' gives whether f' rises or falls; a one-sided monotone-bounded f' has a finite limit that equals the one-sided derivative.