Counting and combinatorics

Many problems ask you to count arrangements or pairs with a given property. Listing every candidate takes exponential time on anything but the smallest input. Counting the outcomes directly, without ever listing them, is what makes these problems solvable at senior-level constraints.

Counting instead of enumerating

Say you want to count unordered pairs of positions i < j where arr[i] < arr[j]. Checking every one of the $\binom{N}{2}$ pairs directly costs $O(N^2)$. A faster approach asks a narrower question at each position: as you reach position j, how many earlier positions hold a value smaller than arr[j]?

1import sys2from bisect import bisect_left3
4
5def main() -> None:6    input_data = sys.stdin.read().split()7    n = int(input_data[0])8    arr = list(map(int, input_data[1:n + 1]))9
10    count = 011    sorted_values = []12
13    for i in range(n):14        pos = bisect_left(sorted_values, arr[i])15        count += pos16        sorted_values.insert(pos, arr[i])17
18    print(count)19
20
21if __name__ == "__main__":22    main()

5
2 1 4 3 5

8

Walk through [2, 1, 4, 3, 5]. At position 0, insert 2 into an empty sorted list; nothing is smaller yet. At position 1, insert 1; still nothing smaller before it. At position 2, insert 4; the values already inserted, [1, 2], are both smaller, so this position contributes 2. At position 3, insert 3; the same two values [1, 2] are smaller (4 is already in the list, but this position never compares against itself), contributing 2 more. At position 4, insert 5; all four earlier values are smaller, contributing 4. The running total is 0 + 0 + 2 + 2 + 4 = 8, which matches the program's output. bisect_left finds how many of the values inserted so far are smaller than the current one, and insort keeps the list sorted so the next lookup stays valid. Both run in O(log n), for $O(n \log n)$ overall instead of $O(n^2)$.

Complementary counting

Sometimes the outcomes you want are hard to count directly, but the outcomes you do not want are easy. Count everything, then subtract the easy, unwanted case.

1import math2import sys3
4
5def main() -> None:6    input_data = sys.stdin.read().split()7    n = int(input_data[0])8    arr = list(map(int, input_data[1:n + 1]))9
10    total_triplets = math.comb(n, 3)11    bad_count = 012
13    for i in range(n):14        for j in range(i + 1, n):15            if arr[i] >= arr[j]:16                bad_count += n - j - 117
18    print(total_triplets - bad_count)19
20
21if __name__ == "__main__":22    main()

5
1 2 3 4 5

10

Here the property under test is whether the first two positions of a triplet are in increasing order; what the third position holds does not matter. For [1, 2, 3, 4, 5], every earlier value is smaller than every later one, so no pair i < j is out of order. All $\binom{5}{3} = 10$ triplets qualify, which is what the program prints. Take a less orderly array such as [2, 1, 4, 3, 5] instead. The pair at positions 0 and 1 is out of order, since arr[0] = 2 is not smaller than arr[1] = 1; with j = 1, that contributes 5 - 1 - 1 = 3 disqualified triplets, one for each k in {2, 3, 4}. The pair at positions 2 and 3 is also out of order, since arr[2] = 4 is not smaller than arr[3] = 3; with j = 3, that contributes 5 - 3 - 1 = 1 more. Four triplets are disqualified out of ten, leaving six. Counting the four disqualified triplets directly is a simple double loop; counting the six qualifying ones directly would need a three-way comparison at every step.

Binomial coefficients for splitting items into groups

When you divide a set of labeled items into groups of fixed sizes, the number of ways to do it is a product of binomial coefficients: choose the first group out of everything, choose the second group out of what remains, and so on.

1import math2import sys3
4
5def main() -> None:6    input_data = sys.stdin.read().split()7    k = int(input_data[0])8    groups = list(map(int, input_data[1:1 + k]))9
10    result = 111    total = sum(groups)12    used = 013
14    for g in groups:15        result *= math.comb(total - used, g)16        used += g17
18    print(result)19
20
21if __name__ == "__main__":22    main()

3
3 4 3

4200

Out of 10 items, choose 3 for the first group: $\binom{10}{3} = 120$ ways. Out of the 7 that remain, choose 4 for the second group: $\binom{7}{4} = 35$ ways. The last 3 items form the final group in exactly $\binom{3}{3} = 1$ way. Multiplying gives 120 * 35 * 1 = 4200, which matches the program's output. Python's math.comb, available in Python 3.8, computes each coefficient directly, without the overflow risk of computing large factorials by hand.

Two pointers over a sliding constraint

Some counting problems ask for pairs or ranges where a constraint holds only within a bounded difference. Sort the values first, then let two pointers sweep the sorted array together instead of comparing every pair.

1import sys2
3
4def main() -> None:5    input_data = sys.stdin.read().split()6    n = int(input_data[0])7    k = int(input_data[1])8    arr = list(map(int, input_data[2:2 + n]))9
10    arr.sort()11    count = 012    left = 013
14    for right in range(n):15        while left < right and arr[right] - arr[left] > k:16            left += 117
18        count += right - left19
20    print(count)21
22
23if __name__ == "__main__":24    main()

5 3
1 2 5 6 9

4

With [1, 2, 5, 6, 9] sorted and K = 3, left starts at 0. As right advances, the loop moves left forward whenever the gap between arr[right] and arr[left] exceeds K, then adds right - left, the count of valid partners for this right. Because the array is sorted, once a value becomes too far from arr[right] to satisfy the constraint, every value before it is too far as well, so left only ever moves forward. That is what lets the two pointers sweep the array once for a total of O(n) instead of comparing every pair.

Why these techniques work, and where they stop working

Counting without enumeration works when the outcome has a structure that a data structure or a formula can summarize, instead of needing to check every candidate one at a time. The pair-counting example works because "how many earlier values are smaller" is exactly what a sorted list answers on every insertion. Complementary counting works when the property you actually want is hard to check directly but its opposite has an easy structure, such as the fixed-order pair check above.

The two-pointer technique depends entirely on the array being sorted, or on some other property that is monotonic in the same direction as the loop. If left were allowed to move backward as right increases, correctness would break, since some valid pairs would never be counted. Confirm that the quantity you are bounding only grows in one direction before reaching for two pointers.

Binomial-coefficient counting depends on knowing whether the groups you are filling are distinguishable. $\binom{10}{3} \times \binom{7}{4}$ assumes group A and group B are different from each other, so swapping their contents produces a different outcome. If the groups are interchangeable, the same product overcounts, and you need to divide out the number of ways to permute the groups among themselves.

Common mistakes

A frequent mistake is losing track of what "bad" means partway through a complementary count. If a triplet's property depends on more than one pair of positions, make sure every disqualifying condition is captured exactly once, so nothing is subtracted twice and nothing is missed.

Another mistake is applying a two-pointer sweep to data that was never sorted or never had the needed monotonic property in the first place. Check that sorting does not change what the problem is asking, since some counting problems care about the original index order and cannot be sorted away.

A third mistake is choosing the wrong binomial-coefficient formula for a partition. Confirm whether the problem's groups are labeled or interchangeable before multiplying coefficients together, and adjust with a division by a factorial of group counts if the groups are interchangeable.

Recap

Counting a structured outcome directly, rather than listing every candidate, turns exponential enumeration into a polynomial-time computation. Complementary counting flips a hard property into an easy one to subtract. Binomial coefficients count group splits. Two pointers count pairs under a sliding constraint, as long as the underlying order is monotonic.