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

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

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