[OFFICIAL] Basic Math/Combinatorics Problems

Hi all,

Let’s have discussion about generic questions related to combinatorics, probability, expectation, etc. This can be run in parallel with the current weekly problem sets, since improving in Math is a long process. (Avoid using a computer to try to solve these questions, you should aim to make a closed form formula for these questions)

So I am uploading some questions here, if you have any good questions of similar taste in mind do share them here :slight_smile:

We will first do some easier combinatorics questions, later on we can move to expectation, probability, recurrences, etc.

Incase you think you don’t have enough background in probability/combinatorics then refer to this place it is a good resource with good theory + good problems: Brilliant.org discrete math section

1a. Given a 2d grid how many ways are there to go from (0,0) (bottom left corner) to (4,6) (top right corner) given you are allowed to move only right and up?
1b. Count the number of ways to go from (0,0) to (5,5) when you allowed to move right and up. But you are also allowed to move one step left at most once ?

Solution

1a. Think of going right as R and going up as U. Then your path is basically a 10 character string of 4Rs and 6Us. Say your string starts with “RUU”, then it means first step take a right then take two ups and so on. So how many ways are there to go from (0, 0) to (4, 6)? It is equal to number of ways to re-arrange the 4Rs and 6Us in 10 dashes, i.e C(10, 4).

1b. TBA

2a. Number of palindromes using [a-z] of length exactly 7?
2b. How about for general length = N?
2c. How many recursively palindromic binary strings are there of length N? (A string “s” of length N is recursively palindromic is “s” is a palindrome and the first half of “s”, i.e from s[0] to s[N/2 - 1] is also recursively palindrome). For example for N = 5, there are four such strings {00000, 00100, 11011, 11111}, so answer is 4.

Solution

2a. Length is 7 so treat it as 7 dashes. The first 3 dashes fix the characters for the last 3 dashes as well and the middle dash can be anything. So answer is 26^4.

2b. For general N, extend this idea to 26^{\lceil \frac{N}{2} \rceil}. This is ceiling function, because for odd N, the middle dash provides extra 26 options, but for even there is no such middle dash.

2c. TBA

3a. Number of factors of 840 (including 1 and 840 itself)?
3b. Sum of all the factors of 840 (including 1 and 840 itself)?
3c. Number of factors and sum of factors for a generic N?

Solution

3c. Explaining the generalised version, can extend it for specific N = 840.

Let N = p_1^{k_1} \times p_2^{k_2} \times \dots = \prod_{i = 1}^{m}p_i^{k_i}, where each p_i is a unique prime number and k_i > 0 and m denotes the number of distinct prime factors of N, i.e this representation is the prime factorisation of N.

Now using this, you can see that the number of factors is (k_1 + 1) \times (k_2 + 1) \times \dots = \prod_{i = 1}^{m}(k_i + 1)
Proof: Your factor must be have its prime factorisation as a “subset” of the prime factorisation of N, i.e let K be a factor of N and its prime factorisation be p_1^{q_1}\times p_2^{q_2} \dots p_m^{q_m}, then q_i \leq k_i, \forall i \in [1, m].

Now each of the prime has to come lesser of equal number of times than it comes in N. So for p_1 how many possibilities do we have? We have p_1^0, p_1^1, \dots, p_1^{k_1}, i.e (k_1 + 1) possibilities. Similarly for a general p_i we have (k_i + 1) possibilities. Since each prime is independent for us, therefore answer is $\prod_{i = 1}^{m}(k_i + 1).

Sum of factors = (p_1^0 + p_1^1 + p_1^2 + \dots + p_1^{k_1}) \times (p_2^0 + p_2^1 + \dots + p_2^{k_2}) \times \dots = \prod_{i = 1}^{m}(\sum_{j = 1}^{k_i}(p_i^j)) = \prod_{i = 1}^{m}\frac{p_i^{k_i + 1} - 1}{p_i - 1}

Proof: Think of the polynomial (p_1^0 + p_1^1 + p_1^2 + \dots + p_1^{k_1}) \times (p_2^0 + p_2^1 + \dots + p_2^{k_2}) \times \dots = \prod_{i = 1}^{m}(\sum_{j = 1}^{k_i}(p_i^j)). Then try to actually manually work out each term of this expression. Notice that each term will be of the form p_1^{a_1} \times p_2^{a_2} \times \dots \times p_m^{a_m}, where this term is actually one of the factors of N. Also notice that each factor will come at least once and not be duplicated, i.e it will come exactly once. What this means is that that all the terms of this expression are all the factors. And all the terms are under addition, so they are giving us the same only. That is why the expression is equal to the sum of all the factors (including 1 and N)

4a. Given x + y + z = 10, x >= 0, y >= 0 and z >= 0, how many integer solutions, i.e triplets of integer (x, y, z)'s are there satisfying the above system of equations?
4b. How about x + y + z = 10, x >= 1, y >= 2 and z >= 3. Now how many ?

Solution

4a. Think of forming 10 as 10 stones and x, y, z as 2 sticks. So you have 10 stones and 2 sticks and you want to put these sticks in between these 10 stones which are present in a straight line. x will be equal to the number of stones between the start and the first stick, y will be the number of stones between first and second stick and z will the be the number of stones between the second stick and the end. Notice that solving number of non-negative solutions to x + y + z = 10 is now equal to the number of ways we can put these 2 sticks. So we have 10 + 2 = 12 dashes and we want to put these 2 sticks in between, i.e C(12, 2).

4b. TBA

I hope to add more questions as and when I feel we can move to harder questions.

Feel free to have an attempt at these questions and share you solutions/explanations in the comment section below :slight_smile:

Update 1: I saw a good response and will be working on adding more problems soon. Meanwhile I have added solutions to some of the parts. Please, please dont look at those solutions immediately after reading the question. Also TBA = To Be Announced.

24 Likes

i have formed the formula for 1 a …that is (m+n) C n . where m = row no. n = column no.
i got this formula by doing these steps
step 1 : we can calculate no.of ways to [ i, j] just by summing no. of ways to [i-1, j] and no.of ways to [i, j-1] (becoz to go to [i, j] from these two points we have only one way which is right and up move)
step 2: the first column and first raw will be filled by 1 only
when i filled the grid i found out that the diagonal no. are binomial coefficient (diagonal with 1 as end points)(no in pascal triangle)
and found the above formula.

1 Like

@sidhant007 in 1b:
in a way to reach from (0,0) to (5,5) can we visit a coordinate more than once?

and can u provide the link to the this question so that i can test my solution?

4a and 4b can be done by using formula n+r-1©r-1 formula

where n = value in RHS.
and r = number of variables

for 4a->

10+3-1©3-1 = 12©2 = 66

for 4b->

we just make RHS value of inequation to 0;
x-1>=0 , y-2>=0 , z-3>=0;

NOW

x-1+y-2+z-3=10
x+y+z = 4;

now the same formula as in (4a)

4+3-1©3-1 = 15

Used the simple terms to explain the problem,

popular formula

C(n+r-1,r-1)

2 Likes

For the :
1a and 1b approach is the same !!
We have to go from (x, y) to (a, b) then number of moves will be:
(n+m)Cn where n = abs(a -x) and m = abs(b - y)
2a: 26 2626*26
2b: power(26, ceil(num/2))

1 Like

Ofcourse!

Intiution behind problem 4.
4.a) Think that we have laid down 10 balls in a row and we want to partition these balls in 3 distinct bins. How to do that ? Not so intuitive use 2 sticks and place them somewhere in the row of balls. Profit : Now you can easily change the position of those sticks across the balls’ row and count different combinations that can occur or in problems’ terms integer solutions for x, y and z. How to find the total ways to partition these balls into 3 bins ? Easy just choose the positions of the two sticks and the task is done. Solution: (10 + no_sticks_required)choose(no_sticks_required)

1 Like

Intuition behind Problem 1a:
Notation : # --> Number of
Want to go from (0, 0) to (4, 6). Let’s say that each right move is defined as “R” and each up move is defined as “U”. A possible solution is UUUUUURRRR or RURUUURRUU. So see the pattern that #U’s + #R’s == 10. Now the problem can be formulated as choosing 6U’s or 4R’s out of string of len 10. Formula (#U’s needed + #R’s needed)choose(#U’s needed).

For 2a. we can go about the question like this.
visualize the question as blank spaces for each characters like if we take the N in the question is 7. So the blank spaces would be like :-> _ _ _ _ _ _ _ so for the 1 st space it will have 26 choices for us to choose from and its corresponding character (the mirror image) will have to be the same character to make the word palindrome. And the question doesn’t say anything about using a character only once so we will have the answer as 26 * 26 * 26 * 26 * 1 * 1 * 1 (the 4 th ‘26’ is there cause it is at the middle and it wouldn’t affect the word being palindrome.

As for generalizing the solution 2.b we can write it as 26 * (ceil(N/2) ). Cause the for any odd number it will be the same as i have explained above and for even numbers the word will always be divided into two equal parts so the ceil() function wouldn’t matter anyway. Its basically there to handle the odd cases.

Thank You, for reading hope it helped someone.

Problem 3:
Factorise N into prime factors and then number of factors is the product of all nums that sits in the powers. The sum is the product of Gp of each prime pi from 0-to-Ki.

1
a) nCr(10, 4) = nCr(10, 6)
b) For (5,5) ans is 5 * nCr(12, 7) For general (n, m), ans is n * nCr(n+m+2, n+2).

2
a) 26^(3)
b) 26^((n+1)/2)
c) 2^(__builtin_popcountll(n))

3 840 = 2^3 * 3 * 5 * 7
a) No. of factors = (3 + 1) * (1 + 1) * (1 + 1) * (1 + 1) => 4 * 2 * 2 * 2 => 32
b) Sum of factors = (1 + 2 + 2^2 + 2^3) * (1 + 3) * (1 + 5) * (1 + 7) => 15 * 4 * 6 * 8 => 2880
c) No. of factors of N = p1^x1 * p2^x2 * … * pn^xn => (x1+1)(x2+1)…*(xn+1)
Sum of factors of N = (1 + p1^1 + p1^2 + p1^x1) * … * (1 + pn^1 + pn^2 + pn^xn) => Each term can be computed using G.P
4)
a) nCr(12, 2) = nCr(12, 10)
b) nCr(6, 2) = nCr(6, 4)

1 Like

DISCRETE MATHS Guys you can check this channel out. Its free and very well explained. Many topics of discrete maths which are required in CP sometimes are covered there.
Hope this helps!

2 Likes

For 2 a) I think it should be 26^(4).

Can you add this grid problem?
https://hack.codingblocks.com/app/dcb/1271