
Introduction Combinatorial primitives The rule of sum The rule of product For example, if we have three towns  A, B and C  and there are 3 roads from A to B and 5 roads from B to C, then we can get from A to C through B in 3*5=15 different ways. These rules can be used for a finite collections of sets. Permutation without repetition When we choose k objects from nelement set in such a way that the order matters and each object can be chosen only once: For example, suppose we are planning the next 3 challenges and we have a set of 10 easy problems to choose from. We will only use one easy problem in each contest, so we can choose our problems in different ways. Permutation (variation) with repetition The number of possible choices of k objects from a set of n objects when order is important and one object can be chosen more than once: n^{k}
For example, if we have 10 different prizes that need to be divided among 5 people, we can do so in 5^{10} ways. Permutation with repetition The number of different permutations of n objects, where there are n_{1} indistinguishable objects of type 1, n_{2} indistinguishable objects of type 2,..., and n_{k} indistinguishable objects of type k (n_{1}+n_{2}+…+n_{k}=n), is: For example, if we have 97 coders and want to assign them to 5 rooms (rooms 14 have 20 coders in each, while the 5th room has 17), then there are possible ways to do it. 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 kelement subsets (when each element can be chosen only once) of nelement set is: For example, if we have 7 different colored balls, we can choose any 3 of them in different ways. Combination with repetition Let's say we choose k elements from an nelement set, the order doesn’t matter and each element can be chosen more than once. In that case, the number of different combinations is: For example, let's say we have 11 identical balls and 3 different pockets, and we need to calculate the number of different divisions of these balls to the pockets. There would be different combinations. It is useful to know that is also the number of integer solutions to this equation: Why? It's easy to prove. Consider a vector (1, 1, …, 1) consisting of (n+k1) ones, in which we want to substitute n1 ones for zeroes in such way that we'll get n groups of ones (some of which may be empty) and the number of ones in the i^{th} group will be the value of x_{i}: The sum of x_{i} will be k, because k ones are left after substitution. The Basics Binary vectors Some problems, and challenge problems are no exception, can be reformulated in terms of binary vectors. Accordingly, 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: 1. Number of binary vectors of length n: 2^{n}. 2. Number of binary vectors of length n and with k ‘1’ is We just choose k positions for our ‘1’s. 3. The number of ordered pairs (a, b) of binary vectors, such that the distance between them (k) can be calculated as follows: . Let a = (a_{1}, a_{2}, …a_{n}), b = (b_{1}, b_{2}, …b_{n}) and distance between them is k. Next, let’s look at the sequence of pairs (a_{1}, b_{1}), (a_{2}, b_{2}), … (a_{n}, b_{n}). There are exactly k indices i in which a_{i} ≠ b_{i}_{}. They can be (0,1) or (1,0), so there are 2 variants, and nk can be either (0,0) or (1,1), for another 2 variants. To calculate the answer we can choose k indices in which vectors differs in ways, then we choose components that differs in 2^{k} ways and components that are equal in 2^{nk} ways (all of which use the permutation with repetition formula), and in the end we just multiply all these numbers and get . Delving deeper This formula is a generalization of: There are many different problems that can be solved using the sieve principle, so let’s focus our attention on one of them. This problem is best known as “Derangements”. A derangement of the finite set X is a bijection from X into X that doesn’t have fixed points. A small example: For set X = {1, 2, 3} bijection {(1,1), (2,3), (3,2)} is not derangement, because of (1,1), but bijection {(1,2), (2,3), (3,1)} is derangement. So let’s turn back to the problem, the goal of which is to find the number of derangements of nelement set. We have X = {1, 2, 3,…, n}. Let:
In formula we have sums , in our case we’ll have , so let’s calculate them: (because there are exactly ielement subsets of X). Now we just put that result into the sieve principle’s formula: And now the last step, from we’ll have the answer: And the last remark: This problem may not look very practical for use in TopCoder problems, but the thinking behind it is rather important, and these ideas can be widely applied. Another interesting method in combinatorics  and one of my favorites, because of its elegance  is called method of paths (or trajectories). The main idea is to find a geometrical interpretation for the problem in which we should calculate the number of paths of a special type. More precisely, if we have two points A, B on a plane with integer coordinates, then we will operate only with the shortest paths between A and B that pass only through the lines of the integer grid and that can be done only in horizontal or vertical movements with length equal to 1. For example: All paths between A and B have the same length equal to n+m (where n is the difference between xcoordinates and m is the difference between ycoordinates). We can easily calculate the number of all the paths between A and B as follows: or .
Let’s solve a famous problem using this method. The goal is to find the number of Dyck words with a length of 2n. What is a Dyck word? It's a string consisting only of n X’s and n Y’s, and matching this criteria: each prefix of this string has more X’s than Y’s. For example, “XXYY” and “XYXY” are Dyck words, but “XYYX” and “YYXX” are not. Let’s start the calculation process. We are going to build a geometrical analog of this problem, so let’s consider paths that go from point A(0, 0) to point B(n, n) and do not cross segment AB, but can touch it (see examples for n=4). It is obvious that these two problems are equivalent; we can just build a bijection in such a way: step right  ‘X’, step up  ‘Y’. Here's the main idea of the solution: Find the number of paths from A to B that cross segment AB, and call them “incorrect”. If path is “incorrect” it has points on the segment CD, where C = (0, 1), D = (n1, n). Let E be the point nearest to A that belongs to CD (and to the path). Let’s symmetrize AE, part of our “incorrect” path with respect to the line CD. After this operation we’ll get a path from F = (1, 1) to B. It should be easy to see that, for each path from F to B, we can build only one “incorrect” path from A to B, so we’ve got a bijection. Thus, the number of “incorrect” paths from A to B is . Now we can easily get the answer, by subtracting the number of “incorrect” paths from all paths: This number is also known as n’s Catalan number: C_{n} is the number of Dyck words with length 2n. These numbers also appear in many other problems, for example, C_{n} counts the number of correct arrangements of n pairs of parentheses in the expression, and C_{n} is also the number of the possible triangulations of a polygon with (n+2) vertices, and so on. Using recurrence relations If you'd like to learn more, check out these tutorials: An Introduction to Recursion, Recursion, Part 2, and Dynamic Programming: From novice to advanced. Done reading? Let’s take a look at some examples. ChristmasTree (SRM 331 Division Two – Level Three): We’ll use DP to solve this  it may not be the best way to tackle this problem, but it’s the easiest to understand. Let cnt[lev][r][g][b] be the number of possible ways to decorate the first lev levels of tree using r red, g green and b blue baubles. To make a recurrent step calculating cnt[lev][r][g][b] we consider 3 variants: cnt[lev][r][g][b]= 1) we fill the last level with one color (red, green or blue), so just: = cnt [lev1][rlev][g][b]+ cnt[lev1][r][glev][b]+ cnt[lev1][r][g][blev]+ ; 2) if (lev%2 == 0) we fill the last level with two colors (red+green, green+blue or red+blue), then we calculate the number of possible decorations using the Permutation with repetition formula. We’ll get possible variants for each two colors, so just (cnt[lev1][rlev/2][glev/2][b]+...+cnt[lev1][r][glev/2][blev/2])+; 3) if (lev%3 == 0) we fill the last level with three colors and, again using the Permutation with repetition formula, we’ll get possible variants, so we’ll get: (all cnt[l][i][j][k] with negative indices are 0). DiceGames (SRM 349 Division One – Level Two): First we should do some preparation for the main part of the solution, by sorting sides array in increasing order and calculating only the formations where the numbers on the dice go in nondecreasing order. This preparation saves us from calculating the same formations several times (see SRM 349  Problem Set & Analysis for additional explanation). Now we will only need to build the recurrence relation, since the implementation is rather straightforward. Let ret[i][j] be the number of different formations of the first i dice, with the last dice equal to j (so , where n is the number of elements in sides). Now we can simply write the recurrence relation: The answer will be . Conclusion References:


Home 
About TopCoder 
Press Room 
Contact Us 
Careers 
Privacy 
Terms
Competitions  Cockpit 
Copyright TopCoder, Inc. 2001 