Tricks in counting problems
tags:competitive-programming
algorithm
incomplete
Outline
Introduction
Hello, in this blog, I’ll just be listing down certain tricks and insights which I encounter(ed) in counting problems. It’s going to be more of a personal archive for me, and less of an instructive tutorial. It will remain a work in progress probably until I stop doing competitive programming.
If this blog does end up reaching a state close to what I currently envision it to be, it will be somewhat hard to navigate since there will be a lot of independent content crammed next to each other. I recommend navigating through the “Outline” instead of manually scrolling if the blog is in such a state at the time of you reading this.
1. Pretend that elements are distinct
Idea (1)
Consider a problem which involves the following:
Maintain a set $S$ while performing the following updates:
Add some elements to $S$.
Remove some number of elements from $S$ and do something with these elements.
Finally, you have to find the total number of ways that this process could have been executed.
Let’s consider a specific example to illustrate the idea. You have a set $S$, an initially empty list $p$, and have to process queries are of the following form:
- Add $x$ elements of the same type to $S$, given that no element of this type has been added before.
- Remove $y$ (given that $y \leq \vert S \vert$) elements from $S$, order these $y$ removed elements in any manner, and append them to $p$.
Finally, you need to find the number of distinct generatable lists $p$.
Notation
- $S_i$ : the set $S$ after $i$ operations
- $t_i$ : type of the $i$'th query
- $x_i$ : number of elements to add in the $i$'th query
- $y_i$ : number of elements to remove in the $i$'th query
The answer is simply:
\[\frac{\prod_{i \mid t_i = 2} {\binom{\vert S_{i - 1}\vert}{y_i} \cdot y_i !}}{\prod_{i \mid t_i = 1} {x_i !}}\]It is not difficult to see why this is true. Consider what happens if we “pretend” for every type 1 query that all the elements inserted in it were distinct. This makes it trivial for us to compute the number of ways to perform a type 2 query, which would otherwise be difficult to compute.
Now, once we have computed the final (incorrect) answer, let’s “stop pretending” that type 1 queries involved distinct elements. For every type 1 query $i$, it’s easy to see that our pretense results in the answer increasing by a factor of $x_i!$. So, we just “fix” the answer by dividing it by $\prod_{i \mid t_i = 1} {x_i !}$.