Let $m_1, m_2, \ldots, m_n$ be a collection of $n$ positive integers, not necessarily distinct. For any sequence of integers $A = (a_1, \ldots, a_n)$ and any permutation $w = w_1, \ldots, w_n$ of $m_1, \ldots, m_n$, define an $A$-inversion of $w$ to be a pair of entries $w_i, w_j$ with $i < j$ for which one of the following conditions holds: $a_i \ge w_i > w_j$ $w_j > a_i \ge w_i$, or $w_i > w_j > a_i$. Show that, for any two sequences of integers $A = (a_1, \ldots, a_n)$ and $B = (b_1, \ldots, b_n)$, and for any positive integer $k$, the number of permutations of $m_1, \ldots, m_n$ having exactly $k$ $A$-inversions is equal to the number of permutations of $m_1, \ldots, m_n$ having exactly $k$ $B$-inversions.
Problem
Source: USAMO #2
Tags: AMC, USA(J)MO, USAMO, 2017 USAMO, combinatorics, Hi
High
20.04.2017 02:16
Do you think proving trivial case where all m are distinct can salvage anything?
Shaddoll
20.04.2017 02:16
We proceed by induction. For $n=1$, there are obviously $0$ A-inversions regardless of $A$. Note that the number of A-inversions is the number of A-inversions involving $w_1$ plus the number of $A-a_1$ inversions(where $A-a_1$ is $A$ with the first element truncated and the other elements with indices shifted down by $1$). By inductive hypothesis, the number of ways to get $k$ inversions not involving the first element is the same for any $A-a_1$, so we can assume all the $a_i$s are equal.
Now, WLOG, let the distinct elements be $1$, $2$, ..., $x$(where each element has the corresponding multiplicity in the original set, ranked in order). Now, we claim that a cyclic shift(Shifting $1$ to $2$, $2$ to $3$, and so on, $x-1$ to $x$, and $x$ to $1$) preserves the number of permutations with $k$ normal inversions. This is clearly equivalent to the proving the problem for all $a_i$s are equal(too see why, we note that an A-inversion with all equal $a_i$ is a normal inversion where the comparison function becomes $x>y$ if $x\leq a_1 < y$ and otherwise stays normal. Then, notice that moving the $a_i$ past an integer is just a cyclic shift). We biject as follows:
Consider each element $x$ and say it's at index $i$. Then, replace $x$ with $1$ at index $n-i+1$. Then, shift the remaining elements up by $1$ and keep their relative order preserved, filling in the gaps. Now, notice that this function preserves the number of inversions, because the number of inversions not involving $x$ in the original permutation is the same as the number of inversions not involving $1$ in the new permutation(as the relative ordering is the same, except shifted up by $1$). And note that if $w_i=1=x$, then $(i, j)$ is an inversion iff $(n+1-i, n+1-j)$ is an inversion in the new ordering(since $x$ is greater than everything and thus it's inversion iff $j<i$ and $w_j \not = x$, and $1$ is smaller than everything and thus it's inversion iff $j>i$ and $w_j \not = 1$). Therefore, we have a bijection on the number of inversions. Furthermore, the transformation is bijective, as the reverse process is moving all the $1$s at position $i$ to $n-i+1$ and moving all the other elements down by $1$, keeping the relative order preserved. Therefore, we're done.
Whoops wrote BS for 2 pages(proving for all distinct), then wrote down this solution, except didn't realize I was done. Don't know how much I'll get for this problem.
infiniteturtle
20.04.2017 02:18
Define $f_A(i,j)=(w_i-w_j)(a_i-w_i)(a_i-w_j)$, where $A=(a_1,a_2,\dots ,a_n).$ Induct.
shiningsunnyday
20.04.2017 02:22
Here's the natural interpretation of the condition. In permutation $(w_1, \ldots, w_j, \ldots, w_k, \ldots, w_n)$ with $w_j, w_k$ being an $A$-inversion, note that there must be the corresponding permutation $(w_1, \ldots, w_k, \ldots, w_j, \ldots, w_n)$ with $w_j, w_k$ for which it is not an $A$-inversion.
I put that above + proving it for $n=2$ and writing down: "assume it holds true for $n=2, \ldots, n-1.$ For $n$ WLOG let $w_{n} = \max \{w_1, w_2, \ldots, w_{n} \},$ and it suffices to show that the number of new $A$-inversions created with $w_n$ as one of the pair can be bijected to another permutation with the same number of $B$-inversions created with $w_n$ as one of the pair, which is easy" (I don't think this is even true lol). How much does this worth? (not expecting much...)
Phie11
20.04.2017 02:22
infiniteturtle wrote:
Define $f_A(i,j)=(w_i-w_j)(a_i-w_i)(a_i-w_j)$, where $A=(a_1,a_2,\dots ,a_n).$ Induct.
I got the first part. Do you think I would get a point?
v_Enhance
20.04.2017 02:24
infiniteturtle wrote:
Define $f_A(i,j)=(w_i-w_j)(a_i-w_i)(a_i-w_j)$, where $A=(a_1,a_2,\dots ,a_n).$ Induct.
How does this work? I actually don't see. (I'm sure there's a solution using this $f_A$ but I can't tell what it is.)
infiniteturtle
20.04.2017 02:27
Compare $A$ and $A'=(a_1+1,a_2,a_3,..., a_n)$. (I guess I forgot to say that $w_i,w_j$ make an inversion iff $w_j\neq w_i, a_i$ and $f_A(i,j)\ge 0.$)
efang
20.04.2017 02:29
We create a bijection to a sequence $B = (b_1, b_2, ... ,b_n)$ such that every integer $B$ is greater than everything in the permutation. Let $A$ be an arbitrary sequence. For each permutation $m_1. m_2, .. ,m_n$ define the inversion set with respect to A of $m_i$ to be all the $m_j$ such that $(m_i, m_j)$ is an A-inversion. And let $In_A(m_i)$ be the cardinality of the inversion set with respect to A of $m_i$ For each sequence $M = m_1, m_2, ... , m_n$ we create a permutation such that the number of A-inversions of M is equal to the number of $B$-inversions. Call this sequence $p_1, p_2, ... ,p_n$. We create this sequence backwards. If $In_A(m_{n-1}) = 1$ then we let $p_{n-1} > p_n$ and if $In_A(m_{n-1}) = 0$ then we let $p_{n-1} \le p_n$. Similarly if $In_A(m_{n-2}) = 2$ then we let $p_{n-2}$ be greater than the last 2 terms, if it's 1 then in the middle and if its 0 then less than both of them. We continue in this fashion until we create a well defined sequence of $p_1, p_2, ... p_n$ which has the same number of $B$-inversions. (This is because the number of $B$ inversions of $p_1, p_2, ... , p_n$ is when $i<j$ and $p_i > p_j$ and by construction this is the same number of $A$-inversions of the sequence $M$) All that remains to be show is that if we have 2 sequences $t_1, t_2, ... ,t_n$ and $q_1, q_2, ... ,q_n$ such that $In_A(t_i) = In_A(q_i)$ then we have that these 2 sequences are the same. The casework for this is pretty silly, just start with $In_A(t_1) = In_A(q_1) \implies t_1 = q_1$ and then continue in this fashion for the rest of the sequence we easily see that this is a bijection. We have found a bijection to a constant set which preserves the number of inversions. Thus, the number of permutations with $k$ inversions is constant regardless of the sequence $A$ as desired. Wait somebody pls check this
gradysocool
20.04.2017 02:32
So I tried to fakesolve this, and then somehow my fakesolve turned into a valid solution. So essentially I used induction to prove that it was sufficient to prove for all a_i's equal. Then I managed in the last 10 minutes to find what I called a "transitive comparison $*>$" (roughly a redefinition of $>$), such that if $m_i*>m_j$ then it is counted as an $A$-inversion. I just hope my proof is complete enough and understandable enough to get 7...this one was difficult. Do you think this counts as the algebra problem? It felt like algebra to me (please don't take away my combo ).
adamov1
20.04.2017 02:37
Can someone check if this works? Edit: this works Induction on $n$ trivially gives that the result is true for all distinct, and we replace integer with reals because it makes our life easier. Now, let $F_k$ be the number of permutations of our original sequence $M$ that give $k$ $A$-inversions. We will construct a new sequence $M'$ by taking each duplicated set $m_{i+1},...,m_{i+j}$ and subtracting very small (different and $<1$) values to make them pairwise distinct. Let $F_k'$ be the same as $F_k$ but for this new sequence. I claim that the $F_k'$ are related to the $F_k$ by a system of linear equations with coefficients independent of $A$. Consider the $A$-inversions added to a permutation of $M$ by performing our operation and sending it to a permutation of $M'$. Because of the way we dealt with the duplicated elements, the only inversions we add are those that lie solely amongst each group of formerly duplicated values. By construction the $a_i$ cannot lie in between 2 of these values, so these $A$-inversions are just of type 1 and 3, i. e. they are just inversions in the traditional sense, thus the number of inversions added is independent of the $a_i$. If $M$ has duplicate sets of size $j_1,...,j_x$, then we can add at most $L=\binom{j_1}{2}+...+\binom{j_x}{2}$ inversions by permuting the duplicate values. Thus we can write $F_k'=c_{k,0} F_k+c_{k,1} F_{k-1}+...+c_{k,L} F_{k-L}$ where the $c_{i,j}$ are independent of the $a_i$. These equations form a triangular matrix which has a unique solution, thus the values of $F_k$ are uniquely determined from those of $F_k'$ so the $F_k$ are independent of $A$.
pieater314159
20.04.2017 02:43
Shaddoll wrote:
We proceed by induction. For $n=1$, there are obviously $0$ A-inversions regardless of $A$. Note that the number of A-inversions is the number of A-inversions involving $w_1$ plus the number of $A-a_1$ inversions(where $A-a_1$ is $A$ with the first element truncated and the other elements with indices shifted down by $1$). By inductive hypothesis, the number of ways to get $k$ inversions not involving the first element is the same for any $A-a_1$, so we can assume all the $a_i$s are equal.
Now, WLOG, let the distinct elements be $1$, $2$, ..., $x$(where each element has the corresponding multiplicity in the original set, ranked in order). Now, we claim that a cyclic shift(Shifting $1$ to $2$, $2$ to $3$, and so on, $x-1$ to $x$, and $x$ to $1$) preserves the number of permutations with $k$ normal inversions. This is clearly equivalent to the proving the problem for all $a_i$s are equal. We biject as follows:
Consider each element $x$ and say it's at index $i$. Then, replace $x$ with $1$ at index $n-i+1$. Then, shift the remaining elements up by $1$ and keep their relative order preserved, filling in the gaps. Now, notice that this function preserves the number of inversions, because the number of inversions not involving $x$ in the original permutation is the same as the number of inversions not involving $1$ in the new permutation(as the relative ordering is the same, except shifted up by $1$). And note that if $w_i=1=x$, then $(i, j)$ is an inversion iff $(n+i-1, n+j-1)$ is an inversion in the new ordering(since $x$ is greater than everything and thus it's inversion iff $j<i$ and $w_j \not = x$, and $1$ is smaller than everything and thus it's inversion iff $j>i$ and $w_j \not = 1$). Therefore, we have a bijection on the number of inversions. Furthermore, the transformation is bijective, as the reverse process is moving all the $1$s at position $i$ to $n-i+1$ and moving all the other elements down by $1$, keeping the relative order preserved. Therefore, we're done.
Whoops wrote BS for 2 pages(proving for all distinct), then wrote down this solution, except didn't realize I was done. Don't know how much I'll get for this problem. Why can we assume all $a_i$s are equal? I don't quite understand that step.
mathwizard888
20.04.2017 02:49
pieater314159 wrote: Shaddoll wrote:
We proceed by induction. For $n=1$, there are obviously $0$ A-inversions regardless of $A$. Note that the number of A-inversions is the number of A-inversions involving $w_1$ plus the number of $A-a_1$ inversions(where $A-a_1$ is $A$ with the first element truncated and the other elements with indices shifted down by $1$). By inductive hypothesis, the number of ways to get $k$ inversions not involving the first element is the same for any $A-a_1$, so we can assume all the $a_i$s are equal.
Now, WLOG, let the distinct elements be $1$, $2$, ..., $x$(where each element has the corresponding multiplicity in the original set, ranked in order). Now, we claim that a cyclic shift(Shifting $1$ to $2$, $2$ to $3$, and so on, $x-1$ to $x$, and $x$ to $1$) preserves the number of permutations with $k$ normal inversions. This is clearly equivalent to the proving the problem for all $a_i$s are equal. We biject as follows:
Consider each element $x$ and say it's at index $i$. Then, replace $x$ with $1$ at index $n-i+1$. Then, shift the remaining elements up by $1$ and keep their relative order preserved, filling in the gaps. Now, notice that this function preserves the number of inversions, because the number of inversions not involving $x$ in the original permutation is the same as the number of inversions not involving $1$ in the new permutation(as the relative ordering is the same, except shifted up by $1$). And note that if $w_i=1=x$, then $(i, j)$ is an inversion iff $(n+i-1, n+j-1)$ is an inversion in the new ordering(since $x$ is greater than everything and thus it's inversion iff $j<i$ and $w_j \not = x$, and $1$ is smaller than everything and thus it's inversion iff $j>i$ and $w_j \not = 1$). Therefore, we have a bijection on the number of inversions. Furthermore, the transformation is bijective, as the reverse process is moving all the $1$s at position $i$ to $n-i+1$ and moving all the other elements down by $1$, keeping the relative order preserved. Therefore, we're done.
Whoops wrote BS for 2 pages(proving for all distinct), then wrote down this solution, except didn't realize I was done. Don't know how much I'll get for this problem. Why can we assume all $a_i$s are equal? I don't quite understand that step. Hm yeah the number of $A$-inversions involving $w_1$ depends on $a_1$ unless I'm being dumb.
bobthesmartypants
20.04.2017 02:52
Does anyone have a solution utilizing the fact that the condition becomes very nice if you put all the points on the real line + point at infinity, i.e a circle? The fact that it became so nice was my downfall
Shaddoll
20.04.2017 03:49
mathwizard888 wrote: pieater314159 wrote: Shaddoll wrote:
We proceed by induction. For $n=1$, there are obviously $0$ A-inversions regardless of $A$. Note that the number of A-inversions is the number of A-inversions involving $w_1$ plus the number of $A-a_1$ inversions(where $A-a_1$ is $A$ with the first element truncated and the other elements with indices shifted down by $1$). By inductive hypothesis, the number of ways to get $k$ inversions not involving the first element is the same for any $A-a_1$, so we can assume all the $a_i$s are equal.
Now, WLOG, let the distinct elements be $1$, $2$, ..., $x$(where each element has the corresponding multiplicity in the original set, ranked in order). Now, we claim that a cyclic shift(Shifting $1$ to $2$, $2$ to $3$, and so on, $x-1$ to $x$, and $x$ to $1$) preserves the number of permutations with $k$ normal inversions. This is clearly equivalent to the proving the problem for all $a_i$s are equal. We biject as follows:
Consider each element $x$ and say it's at index $i$. Then, replace $x$ with $1$ at index $n-i+1$. Then, shift the remaining elements up by $1$ and keep their relative order preserved, filling in the gaps. Now, notice that this function preserves the number of inversions, because the number of inversions not involving $x$ in the original permutation is the same as the number of inversions not involving $1$ in the new permutation(as the relative ordering is the same, except shifted up by $1$). And note that if $w_i=1=x$, then $(i, j)$ is an inversion iff $(n+i-1, n+j-1)$ is an inversion in the new ordering(since $x$ is greater than everything and thus it's inversion iff $j<i$ and $w_j \not = x$, and $1$ is smaller than everything and thus it's inversion iff $j>i$ and $w_j \not = 1$). Therefore, we have a bijection on the number of inversions. Furthermore, the transformation is bijective, as the reverse process is moving all the $1$s at position $i$ to $n-i+1$ and moving all the other elements down by $1$, keeping the relative order preserved. Therefore, we're done.
Whoops wrote BS for 2 pages(proving for all distinct), then wrote down this solution, except didn't realize I was done. Don't know how much I'll get for this problem. Why can we assume all $a_i$s are equal? I don't quite understand that step. Hm yeah the number of $A$-inversions involving $w_1$ depends on $a_1$ unless I'm being dumb. I think you are misunderstanding my solution. We set the rest of the $a_i$s to be equal to $a_1$(which I showed we could do by induction). And then we prove that no matter what we set that equal amount to, it gives the same amount of ways for $k$ A-inversions.
mota60ceng
20.04.2017 03:52
bobthesmartypants wrote: Does anyone have a solution utilizing the fact that the condition becomes very nice if you put all the points on the real line + point at infinity, i.e a circle? The fact that it became so nice was my downfall Ok so I came up with the circle epiphany 5m before the end of the contest, but I think something like this works:
Place the set of $2n$ values $a_1, \ldots, a_n, m_1, \ldots, m_n$ in non-increasing order, so that when the values are equal, the $a's$ always come before the $m's$. One way to think of this is $2n$ beads on a string, each labeled with the respective $a$ or $m$. Then we wrap the string around in a circle, so that going clockwise the values are always nonincreasing (until we jump from the highest value to the lowest). We call this a A-bracelet. With this configuration, the A-inversion condition becomes seeing $a_i, w_i, w_j$ in clockwise order.
Note that for a sequence $A$, the position (and label) of the A-beads on the bracelet are fixed regardless of the permutation $w$, since the set of $w's$ doesn't change. So a permutation only rearranges the labels on the $w$-beads. Now, we can create a bijection from (A, w) to (B, w') as follows:
1) figure out the fixed positions of the B-beads on the string.
As an example, let the A-bracelet be $a_4, a_5, a_1, 3, a_3, 5, 1, a_2, 2, 4$ (where 3 stands for w_3 being in that position, taking on whatever value necessary to fit the bracelet order), and the B-bracelet be $b_1, ?, b_5, b_2, ?, ?, ?, b_4, ?, b_3$, where the $?$'s are where the permuted values $w'$ will go.
2) Starting at $i=1$, we read off the bracelet made by (A, w) starting from $a_i$, ignoring other $a's$ and only paying attention to the position of the $w_j's$. Let's say we see the w_subscripts in the order $3, 5, 1, 2, 4$ -- then $(1, 2), (1, 4)$ are the inversions with $i=1$, since they come after $w_1$. So if we want to preserve the number of inversions with $i=1$ on the B-bracelet, we also want to put $w'_1$ in the 3rd space after $b_1$. This gives
$b_1, ?, b_5, b_2, ?, 1, ?, b_4, ?, b_3$
3) Do the same for $i=2..n$. For this example:
$i=2$: reading off A-bracelet: $2, 4, 3, 5, 1$, so $w'_2$ should come right after $b_2$ -- $b_1, ?, b_5, b_2, 2, 1, ?, b_4, ?, b_3$
$i=3$: reading off A-bracelet: $5, 1, 2, 4, 3$, so $w'_3$ should come last -- $b_1, ?, b_5, b_2, 2, 1, ?, b_4, 3, b_3$
$i=4$: reading off A-bracelet: $3, 5, 1, 2, 4$, so $w'_4$ should come last -- $b_1, ?, b_5, b_2, 2, 1, 4, b_4, 3, b_3$
$i=5$ just goes in the last place: $b_1, 5, b_5, b_2, 2, 1, 4, b_4, 3, b_3$.
Now, any sequence $A$ just gives us a fixed bead placement, so we can use the above bijection to map each k A-inversion permutation to another k B-inversion permutation. It remains to show that this mapping is a bijection (so it's invertible) and to make the bracelet definition rigorous, but that shouldn't be too hard.
mathwizard888
20.04.2017 03:52
@Shaddoll I don't get how you showed that it's fine to set all of the $a_i$ equal.
MathPanda1
20.04.2017 03:54
infiniteturtle wrote: Compare $A$ and $A'=(a_1+1,a_2,a_3,..., a_n)$. I proved that it suffices to do this, but was not able to actually prove the problem is true for $A$ and $A'$. Will this give me any marks?
nosaj
20.04.2017 03:55
High wrote: Do you think proving trivial case where all m are distinct can salvage anything? I also only proved the case where all of the $m_i$ are distinct. Can someone explain why this case is trivial? (It took me 4 pages just to prove this case.) Was the full problem significantly harder than the case where they're distinct? During the test, I thought I had proved the bulk of the problem and would get most of the points, but after seeing this post, I'm not so sure anymore. Basically, I want to know whether this would be scored 7- or 0+.
High
20.04.2017 04:01
I wouldn't call it completely trivial (I did it by outlining a recursive process -> every choice for $w_1$ contributes a different amount), but proving the actual requires a lot more insight, based on solutions I've seen. Definitely a 0+
fz0718
20.04.2017 04:28
First prove it for all distinct $m_i$, which can be done in several ways, as outlined in the above posts. I personally did this with induction.
Now, once you have it for distinct $m_i$, we can define a few generating functions. Define:
$$j_d(x) = \sum_k \text{[number of permutations of d all distinct numbers with k inversions]} \cdot x^k$$$$f(x) = \sum_k \text{[number of permutations of m with k inversions]} \cdot x^k$$$$g(x) = \sum_k \text{[number of permutations of m with k A-inversions]} \cdot x^k$$Also define $p_1, p_2, \dots, p_{n'}$ to be the unique elements in $m_1, \dots, m_n$, and define $\#(x)$ to be the number of times $x$ appears in $m_1, \dots, m_n$. Note that
$$\sum_{i=1}^{n'} \#(p_i) = n$$
Now, consider what happens when we apply a transformation that provides an arbitrary ordering to the non-distinct elements. More specifically, define a new sequence of unique numbers $m_1', m_2', \dots, m_n'$ such that
$$\{m_1', m_2', \dots, m_n'\} = \bigcup_{i=1}^{n'} \{ np_i + 1, np_i + 2, \dots, np_i + \#(p_i) \}$$And, to maintain the same ordering, define:
$$A' = \{na_1 + n, na_2 + n, \dots, na_n + n\}$$Okay so we're ready to do stuff now. By the previous result, we know that both the number of inversions and A-inversions in the transformed sequence are the same, and the generating function for them we defined as $j_n(x)$. However, we can also count these separately using a product of generating functions.
The inversions in a permutation of the transformed sequence can be divided into inversions that would've been in the old sequence and inversions arising from the ordering we added in. This can be counted as:
$$j_n(x) = \dfrac{f(x)}{\prod_{i=1}^{n'} (\#(p_i)!)} \cdot \prod_{i=1}^{n'} j_{\#(p_i)}(x),$$$$j_n(x) = \dfrac{g(x)}{\prod_{i=1}^{n'} (\#(p_i)!)} \cdot \prod_{i=1}^{n'} j_{\#(p_i)}(x).$$So $f(x) = g(x)$ and we are done.
I actually got this trick from a cs problem, but I forgot the source :/
math90
20.04.2017 08:42
If my collection is $1,1,2$, is the permutation $(1,2,1)$ counted once or twice?
Ani10
20.04.2017 09:03
Hmm this problem seems v tough I feel like this should've been a C3
mathtastic
20.04.2017 17:05
Can someone please provide an English translation of this problem? I wonder what the problem writer was thinking when they wrote it.
bobthesmartypants
20.04.2017 18:12
mathtastic wrote: Can someone please provide an English translation of this problem? I wonder what the problem writer was thinking when they wrote it.
America is engaged in World War III with the world powers. America has $n$ different military bases numbered as military base #1 to military base #n in various locations on the equator, and has some number of countries on the equator that it wants to target with America's supply of nukes. Each country has a certain number of cities, so that the total number of cities equals $n$. Suppose that America starts shooting nuclear warheads one at a time starting with military base #1 to military base #n, and these missiles circle eastwards around the equator. America can choose to bomb each of the $n$ cities in any order, but in any order we choose, we see that each missile flies over a certain number of countries that have not had all their cities destroyed, before landing on the target city. If we let the total number of fly-by's over all non-destroyed cities be $k$, then we want to show that the number of ways to choose the order in which to destroy the cities such that there are exactly $k$ fly-by's is the same no matter where America's military bases are located.
Zawadx
20.04.2017 23:52
Doing it for distinct is easy enough, though I twisted it a bit (brought matrices into the mix >.>). Here's my solution for non-distinct:
Sort the $m_i$ in ascending order. For the duplicated sets $m_{i+1}, \dots, m_j$ assign an order so that we can treat them all as distinct. You then show something is ordered above another with the $*>$ symbol. So for $m_1=m_2=m_3=6$, you can write $7$ $*>$ $m_1$ $*>$ $m_2$ $*>$ $m_3$ $*>$ $5$.
Now we define an $A$-unversion to a pair $w_i, w_j$ satisfying $i<j$ and one of:
$w_i *> w_j$, and $a_i \ge w_i$ or $w_j > a_i$
$w_j *> w_i$ and $a_i \in [w_i, w_j)$. Here we interpret [x, x) as an empty interval.
note that if $w_i \ne w_j$ and unversion is the same as an inversion. But if $w_i = w_j$, exactly one of the pairs $(w_i, w_j)$ and $(w_j,w_i)$ is counted as an unversion where none are counted as an inversion.
Now by our argument for distinct ${m_i}$, the number of permutations having a specific number of $A$-unversions does not depend on the sequence $A$. But the total number of unversions equals the total number of inversions plus the number of pairs of equal $m_i, m_j$ with $i>j$. Since the number of pairs of equal $m_i$ doesn't depend on $A$ either, the total number of inversions doesn't depend on $A$ as well. (QED)
Could someone tell me if there's any flaw? Cause this felt a bit too natural and easy compared to some of the solutions above, so I feel like I'm missing something. Also, is the solution for distinct really trivial to write? I tried to emulate the contest at home, and writing up that part of the solution took me a long time. Is there a simple way to prove that the number of inversions involving $a_1$ is distinct for each $m_i$, taking all values from $0$ to $n-1$?
broses
21.04.2017 17:29
mota60ceng wrote: bobthesmartypants wrote: Does anyone have a solution utilizing the fact that the condition becomes very nice if you put all the points on the real line + point at infinity, i.e a circle? The fact that it became so nice was my downfall Ok so I came up with the circle epiphany 5m before the end of the contest, but I think something like this works:
Place the set of $2n$ values $a_1, \ldots, a_n, m_1, \ldots, m_n$ in non-increasing order, so that when the values are equal, the $a's$ always come before the $m's$. One way to think of this is $2n$ beads on a string, each labeled with the respective $a$ or $m$. Then we wrap the string around in a circle, so that going clockwise the values are always nonincreasing (until we jump from the highest value to the lowest). We call this a A-bracelet. With this configuration, the A-inversion condition becomes seeing $a_i, w_i, w_j$ in clockwise order.
Note that for a sequence $A$, the position (and label) of the A-beads on the bracelet are fixed regardless of the permutation $w$, since the set of $w's$ doesn't change. So a permutation only rearranges the labels on the $w$-beads. Now, we can create a bijection from (A, w) to (B, w') as follows:
1) figure out the fixed positions of the B-beads on the string.
As an example, let the A-bracelet be $a_4, a_5, a_1, 3, a_3, 5, 1, a_2, 2, 4$ (where 3 stands for w_3 being in that position, taking on whatever value necessary to fit the bracelet order), and the B-bracelet be $b_1, ?, b_5, b_2, ?, ?, ?, b_4, ?, b_3$, where the $?$'s are where the permuted values $w'$ will go.
2) Starting at $i=1$, we read off the bracelet made by (A, w) starting from $a_i$, ignoring other $a's$ and only paying attention to the position of the $w_j's$. Let's say we see the w_subscripts in the order $3, 5, 1, 2, 4$ -- then $(1, 2), (1, 4)$ are the inversions with $i=1$, since they come after $w_1$. So if we want to preserve the number of inversions with $i=1$ on the B-bracelet, we also want to put $w'_1$ in the 3rd space after $b_1$. This gives
$b_1, ?, b_5, b_2, ?, 1, ?, b_4, ?, b_3$
3) Do the same for $i=2..n$. For this example:
$i=2$: reading off A-bracelet: $2, 4, 3, 5, 1$, so $w'_2$ should come right after $b_2$ -- $b_1, ?, b_5, b_2, 2, 1, ?, b_4, ?, b_3$
$i=3$: reading off A-bracelet: $5, 1, 2, 4, 3$, so $w'_3$ should come last -- $b_1, ?, b_5, b_2, 2, 1, ?, b_4, 3, b_3$
$i=4$: reading off A-bracelet: $3, 5, 1, 2, 4$, so $w'_4$ should come last -- $b_1, ?, b_5, b_2, 2, 1, 4, b_4, 3, b_3$
$i=5$ just goes in the last place: $b_1, 5, b_5, b_2, 2, 1, 4, b_4, 3, b_3$.
Now, any sequence $A$ just gives us a fixed bead placement, so we can use the above bijection to map each k A-inversion permutation to another k B-inversion permutation. It remains to show that this mapping is a bijection (so it's invertible) and to make the bracelet definition rigorous, but that shouldn't be too hard.
What about $a_1, 1, a_2, 2$ and $b_1, b_2, ?, ?$ Then 1 and 2 should both be placed in the first spot. I was thinking this same circle thing too.
linpaws
22.04.2017 08:23
First, note that A and B are not important. The problem really asks that the distribution of the number of inversions does not depend on A.
Now, if we play around and make A very large, the inversions become standard inversions. In an array of numbers, the number of inversions is just the number of pairs $(i, j)$ with $i<j$ and $a_i>a_j$ (this is a common topic in algorithmic programming/USACO).
Eventually, I got stuck, so I thought about inversion counting in USACO contests. The easy $n^2$ solution is to loop over every pair, but one $n$log$n$ solution is to loop once through the array in order, similar to the following: for simplicity, suppose the numbers are distinct $x_1<x_2<...<x_n$. Then, if the first number is $x_i$, it is in $(i-1)$ inversions: every $x_j$ with $j<i$ appears after it. Then, we add $(i-1)$ to a running counter, "delete" it, and now have $(n-1)$ numbers. This means that depending on $x_i$, there are anywhere from $0$ to $n-1$ inversions including the first element. We now keep going on these $(n-1)$ numbers, where on our new list, there are anywhere from $0$ to $n-2$ inversions including the first element. If we keep going until the end, doing this step n times, we get that we add a number from $0$ to $n-1$, a number from $0$ to $n-2$, ..., a number from $0$ to $0$. Clearly, there are $n!$ ways to do this.
First, suppose all the $w_i$ are distinct. Also, clearly the fact that they are integers doesn't matter (they can be real numbers). WLOG suppose $m_1<m_2<...<m_i<=a_i<m_{i+1}<...<m_n$. It is easy to see that if $w_1=m_j$, the number of inversions that contain $w_1$ and some other number is $(n-1-i)+j$ if $j<=i$, and $j-i-1$ if $j>i$. Note that this goes through all the numbers from $0$ to $n-1$. Then, this is just like in the motivation: we take a number from $0$ to $n-1$, then a number from $0$ to $n-2$, and so on, until a number from $0$ to $0$, and add these $n$ numbers up. This gives us a number of inversions, and there are n! different ways to do this process. It is equivalent for any choice of the sequence A.
Formally: We use induction. There are $n$ ways to choose $w_1$, corresponding to a number of inversions with $w_1$ from $0$ to $n-1$. Then, if we hide $w_1$ and keep going, if we consider the inversions in the rest of the $n-1$ numbers, this is equivalent to the case for $n-1$ numbers.
For ease of explanation, let us define the generating function $g(x)$ to be the sum of $c_ix^i$, where $c_i$ is the number of permutations of the numbers with $i$ A-inversions. We claim that this is fixed, only dependent on the number of numbers. We do this with induction. Let $g_k(x)$ be the generating function corresponding to permutations of $k$ numbers. Clearly, $g_1(x)=1x^0=1$. Then, from what we have above, clearly $g_k(x)=(1+x+...+x^{k-1})g_{k-1}(x)$.
Example: $3$ numbers, say $1, 2, 3$. For each permutation (assume the $a_i$ are very large so these are regular inversions), the number of inversions is as follows: $(1,2,3)=0, (1,3,2)=1, (2,1,3)=1, (2,3,1)=2, (3,1,2)=2, (3,2,1)=3$. This corresponds to the generating function $x^0+x^1+x^1+x^2+x^2+x^3=1+2x+2x^2+x^3$.
Note that just as outlined in the induction, $1+2x+2x^2+x^3=(1+x+x^2)(1+x)(1)$.
Generating functions are not really necessary in the distinct case, but very helpful in the nondistinct case.
For nondistinct: suppose there is a group $X$ of $d$ different $m_i$ with the same value, WLOG $m_1, m_2, ..., m_d$. Suppose we perturb these slightly, where for a very small number $e$, we subtract $e$ from $m_1$, $2e$ from $m_2$, and so on, until subtracting $de$ from $m_d$.
For any permutation, consider the inversions. Any pair outside $X$ is obviously unchanged by this perturbation. Any pair consisting of one number in $X$ and one number outside $X$ is also unchanged (with regards to whether or not it is an inversion). The only changes happen between the numbers already in $X$, where the number of inversions goes from $0$ (because there are no inversions between two equal values) to a distribution following the distribution for the distinct case mentioned above: following the generating function $g_d(x)$.
Now, we will count the inversions in a different manner. Consider the original group of $m_i$ (without the perturbation), but suppose $m_1, m_2, ..., m_d$ are indistinguishable. That is, permuting $m_1, m_2, ..., m_d$ within a permutation is considered the same permutation, so the number of permutations is $n!/d!$. Suppose that this follows a generating function $f(x)$. The coefficient in front of each exponent is equal to the number of permutations with the number of inversions equal to that exponent.
Then, when we do the perturbation, each original permutation gives rise to $d!$ new ones, because the $m_1, m_2, ..., m_d$ are no longer indistinguishable. To each possible number of inversions, we are adding a new number corresponding to the distribution for $k$ distinct numbers. This actually corresponds to multiplying $f(x)$ by $g_d(x)$.
Similarly, if the groups of $m_i$ with the same value have sizes $d_1, d_2, ..., d_y$, then if we consider the $n!/(d_1!d_2!...d_y!)$ permutations of the $m_i$, which follow some generating function $f(x)$. If we perturb every group, this is equivalent to the new generating function $f(x)g_{d_1}(x)g_{d_2}(x)...g_{d_y}(x)$. And now we have $n$ distinct numbers, so our new generating function is also equal to $g_n(x)$. Therefore, our generating function without the perturbations is $\frac{g_n(x)}{g_{d_1}(x)g_{d_2}(x)...g_{d_y}(x)}\cdot (d_1!d_2!...d_y!)$, where the $(d_1!d_2!...d_y!)$ factor is when we don't perturb but we make the equal values distinguishable, so we are just adding $0$ new inversions to each new permutation. The important thing is that this generating function is independent of $A$, so we are done.
Suppose the groups of equal values among the $m_i$ have size $d_1, d_2, ..., d_y$, so $d_1+d_2+...+d_y=n$.
Define the generating function $g_k(x)=(1+x+...+x^{k-1})(1+x+...+x^{k-2})...(1+x)(1)$.
Then, the generating function corresponding to the distribution of the number of inversions over all permutations is
$$ \frac{g_n(x)\cdot d_1!d_2!...d_y!}{g_{d_1}(x)g_{d_2}(x)...g_{d_y}(x)}. $$
Here the generating function is the sum of $c_ix^i$, where $c_i$ is the number of permutations with $i$ inversions.
ABCDE
28.04.2017 00:02
Solved this a week too late Here's a pretty straightforward solution with generating functions: First, we may order $m_1,m_2,\ldots,m_n$ anyway we want as we only care about their permutations, so order them to \[m_1=m_2=\ldots=m_{c_1}<m_{c_1+1}=m_{c_1+2}=\ldots=m_{c_2}<\ldots<m_{c_1+c_2+\ldots+c_{i-1}+1}=m_{c_1+c_2+\ldots+c_{i-1}+2}=\ldots=m_{c_1+c_2+\ldots+c_i}\]where $c_1+c_2+\ldots+c_i=n$. For convenience, set $n_0=0$ and $n_j=m_{c_j}$ for $j>0$. Note that we may assume that $a_j\in\{n_0,n_1,\ldots,n_i\}$ as the only thing that affects the conditions is the interval out of $(-\infty,n_1),[n_1,n_2),[n_2,n_3),\ldots,[n_{i-1},n_i),[n_i,\infty)$ that $a_j$ lies in. Now, we induct on $n$ to show that \[c_1!\cdot c_2!\cdot\ldots\cdot c_i!\cdot\binom n{c_1,c_2,\ldots,c_i}_t\]is the generating function such that the coefficient of $t^k$ is the number of permutations of $m_1,m_2,\ldots,m_n$ with exactly $k$ $A$-inversions for any $A$, which will imply the problem statement as this expression is independent of $A$. Here, we define the $t$-factorial as $j!_t=\frac{(1-t)(1-t^2)\ldots(1-t^j)}{(1-t)^j}$ for any nonnegative integer $j$ and the $t$-multinomial as $\binom n{c_1,c_2,\ldots,c_i}_t=\frac{n!_t}{c_1!_t\cdot c_2!_t\cdot \ldots\cdot c_i!_t}$.
By the problem statement, you know that this generating function must be independent of $A$. Setting $A=0,0,\ldots,0$, $A$-inversions become regular inversions. It is then easy to induct to show that this generating function is $n!_t$ if $c_1=c_2=\ldots=c_n=1$. For the repeating case, note that each group of $c_i$ contributes an extra $c_i!_t$ overall, while they really should contribute $c_i!$. Since the permuting each group is independent, we can multiply by $\frac{c_i!}{c_i!_t}$, resulting in the generating function described above.
For the base case of $n=1$, our generating function is $1\binom11_t=1$, which is correct as we only have to consider the identity permutation which has no inversions. For the inductive step, suppose that $a_1=n_p$ and $w_1=n_q$. Note that if $w_1$ is in $r$ inversions, then the generating function for the number of permutations of $m_1,m_2,\ldots,m_n$ with $w_1=n_q$ and a fixed number of inversions is \[t^r\cdot c_1!\cdot c_2!\cdot \ldots\cdot (c_q-1)!\cdot \ldots\cdot c_i!\cdot\binom{n-1}{c_1,c_2,\ldots,c_q-1,\ldots,c_i}_t\]with the second term derived from the inductive hypothesis. If $p\ge q$, then $w_1,n_j$ is an inversion if $j>p$ or $j<q$, leading to $c_1+c_2+\ldots+c_{q-1}+c_{p+1}+c_{p+2}+\ldots+c_i$ inversions involving $w_1$. If $p<q$, then $w_1,n_j$ is an inversion if $p<j<q$, leading to $c_{p+1}+c_{p+2}+\ldots+c_{q-1}$ inversions involving $w_1$. Summing over all possible values of $w_1$ (noting that there are $c_q$ times when $w_1=n_q$), it suffices to show that \[\sum_{q=1}^p c_q\cdot t^{c_1+c_2+\ldots+c_{q-1}+c_{p+1}+c_{p+2}+\ldots+c_i}\cdot c_1!\cdot c_2!\cdot \ldots\cdot (c_q-1)!\cdot \ldots\cdot c_i!\cdot\binom{n-1}{c_1,c_2,\ldots,c_q-1,\ldots,c_i}_t\]\[+\sum_{q=p+1}^i c_q\cdot t^{c_{p+1}+c_{p+2}+\ldots+c_{q-1}}\cdot c_1!\cdot c_2!\cdot \ldots\cdot (c_q-1)!\cdot \ldots\cdot c_i!\cdot\binom{n-1}{c_1,c_2,\ldots,c_q-1,\ldots,c_i}_t\]\[=c_1!\cdot c_2!\cdot\ldots\cdot c_i!\cdot\binom n{c_1,c_2,\ldots,c_i}_t.\]This is much easier than it looks. Dividing both sides by $\frac{c_1!\cdot c_2!\cdot \ldots\cdot c_i!\cdot\binom n{c_1,c_2,\ldots,c_i}_t}{1-t^n}$, we are left with showing \[\sum_{q=1}^p t^{c_1+c_2+\ldots+c_{q-1}+c_{p+1}+c_{p+2}+\ldots+c_i}\cdot(1-t^{c_q})+\sum_{q=p+1}^i t^{c_{p+1}+c_{p+2}+\ldots+c_{q-1}}\cdot(1-t^{c_q})=1-t^n\]which is clearly true as the LHS telescopes to the RHS.
AIME12345
26.03.2020 00:58
Solved with franchester, ingenio, GameMaster402, anish9876, mira74, SD2014, AOPS12142015, huangyi_99, sriraamster, kothasuhas, budu, and mathfun5. We first solve a simpler case of the problem, where the $m_i$ are distinct. Lemma: For $n \in \mathbb{N}$, the number of permutations having $k$ $A$-inversions can be expressed by the coefficient of the $x^k$ term of the generating function $f(x) = \prod_{i=1}^{n} \frac{x^i-1}{x-1}$. Proof: We proceed by induction on $n$. The base case $n = 1$ is trivial as no such inversions exist. For $n = 2$, there is only one permutation with $0$ $A$-inversions and only one permutation with $1$ $A$-inversions, corresponding to the generating function $f(x) = x + 1$. Now, assume the lemma holds true for some $n \in \mathbb{N}$. We want to show this is true for $n+1$. Order the positive integers $(m_2,\cdots,m_{n+1})$ by size. Now, add a slot $a_1$ to a permutation $(a_2,\cdots,a_{n+1})$. Let $w_1 = m_y$. If $a_1<m_1$ or $a_1 \ge m_{n+1}$, then the number of new inversions generated to the old permutation is $y - 1$, as we can only generate new inversions from $a_1$ with values less than $w_1$. Otherwise, there exists $y \in \mathbb{N}$ such that $m_z \le a_1 < m_{z+1}$. We proceed with casework on $w_1$: If $w_1 = m_z$ (so $z=y$), then we can have an inversion with any other $w_j$, so this generates $n$ new inversions. If $w_1 = m_{z-c}$, then as long as $w_j$ is not between $a_1$ and $w_1$ (both inclusive), then we can have an inversion with $w_j$, so this generates $n-c$ new inversions. If $w_1=m_{z+c}$, then as long as $w_j$ is between $a_1$ and $w_1$ (both exclusive), then we can have an inversion with $w_j$, so this generates $c-1$ new inversions. Thus, after considering all cases of what $a_1$ and $m_1$ can be, there is always a case that generates $i$ new inversions to our old permutation for all $i$ between $0$ and $n$ inclusive, adding to the inductive hypothesis, our generating function is now $\prod_{i=1}^{n} \frac{x^i-1}{x-1} \cdot (1+x+\cdots+x^n) = \prod_{i=1}^{n+1} \frac{x^i-1}{x-1}$, as desired. $\blacksquare$ We now need to consider when multiple $m_i$s can be equivalent. Assume for some $m_i$ that there are $t$ copies of them. We can replace multiple $m_i$s by $m_i+k\epsilon$ where $\epsilon>0$ and $k$s are distinct. Then we have the same generating function, but we've overcounted by $\frac{f(t)}{t!}$, as there are no inversions between two equivalent integers. So for a general case of our set $(m_i)$, our generating function is $g(x) = \frac{f(x)(t_1!)(t_2!) \cdots (t_l!)}{f(t_1)f(t_2) \cdots f(t_l)}$, where $t_j$ is the number of repetitions of the $j$th smallest element in $(m_i)$. The number of permutations of $(m_i)$ having $k$ $A$-inversions can be expressed by the coefficient of the $x^k$ term. Since this generating function is independent of what the permutations $A$ and $B$ are, the number of permutations of $(m_i)$ having exactly $k$ $A$-inversions is equal to the number of permutations of $(m_i)$ having exactly $k$ $B$-inversions, and we are done. YUH.
GeronimoStilton
25.09.2021 15:10
The following approach leaves out a few steps, but the details can be filled in by taking cases which are done after the main content. Let $m_1\le m_2\le \cdots \le m_n$ without loss of generality. We prove the result by induction on $n$. The result is clear at $n=1$. We first argue that we can assume $m_1<m_2$ and so on. This is because if $m_i = m_{i+1} = \cdots = m_{j-1} = m_j<m_{j+1}$, replacing each $m_k$ for $k\ge j$ with $m_k+1$ and moving each $a_t$ that was equal to $m_i$ to $m_i+1$ will multiply the polynomial by $(1+q+\cdots+q^{j-i})/(j-i+1)$ by analyzing what inversions this adds. So this means we can assume $m_1<m_2<\cdots<m_n$. We can maneuver the $a_2,a_3,\cdots,a_n$ by the induction hypothesis since it only affects the generating function for $n-1$. Then for $a_1$, we have a generating function of $1+q+\cdots+q^{n-1}$ based on the value of $w_1$ regardless of what $a_1$ actually is, so $a_1$ also does not matter and we are done. $\fbox{}$ To see the $(1+q+\cdots+q^{j-i})/(j-i+1)$ leap, note that inversions are only added among the $m_i,\cdots,m_j$ thus we can consider just those. There are no inversions in a constant sequence and in a sequence of $\underbrace{1,1,\cdots,1}_{j-i},2$ as we can WLOG assume we have (since we can always replace $a_s$ with $a_s = \max_{w_i \le a_s} w_i$ for no change), some $w_u$ is equal to $2$ so the only possible inversions are $a_u\ge w_u>w_v$ and $w_u>w_v>a_u$, the number of which is exactly equal to $j-i+1-u$. This replaces the inversions in which it does not matter where $w_u$ is. Note that if $a_1\ge w_1$ there are $n-1-(a_1-w_1)$ inversions and if $a_1<w_1$ there are $w_1-a_1-1$ inversions so varying $w_1$ does cover all terms equally.
hellnish
17.09.2023 10:56
Does generating function really work? I have spent hours calculating the value of the k inversions,but I gained nothing. The formula seems so ugly.
HamstPan38825
27.12.2023 00:17
Here's the generating function solution from the OTIS walkthrough. It's quite motivated but still fairly painful to carry out. Notice that it suffices to show the result with $B = (0, 0, \dots, 0)$. For this $B$, I claim: Claim. The number of permutations of $[n]$ with exactly $k$ inversions is given by the coefficient of $q^k$ in $$n!_q = (1+q)(1+q+q^2)\dots(1+q+\cdots+q^{n-1}) = \prod_{i=1}^n \frac{1-q^i}{1-q}.$$ Proof. Induction. For $k$ the last term of the permutation $\sigma$, $k$ contributes exactly $k-1$ inversions to $\sigma$ and hence corresponds to a coefficient of $q^{k-1}$ in the product. Thus, adding a term is equivalent to multiplying by $1+q+\cdots+q^{n-1}$. $\blacksquare$ Now we deal with the multiplicity issue. Let $\{x_n\}$ be the increasing sequence of distinct integers that constitutes $\{m_n\}$, and let $e_i$ be the multiplicity of $x_i$ in $\sigma$. Let $F(e_1, \dots, e_m)$ be the generating function for the inversions on a sequence with multiplicities $e_1, \dots, e_m$. Claim. $F(e_1, \dots, e_m)$ is given explicitly by $n!_q \cdot \prod_{i=1}^m \frac{e_i!_q}{e_i!}$. Proof. This is essentially the functional analog of the classic overcounting problem. For any $e_i$ copies of $x_i$, perturb each of them a tiny amount such that any inversions containing exactly one element $x_i$ are preserved; after altering this for each $i$, the inversions are given by $n!_q$. Now, imagine returning all the $x_i$ for each $i$ to be equal; any inversions within the $x_i$ which contribute to the product, globally represented by $q^j$ terms, are replaced with $q^0$ terms. This replaces $e_i!_q$ in the original product with $e_i! \cdot q^0 = e_i!$. Performing this across all such $e_i$ yields the result. $\blacksquare$ Notice that we have $$\frac{e_i \cdot F(e_1, \dots, e_i - 1, \dots, e_m)}{F(e_1, \dots, e_m)} = \frac{1-q^{e_i}}{1-q^n}$$from direct computation on this formula. To finish, we prove by induction that the generating function of inversions with any arbitrary sequence $A$ is also given by $F$. In particular, we need only consider the contributions of the elements $m_i$ with respect to $a_1$. To begin with, for each of the, say $r$, $x_i$ such that $x_i \leq a_1$, $x_i$ contributes $$T_i = e_i \cdot q^{n-(e_i+e_{i+1}+\cdots+e_r)} \cdot F(e_1, \dots, e_i-1, \dots, e_m)$$as one of the $e_i$ $x_i$ forms an inversion with $a_1$ and one of the $e_j$ $x_j$ that is not within the subtracted sum per the given conditions. Similarly, for $x_i > a_1$, $x_i$ contributes $$T_i = e_i \cdot q^{e_{r+1} + \cdots + e_{i-1}} \cdot F(e_1, \dots, e_i-1, \dots, e_m).$$Hence it suffices to show that \begin{align*} F(e_1, e_2, \dots, e_m) &= \sum_{i=1}^m T_i \\ F(e_1, e_2, \dots, e_m)&=\sum_{i=1}^r e_i \cdot q^{n-(e_i+e_{i+1}+\cdots+e_r)} \cdot F(e_1, \dots, e_i-1, \dots, e_m) + \sum_{i=r+1}^m e_i \cdot q^{e_{r+1} + \cdots + e_{i-1}} \cdot F(e_1, \dots, e_i-1, \dots, e_m) \\ 1-q^n &= \sum_{i=1}^r (1-q^{e_i})q^{n-(e_i+\cdots+e_r)}+ \sum_{i=r+1}^m q^{e_{r+1}+\cdots+e_{i-1}}(1-q^{e_i}) \\ 1-q^n &= q^{e_{r+1}+\cdots+e_m} - q^n + 1 - q^{e_{r+1}+\cdots+e_m} \end{align*}as the terms of the sum telescope. This finishes the proof.
SixFifteenths
18.04.2024 08:13
very hard problem than 5,can someone tell me why to think about generating function?Thanks