There is problem called D. Count the Arrays on Codeforces.
Array is set of elements. In this case, set can (and have to) contain one duplicate
I started learning combinatorics but I still can't solve it. Here's the formula I derived:
For first two conditions, I started with: $\binom{m}{n}$. There are n possible positions on which any element from 1 to m can be placed.
For the third condition, I made it: $\binom{m}{n-1} * \binom{n-1}{1}$ because we will have one fixed element which will be duplicate. I use $n$ and not $m$ because not all elements available from $m$ are included in $n$ available positions. The duplicate, as the word says, must be the same as some of included elements. Then I substract $1$ because due to 4-th condition, the element at index i will never have duplicate.
For the fourth condition, I have no idea. Due to this point I know that the first duplicated element will be before i-th element and the another after i-th. But how can I count only arrays that are ascending to some point and then descending? I see too many possibilites and can't derive formula for it.
Any idea? How would you approach this problem?
Best Answer
I got $$ (n-2)\binom{m}{n-1}2^{n-3} $$ The key idea is to make an observation as to the position of the numbers in the array and then count the possible number of arrays by thinking "algorithmically" in the steps involved in building each of said arrays.
This is similar to your approach - you will recognise some of the binomial coefficients in the ideas proposed. However, I find it important to understand how each component combines together to get the formula, which I do not immediately gather from the proposed approach and I hope may be evident in this one. I find it helpful to find an algorithmic procedure to generate precisely all arrays, and then develop a counting strategy based on it.
Observation: the repeated element's position
Suppose we have $A$ an array which satisfies all conditions, and fix $i$ the index as from which the coefficients become strictly decreasing and up to which the coefficients are strictly increasing.
Note at this point that if we think of the array as encoding the height of a landmass at each position then the landmass will look like a mountain with a single peak at $i$, as the numbers will be increasing at first until they reach a peak and then they will be decreasing.
With this intuition in mind, note that the repeated numbers cannot be besides each other: if they were then we would have a tie and there would not be a strict increment/decrement. Then both repeated numbers need to be one at each side of the peak.
Note also that the maximum necessarily corresponds to the peak and then it cannot be the repeated number. If it were, both maximums necessarily need to share the peak and we would once again have a tie.
Solution
We will first build an array with $n-2$ distinct numbers from the $m$ and then add the repeated elements in order to build each possible array. In more detail:
Any array will have $n-1$ distinct elements in some order from the $m$ elements, for which we will have $\binom{m}{n-1}$ ways of choosing them.
For any choice of $n-1$ elements, we may choose the repeated number from among them: this amounts to $n-2$ possible choices given the $n-1$ numbers as we exclude the biggest.
Now, having chosen $n-1$ numbers and the repeated number, we need to choose an ordering so that the array satisfies the given condition.
Then I propose the following: choose from the $n-1$ distinct numbers excluding the maximum and the repeated numbers which of them will go before the maximum, which we will add in increasing order, and which will go after, which we will add in decreasing order. Since for each of the $n-3$ numbers we have two choices, to add it before or after the maximum, and all choices are independent of each other, we get $2^{n-3}$ ways of choosing which numbers go before and which numbers go after.
Now we will have an array with $n-2$ elements, as we still have not placed the repeated numbers inside the array! Note that there is just one place to put them: one on each side of the maximum, as we deduced should happen in the observation.
Combining all steps in the procedure, we get: $$ \binom{m}{n-1} (n-2) 2^{n-3} = (n-2)\binom{m}{n-1}2^{n-3} $$ which is the proposed result.