ریاضیات گسستهDiscrete Mathematics

Turn a constant-coefficient recurrence into a polynomial; its roots (and their multiplicity) give the closed form.

On subsets of N, A is equivalent to B iff A delta B is finite: each class is countable, but there are continuum-many classes.

A function is a total single-valued map; injectivity/surjectivity/bijectivity control cardinality, and preimages commute with every set operation while images only respect unions.

For nested indexed intervals, a union takes the largest member and an intersection takes the smallest.

To negate a quantified sentence, push the negation inward: flip every quantifier ( ∀leftrightarrow∃ ) in order and negate the innermost predicate, turning ∧/∨ and → by De Morgan.

When some elements are locked into specific slots, only permute the remaining free elements.

Zorn's Lemma, the Hausdorff Maximal Principle, well-ordering, and cardinal comparability are all logically equivalent to the Axiom of Choice.

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 ⌋ .

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.

Irrational just means "not a fraction"; algebraic vs. transcendental is a finer split — algebraic numbers are roots of integer polynomials and are closed under arithmetic and radicals, while transcendental numbers like π and e satisfy no such polynomial.

(x+y)^n=∑_(k=0)^nC(n, k)x^ky^(n-k) ; read backwards, any sum ∑_kC(n, k)c^k collapses to (1+c)^n .

"if" introduces the hypothesis, "only if" the necessary consequent, and "unless" means "if not" — three connectives, three fixed implication patterns that konkur loves to swap.

Each rung pair holds at most one vertex, so a large independent set fixes which columns are used; the empty columns cut the rest into paths, and every path contributes a factor of 2 (outer/inner must alternate).

Color the cells/vertices in a dependency order; each new one has k minus the number of already-colored neighbors choices, and you multiply.

Count the truth assignments that make a formula true by exploiting free variables, shared-head case splits, and the 2^r - 1 rule for a single clause.

A reflexive, symmetric, transitive relation slices a set into disjoint equivalence classes that partition it; count the distinct classes, not the elements.

To decide if a first-order formula is true, plug the structure's domain and the interpretations of its predicate/function symbols into the formula, then evaluate atoms, connectives, and quantifiers over that domain.

To count tile/object placements on a damaged or restricted board, count on the clean board and subtract the placements the obstruction kills: #good= #all- #blocked .

The hypercube Qn connects n-bit strings (or subsets of an n-set) that differ in one bit; it is n-regular and bipartite, and for n >= 1 always has a perfect matching and a Hamiltonian cycle (n >= 2).

∏_(i∈ I) X_i is the set of choice functions f:I→bigcup_i X_i with f(i)∈ X_i — one element picked from each X_i .

A monotone F:P(A)→ P(A) has a least fixed point, equal to bigcap X : F(X)⊆ X — the intersection of all its pre-fixed points.

A tree has at most one perfect matching (uniqueness, via the acyclic symmetric-difference argument); and any graph on 2n vertices with minimum degree ≥ n has a perfect matching (existence, Dirac-type).

A linear recurrence reduced mod m depends only on a finite state of past residues, so its residue sequence is eventually periodic — find the period, then answer any far-out term with n mod p .

Count injective assignments (distinct objects to distinct slots) under forbidden pairings by placing the most-constrained slot first and multiplying the shrinking choice counts.

S(n,k) counts the ways to split an n -set into exactly k nonempty, unlabeled blocks; use the recurrence S(n,k)=k S(n-1,k)+S(n-1,k-1) or direct case-by-size counting.

A 2-(v,k,λ) design is a family of k-subsets (blocks) of a v-set in which every pair of points lies in exactly λ blocks. Two counting identities fix r and b; the Fano plane is the 2-(7,3,1) design, and complementing its blocks gives the 2-(7,4,2) design.

Interior is the largest open set inside A, closure the smallest closed set containing A, and boundary what is left over; complementing swaps interior and closure via two duality identities.

Every simple planar graph on n ≥ 3 vertices has at most 3n−6 edges — a direct consequence of Euler's formula, and an instant non-planarity test.

If a count cares only about the relative order of k special positions and otherwise treats all their orderings symmetrically, exactly 1/k! of the unconstrained configurations realize each fixed order.

Each ZF axiom is a license to form a new set from old ones; knowing which axiom does which job lets you justify every set-building step.

To count how many small boxes fit in a grid, multiply the number of orientations by the number of positions per orientation — and each axis of size N holds a segment of length L in exactly N-L+1 positions.

Key lower and upper bounds on the chromatic number χ(G) : the independence-number lower bound χ ≥ n/α , greedy degree-based upper bounds, and the minimum-degree property of color-critical graphs.

The exact number of spanning trees is any cofactor of the Laplacian (Matrix-Tree), but for graphs glued at cut vertices the count simply multiplies block by block — a cycle of length k contributes a factor of k.

If G is Hamiltonian then deleting any set S of vertices leaves at most S connected components: c(G-S) ≤ S . Deleting many vertices and counting components that shatter is the fastest way to prove a graph is NOT Hamiltonian.

The sum of all vertex degrees equals twice the number of edges — so the number of odd-degree vertices is always even, and many "does this graph exist?" questions collapse to one parity/counting check.

A consistent set is satisfiable by some valuation; a maximal consistent one decides every proposition, and Lindenbaum's lemma says every consistent set extends to one.

When each position independently contributes an odd value with probability 1/2, exactly half of all configurations have an even total — so the count is simply (total)/2.

To split distinct objects into unlabeled groups, start from the labeled multinomial count, then divide by j! for every block of j same-size groups — because permuting equal-size groups gives the same partition.

Composition distributes fully over UNION (both sides, always equality), but only ONE-WAY (subset, not equality) over intersection and difference — because it is built from an existential quantifier.

When each iteration replaces every segment by k copies scaled by factor r, the total length is multiplied by kr each step — so it grows geometrically as (kr)^n.

To add up every number formed by permuting a digit set, exploit symmetry: each digit lands in each position equally often, so sum once per position and weight by place value.

A sum of products of binomials whose lower indices add to a constant collapses to a single binomial: the inner indices telescope into one combined choose.

Consistency = having a model. The intersection of two consistent theories is always consistent, but their union can be inconsistent.

When a count splits by one free parameter d and equals a linear formula in d, total it with the arithmetic-series sum instead of listing cases — the running counts form an arithmetic progression you add in one stroke.

Sweep a linear (chain-like) graph left to right; the only state that crosses each cut is whether the boundary vertex is already matched, giving a small linear recurrence you solve like a Fibonacci.

Count relations by splitting the n^2 pairs into independent diagonal loops and off-diagonal blocks, multiplying the choices each property allows. Handle 'not P' constraints by complementary counting: (all) minus (those with P).

Forbidding a length-2 pattern like '01' freezes the string into one rigid shape (a block of 1s then a block of 0s), so the count collapses to choosing a single boundary: n+1 strings. Recognize a union of A_i as 'contains the pattern somewhere', then count the complement.

An occurrence of a variable is bound when it lies inside the scope of a quantifier on that same variable, and free otherwise. Count occurrences, not names, and remember a quantifier's scope stops at its subformula.

Rewrite A -> B as not A or B, then distribute. A conjunction/disjunction in the CONSEQUENT splits cleanly; in the ANTECEDENT the connective FLIPS, so (P or Q) -> R becomes a conjunction.

A function f has a left inverse ( g∘ f=id ) exactly when it is injective, and a right inverse ( f∘ g=id ) exactly when it is surjective. So "is f invertible on one side?" is just a disguised injectivity/surjectivity question.

To count tuples of subsets (A,B,C,…) of an n -set that satisfy a membership condition, decide each element's fate independently: count the legal membership patterns for one element, then raise that number to the power n .

To pick r objects from groups while taking at least one from each, hand one slot to every group up front, then split into cases on how the few leftover slots are distributed — usually a tiny, forced casework.

Symmetric closes every pair under swapping; antisymmetric forbids two-way arrows between distinct points. The only relations that are both are subsets of the diagonal I = (x,x) .

Vertex connectivity, edge connectivity, and minimum degree obey κ(G)≤λ(G)≤δ(G) ; Menger's theorem recasts connectivity as a max number of disjoint paths, and cubic graphs force κ=λ .

To average a permutation statistic over all of S_n , write it as a sum of indicators and use linearity of expectation — one object at a time.

Treat the curves as a planar graph and apply Euler's formula r = E - V + 1 + C: count intersection points (V) and arcs (E), then read off the number of regions.

Decidable = an algorithm always halts with the right yes/no; recursively enumerable (r.e.) = halts only on the YES-instances. Every decidable set is r.e., but not conversely — and the gap is exactly where logic problems live.

A base of a set of propositions Γ is a subset that proves all of Γ yet has no redundant member — a minimal generating set for the deductive closure of Γ .

A monotone path that takes a right-steps and b up-steps can be arranged in C(a+b, b) ways; to force a path through a checkpoint, count each leg separately and multiply.

The path Ramsey number R(P_m,P_n) — the least N so every red/blue coloring of K_N has a red P_m or blue P_n — has the closed form R(P_m,P_n)=m+⌊ n/2⌋-1 for m≥ n≥ 2 ; e.g. R(P_4,P_4)=5 .

A function defined by recursion on a formula's parse tree is pinned down by structural induction; when each connective contributes a distinct prime factor, unique factorization reads back every connective count from the single value f(A).

To turn an n-element universe into a structure you interpret each symbol independently and multiply: a k-ary relation gives 2^(n^k) choices, a k-ary function gives n^(n^k), and a constant gives n.

The transitive closure R^(+) is the smallest transitive relation containing R : it adds (x,y) whenever a directed path of length ≥ 1 runs from x to y .

Each finite ordinal is the set of all smaller ordinals, so n= 0,1,…,n-1 ; inside an iterated power set P^k(∅) only finitely many subsets happen to be exactly such ordinals.