ترکیبیات و شمارش
Combinatorics and Counting
مباحث ترکیبیات و اصول شمارش.
ریاضیات گسسته کنکور ارشد علوم کامپیوتر
کارتها · 29
When some elements are locked into specific slots, only permute the remaining free elements.
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) .
To keep restricted items apart, seat the unrestricted majority first, then drop the restricted items into the gaps between them.
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.
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 .
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.
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 ⌋ .
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.
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.
(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 .
Color the cells/vertices in a dependency order; each new one has k minus the number of already-colored neighbors choices, and you multiply.
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 .
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.