Recent News IntroductionProblems in competitive programming which involve Mathematics are are usually about number theory, or geometry. If you know number theory, that increases your ammo heavily in solving a lot of tougher problems, and helps you in getting a strong hold on a lot of other problems, too.Problems in competitive programming require insight, so just knowing some topics is not enough at all. All of the problems requires more or less math tough. For instance, solving large systems of equations and approximating solutions to differential equations.Set TheoryBefore we proceed, let us get through the some common set operations.Q.) What is a Set?-In mathematics, a set is a collection of distinct objects, considered as an object in its own right.For example, the numbers 2, 4, and 6 are distinct objects when considered separately, but when they are considered collectively they form a single set of size three, written {2,4,6}.Sets are one of the most fundamental concepts in mathematics.A set of polygons in a Venn diagram.SubsetsIf every member of setAis also a member of setB, thenAis said to be asubsetofB, writtenA ⊆ B(also pronounced A is contained in B).Equivalently, we can writeB ⊇ A, read as B is asupersetof A, B includes A, or B contains A.The relationship between sets established by ⊆ is calledinclusionorcontainment.If A is a subset of, but not equal to, B, then A is called a proper subset of B, written A ⊊ B (Ais aproper subsetofB) or B ⊋ A (B is aproper supersetof A).Example:- {1, 3} ⊆ {1, 2, 3, 4}.- {1, 2, 3, 4} ⊆ {1, 2, 3, 4}.The empty set (denoted by the symbol ∅) is a subset of every set and every set is a subset of itself:- ∅ ⊆ A.- A ⊆ A.A is subset of B.Basic operations on SetsThere are several fundamental operations for constructing new sets from given sets.Unions:Two sets can be “added” together. The union of A and B, denoted by A ∪ B, is the set of all things that are members of either A or B.Examples:-{1, 2} ∪ {1, 2} = {1, 2}.-{1, 2} ∪ {2, 3} = {1, 2, 3}.-{1, 2, 3} ∪ {3, 4, 5} = {1, 2, 3, 4, 5}Theunionof A and B, denoted A ∪ B.Some basic properties of unions:-A ∪ B = B ∪ A.-A ∪ (B ∪ C) = (A ∪ B) ∪ C.-A ⊆ (A ∪ B).-A ∪ A = A.-A ∪ ∅ = A.-A ⊆ B if and only if A ∪ B = B.Intersections:A new set can also be constructed by determining which members two sets have “in common”. The intersection of A and B, denoted by A ∩ B, is the set of all things that are members of both A and B. If A ∩ B = ∅, then A and B are said to be disjoint.Examples:-{1, 2} ∩ {1, 2} = {1, 2}.-{1, 2} ∩ {2, 3} = {2}.Theintersectionof A and B, denoted A ∩ B.Some basic properties of intersections:-A ∩ B = B ∩ A.-A ∩ (B ∩ C) = (A ∩ B) ∩ C.-A ∩ B ⊆ A.-A ∩ A = A.-A ∩ ∅ = ∅.-A ⊆ B if and only if A ∩ B = A.Complements:
Two sets can also be “subtracted”. The relative complement of B in A (also called the set-theoretic difference of A and B), denoted by A B (or A − B), is the set of all elements that are members of A but not members of B. Note that it is valid to “subtract” members of a set that are not in the set, such as removing the element green from the set {1, 2, 3}; doing so has no effect.In certain settings all sets under discussion are considered to be subsets of a given universal set U. In such cases, U A is called the absolute complement or simply complement of A, and is denoted by A′.Examples:-{1, 2} {1, 2} = ∅.-{1, 2, 3, 4} {1, 3} = {2, 4}.-If U is the set of integers, E is the set of even integers, and O is the set of odd integers, then U E = E′ = O.Therelative complementof B in A.Thecomplementof A in U.Some basic properties of complements:-A B ≠ B A for A ≠ B.-A ∪ A′ = U.-A ∩ A′ = ∅.-(A′)′ = A.-A A = ∅.-A B = A ∩ B′.-U′ = ∅ and ∅′ = U.Basics of CombinatoricsNOTE:here denotes the number of elements in Set.The basic rules of combinatorics one must remember are:The Rule of Product:The product rule states that if there arepossibilities from setand, then there areways to combine one fromand one from.The Rule of Sum:The sum rule states that if there arepossibilities from setandpossibilities from set, then there areways for eitheroroccur assuming the elements ofandare distinct.Inclusion-Exclusion Formula: (also know as the sieve principle):Generalising the above formula, we get:The reason this works is that summing the sets double counts certain possibilities, namely, those occurring in both sets.Double counting is a slippery aspect of combinatorics, which can make it difficult to solve problems via inclusion-exclusion.These rules can be used for a finite collections of sets.Basics of PermutationPermutation of Distinct Objects:Suppose we have to permutekobjects out ofndistinct objects, then the total number of permutations is given byP = n * (n – 1) * (n – 2) * … * (n – k + 1)which when simplified gives usP = n! / (n – k)!wheren! = n * (n – 1) * (n – 2) * … * 2 * 1.Permutation with Repetition:If we have total n objects, where we have n1 objects of type 1, n2 objects of type 2 and so on upto k.Thusn1+n2+…+nk=n. So the number of permutations of these objects is given by:Combinatorial ObjectsA bijection is a one-to-one mapping between the elements of one set and the elements of another. Counting the size of one of the sets automatically gives you the size of the other set.
Exploiting bijections requires us to have a repertoire of sets which we know how to count, so we can map other objects to them.Combinations without repetition:In combinations we choose a set of elements (rather than an arrangement, as in permutations) so the order doesn’t matter. The number of different k-element subsets (when each element can be chosen only once) of n-element set is:Combinations with repetition:Let’s say we choose k elements from an n-element set, the order doesn’t matter and each element can be chosen more than once. In that case, the number of different combinations is:It is useful to know thatis also the number of integer solutions to this equation:Binary VectorsAccordingly, some knowledge of the basic combinatorial properties of binary vectors is rather important. Let’s have a look at some simple things associated with them:Number of binary vectors of lengthn:2n.Number of binary vectors of lengthnand withk‘1’ issince we just choosekpositions for our ‘1’s.The number of ordered pairs (a, b) of binary vectors, such that the distance between them (k) can be calculated as follows:.The distance between a and b is the number of components that differs in a and b.Recurrence RelationsRecurrence relations make it easy to count a variety of recursively defined structures. Recursively defined structures include trees, lists, well-formed formulae, and divide-and-conquer algorithms – so they lurk wherever computer scientists do.A recurrence relation is an equation which is defined in terms of itself. They are useful because many natural functions are easily expressed as recurrences:Polynomials:Exponentials:Weird but interesting functions otherwise hard to represent:It is often easy to find a recurrence as the answer to a counting problem. Solving the recurrence to get a nice closed form can be somewhat of an art, but as we shall see, computer programs can easily evaluate the value of a given recurrence even without the existence of a nice closed form.Binomial CoefficientsThe most important class of counting numbers are the binomial coefficients, wherecounts the number of ways to choosethings out ofpossibilities.Paths Across a Grid:How many ways are there to travel from the upper-left corner of angrid to the lower-right corner by walking only down and to the right? Every path must consist ofto the right. Every path with a different set of downward moves is distinct, so there aresuch sets/paths.Computation of binomial coefficients can sometimes cause arithmetic overflow in intermediate steps. So a more stable way to perform calculations is using the following formula:.Other Counting SequencesCatalan Numbers:
The recurrence and associated closed formCatalan Numbers and it’s uses.Eulerian Numbers: The Eulerian numberscount the number of permutations of lengthwith exactlyascending sequences or runs. A recurrence can be formulated by considering each permutationof 1,2,…,n-1. There are n places to insert element n, and each either splits an existing run of p or occurs immediately after the last element of an existing run, thus preserving the run count. Thus.Integer Partitions: An integer partition of n is an unordered set of positive integers which add up to n. For example, there are seven partitions of 5, namely, (5), (4, 1), (3, 2), (3, 1, 1), (2, 2, 1), (2, 1, 1, 1) and (1, 1, 1, 1, 1) .The easiest way to count them is to define a functionf(n,k)giving the number of integer partitions ofnwith largest part at mostk. In any acceptable partition the largest part either does or does not reach with limit, sof(n,k)=f(n-k,k)+f(n,k-1). The basic cases aref(1,1)=1andf(n,k)=0whenever k>n.Introduction to ProbabilitiesBasicsWorking with probabilities is much like conducting an experiment. Anoutcomeis the result of an experiment or other situation involving uncertainty. The set of all possible outcomes of a probability experiment is called asample space. Each possible result of such a study is represented by one and only one point in the sample space, which is usually denoted by S.Let’s consider the following experiments:Rolling a die once:
Sample space S = {1, 2, 3, 4, 5, 6}Tossing two coins: 