I found a problem that looked interesting, so I tried to solve it.

problem

There are $ N $ cards, and $ A_i $ is written on the $ i $ th card.
Mr. T pulls out $ M $ sheets from this at the same time. How many pairs of numbers are written on the removed card?
However, it does not distinguish between pairs that are just swapped, such as $ (1,2) $ and $ (2,1) $.

For example, consider the case of $ N = 5 $, $ M = 2 $, $ \ {A \} = \ {1,2,2,3,4 \} $. In this case, $ 7 $ of $ (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,4) $ There is a pair of.

I'm not afraid of counting anymore ~ 35 selections of competition pro counting problems ~ --Qiita Some problems have been modified.

The person who writes this article

The person writing this article has no experience in competitive programming. I don't know how to be a competitive professional, so please take a good look at it.

Prerequisite knowledge

Number of grid paths

Consider such a grid-like path.

If you can only go to the right or up, the number of routes from $ P $ to $ Q $ is

{}_{n+m} \mathrm{C} _m

is.

Calculate the number of routes for each step

Due to the problem of the number of grid paths mentioned above, the horizontal axis is $ p $ and the vertical axis is $ q $, and the number of paths to a certain point $ (p, q) $ is $ (p-1, q) $. And the number of routes to $ (p, q-1) $.

Taking advantage of this property, the distance [^ 1] from $ P $ is increased by $ 1 $. When you reach the end, you will get the value you want. Let's check with the grid of $ 4 \ times 3 $.

[^ 1]: The distance here is the length of the nearest intersection from the intersection of the grid as 1.

It turns out that the number of routes in the $ 4 \ times 3 $ grid is 35. This result matches $ {} _7 \ mathrm {C} _3 = 35 $.

Grid deformation

Such a grid will appear in the following sections. The number of combinations does not change, only the vertical axis is slanted.

Algorithm of the subject

There are $ N $ cards, and $ A_i $ is written on the $ i $ th card.
Mr. T pulls out $ M $ sheets from this at the same time. How many pairs of numbers are written on the removed card?
However, it does not distinguish between pairs that are just swapped, such as $ (1,2) $ and $ (2,1) $.

Consider the case of $ N = 7 $, $ M = 4 $, $ \ {A \} = \ {1,2,2,3,3,3,4 \} $.

Creating a grid

First, create the following grid.

Write the numbers contained in $ A $ on the horizontal axis of the grid. If the same number is included, write it consecutively. The solid black line indicates whether to use the numbers written below. Going to the upper right means using that number, and going to the right side means not using that number.

For example

The pink path represents selecting $ (1, 2, 3, 4) $.

Similarly

Means to select $ (2, 2, 3, 3) $.

Duplicate combination

in this way,

When

Both represent selecting $ (2, 3, 3, 4) $, and there are multiple routes for a combination.

Avoid duplicate combinations

Change the route so that there is one route for one combination. When selecting a number, change to the route ** If there is the same number, select all the same numbers to the right of the selected number **. This allows you to eliminate duplicate combinations.

The light blue line is the deleted route, and the red is the added route. If you select $ 2 $ on the left, select $ 2 $ on the right as well. Similarly, if you select the leftmost $ 3 $, select the remaining two $ 3 $, and if you select the middle $ 3 $, select the right $ 3 $.

As a result, the only routes to select $ (2, 3, 3, 4) $ are as follows.

Enumeration

Count according to the created route.

By this operation, it turns out that the number of selecting 4 from $ \ {A \} = \ {1,2,2,3,3,3,4 \} $ is $ 11 $. It was.

How to select duplicate numbers

Now, pay attention to the part shown in red.

This number is the sum of the parts enclosed in orange.

Similarly, the part shown in red in the figure below is the sum of the parts surrounded by orange.

In a normal grid, the number of routes to the point $ (p, q) $ is the sum of the number of routes to $ (p-1, q) $ and the number of routes to $ (p, q-1) $. did.

Similarly, if there are two identical numbers, the number of routes to $ (p, q) $ is $ (p-2, q) $, $ (p-1, q-1) $, $ (p, q). -2) $ It is the sum of the number of routes.

Similarly, if there are three identical numbers, the number of routes to $ (p, q) $ is $ (p-3, q) $, $ (p-2, q-1) $, $ (p-1). , p-2) $, $ (p, q-3) $ The number of routes is added.

You can see that the route map can be rewritten as follows.

Enumeration (again)

Count again with the rewritten route.

So far, we have seen a concrete example of an algorithm that selects $ M $ cards from $ N $ cards that contain duplicate numbers.

algorithm

Generalize the above algorithm.

-$ A $ represents a set of cards --The number of routes to the $ point (p, q) $ is represented by $ route (p, q) $. $ route (0, 0) = 1 $ --The distance from the origin is represented by $ step $. The initial value of step is $ 0 $

Repeat the following until $ A $ is empty
Extract all one kind of number $ a $ from $ A $ and delete it from $ A $. Let $ c $ be how many $ a $ are
Add $ c $ to $ step $
For an integer $ (p, q) $ that satisfies $ p + q = step \ (0 \ leqq p \ leqq N-M, 0 \ leqq q \ leqq M) $ $ route (p, q) = route (p --c, q) + route (p --c + 1, q -1) + route (p --c + 2, q --2) + ... + route (p) --1, q- (c -1)) + route (p, q --c) $
$ route (N-M, M) $ is the number you want.

Algorithm modification

The above algorithm is $ M $, such as $ N = 7 $, $ M = 2 $, $ \ {A \} = \ {1,2,2,3,3,3,4 \} $ It doesn't work if you have numbers with higher multiplicity (this time there are 3 $ 3 $). If there are more than $ M $ of duplicate numbers, you need to reduce the multiplicity to $ M $ in advance.

Algorithm improvements

Sort by the degree of duplication of numbers

Arrange the numbers by multiplicity. Write the number that appears only once on the far left.

The number when it appears only once can be calculated.

(This is why $ step $ does not start at $ 0 $ in the linked program.)

In the case of a simple lattice, the coefficient when $ (x + y) ^ n $ is expanded appears on the diagonal line (Pascal's triangle / binomial theorem).

Similarly, there is regularity when two identical numbers appear, but I haven't generalized them well yet (I). The number of two appearing is related to the coefficient of $ (x ^ 2 + x + 1) ^ n $. This property can be used to further improve the algorithm.

code

I implemented the above algorithm in Python (version 3.7). combination.count_uniq_combination_lattice

I check if the program is correct by checking if it is the same as this straightforward answer. combination. count_uniq_combination_simple

Reference link

[Elementary Number Theory / Pascal's Triangle-Wikibooks](https://ja.wikibooks.org/wiki/%E5%88%9D%E7%AD%89%E6%95%B4%E6%95%B0% E8% AB% 96 /% E3% 83% 91% E3% 82% B9% E3% 82% AB% E3% 83% AB% E3% 81% AE% E4% B8% 89% E8% A7% 92% E5 % BD% A2)

Afterword

When I first saw the problem, I thought, "I don't know where to start ..." Now that I've written the commentary, I'm starting to think, "Oh, this is surprisingly simple, and it may be common sense in the professional competition world." Perhaps there is already a similar commentary article, but I will publish it because it was good for my own organization.

[Competition Pro] Solve the number of M cards taken out from N cards using a route [Explanation in the figure]