# Count number of pair of sequences

Lets say you have two sequences of non negative integers each of length $$n$$.

ie $$(a_1,a_2,...,a_n)$$ and $$(b_1,b_2,...,b_n)$$ such that $$\max(a_i) < k$$ and $$\max(b_i) < k$$

Game rule:

You can edit both sequence with $$\mathrm{swap}(a_i, b_i)$$ for $$1 ≤ i≤ n$$,

Goal:

$$a_i ≤ a_j$$ for all $$i ≤ j$$ and $$b_i ≤b_j$$ for all $$i ≤ j$$

But not all initial sequence $$a$$ and $$b$$ can be solved. For example $$(2,0)$$ and $$(0,1)$$ is a pair of sequence that can't be solved.

Now given $$n$$ and $$k$$, count number of different pair of initial sequence $$(a,b)$$ that can be solved with game described above.

Example:

for $$n=1$$,$$k=2$$: These are the cases: $${[(0),(0)],[(0),(1)],[(1),(0)],[(1),(1)]}$$. Hence answer would be $$4$$.

• No edits is also an option? If we start with both sequences increasing then we win, right? Commented Jul 23, 2022 at 5:46
• Doability of the game is equivalent to $(\min(a_1,b_1),\dots,\min(a_n,b_n))$ and $(\max(a_1,b_1),\dots,\max(a_n,b_n))$ are both sorted in increasing order. Commented Jul 23, 2022 at 6:10
• @LaylaBailey oops, you are right Commented Jul 23, 2022 at 6:13
• Well in order to show that you can say that $(a, b)$ is swap equivalent to the sequence I mentioned, therefore it is doable if and only if the min and max are doable. For those it is clear that they are doable if and only if they are sorted. I am not convince I can use that to count the number of doable games but it might be useful to the comunity. Commented Jul 23, 2022 at 6:23
• the sequences of mins and maxs are won states, so the question becomes, how many such solved pairs of sequences there are and in how many ways can they be "scrambled up" Commented Jul 23, 2022 at 6:23

Disclaimer: This is just a computational answer but it gives a formula for at least for the case $$k=2$$ (and other small cases too). And it's too long for a comment.

I get these values for $$f(k, n) =$$ the number of these solvable sequence pairs

$$\displaystyle \left(\begin{array}{rrrrrrrrr} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 4 & 11 & 26 & 57 & 120 & 247 & 502 & 1013 & 2036 \\ 9 & 46 & 180 & 603 & 1827 & 5164 & 13878 & 35905 & 90189 \\ 16 & 130 & 750 & 3507 & 14224 & 52068 & 176430 & 562925 & 1711776 \\ 25 & 295 & 2345 & 14518 & 75558 & 346050 & 1436820 & 5520295 & 19916039 \\ 36 & 581 & 6076 & 48006 & 311136 & 1739166 & 8665866 & 39387491 & 166049884 \\ 49 & 1036 & 13776 & 135114 & 1065834 & 7132620 & 41957058 & 222437215 & 1082436355 \\ 64 & 1716 & 28260 & 336666 & 3173808 & 25034724 & 171535650 & 1048436675 & 5829137600 \\ 81 & 2685 & 53625 & 762399 & 8461167 & 77655435 & 612837225 & 4275850150 & 26924807910 \end{array}\right)$$

Calculation done with a Markov chain (code here).

The idea: We start building the two sequences by adding a term to each at a time. We keep as a state $$(m, M)$$ where $$m$$ is the maximum of the minimums and $$M$$ is the maximum of the maximums in the sequences so far. An example: let the sequences be

$$(2,1,3,7) \\ (0,2,2,4)$$

Then the path of the $$(m, M)$$'s is $$(0,0), (0,2), (1,2), (2,3), (4,7)$$. It always starts from $$(0,0)$$ (when the sequences are empty). Then we append $$x_1=2, x_2=0$$, we get $$m=\min(x_1, x_2) = 0$$ and $$M=\max(x_1, x_2) = 2$$. Then append $$x_1=1, x_2=2$$ (notice, these need to satisfy $$\min(x_1, x_2) \geq m$$ and $$\max(x_1, x_2) \geq M$$) and get $$(m,M) = (2,3)$$. And so on.

This leads to the following: there is a transition from $$(m_1, M_1)$$ to $$(m_2, M_2)$$ if $$m_1\leq m_2$$ and $$M_1\leq M_2$$. And it is of weight $$1$$ if $$m_2=M_2$$, because in that case only $$x_1=x_2$$ is possible, otherwise we can flip them and get weight $$2$$ transition (weight meaning the number of ways that lead to that transition). Also the "transition" -matrix $$A$$ has a nice block structure with respect to the blocks determined by value of $$m$$ in the state. And I wonder if that can be used for faster calculation of $$f(k, n) = e_1^T A^n \bf 1$$.

For example for $$k=3$$ we get the following directed graph (with edge labels indicating how many pairs of numbers lead to that transition)

To get the value $$f(k, n)$$ we count the number of $$n$$-walks on the graph starting from $$(0,0)$$. (Regard as there being multiple edges between the vertices when edge label $$>1$$)

For $$k=2$$ the graph is particularly simple and we get that $$f(2, n)$$ is the sum of the first row of

$$\displaystyle \left(\begin{array}{rrr} 1 & 2 & 1 \\ 0 & 2 & 1 \\ 0 & 0 & 1 \end{array}\right)^n$$

and that equals $$2^{n+2}-n-3$$.

Finding the Jordan normal form for the involved matrix (code here), I was able to find the formulas

\begin{align} f(3, n) &= \frac{1}{2}(n+2)(2^{n+2}(n-1)+n+5) \\ f(4, n) &= \frac{1}{6}(n+2)(n+3)(2^{n}(2n^2-2n+8) -n -7 ) \\ f(5, n) &= \frac{1}{72}(n+2)(n+3)(n+4)(2^n(2n^3+22n-24)+3n+27) \\ f(6,n) &= \frac{1}{720} (n + 2) \dots (n + 5) (2^n(n^{4} + 2n^{3} + 23 n^{2} - 26 n +72) - 6 n - 66) \end{align}

These seem to indicate some sort of pattern.

For $$k=7,8,\dots, 12$$ we have that $$\frac{f(k, n)}{n+k-1\choose k-2}$$ is

\begin{aligned} &\frac{1}{180} (2^n(n^{5} + 5 n^{4} + 45 n^{3} - 5 n^{2} + 314 n -360) + 30 n + 390) \\ &\frac{1}{1260} (2^n(n^{6} + 9 n^{5} + 85 n^{4} + 135 n^{3} + 994 n^{2} - 1224 n + 2880) - 180 n - 2700) \\ &\frac{1}{10080} (2^n(n^{7} + 14 n^{6} + 154 n^{5} + 560 n^{4} + 2989 n^{3} - 574 n^{2} + 17016 n - 20160 ) + 1260 n + 21420) \\ &\frac{1}{90720} (2^n(n^{8} + 20 n^{7} + 266 n^{6} + 1568 n^{5} + 8729 n^{4} + 11900 n^{3} + 71644 n^{2} - 94128 n + 201600) - 10080 n - 191520) \\ &\frac{1}{907200} (2^n(n^{9} + 27 n^{8} + 438 n^{7} + 3654 n^{6} + 23961 n^{5} + 71883 n^{4} + 294272 n^{3} - 75564 n^{2} + 1495728 n - 1814400) + 90720 n + 1905120) \\ &\frac{1}{9979200} (2^n(n^{10} + 35 n^{9} + 690 n^{8} + 7590 n^{7} + 60753 n^{6} + 281715 n^{5} + 1193660 n^{4} + 1453060 n^{3} + 7816896 n^{2} - 10814400 n + 21772800) - 907200 n - 20865600) \end{aligned}

EDIT:

Looking at the block structure of the transition matrix, here's for example $$k=4$$:

$$A_4 = \left(\begin{array}{rrrr|rrr|rr|r} 1 & 2 & 2 & 2 & 1 & 2 & 2 & 1 & 2 & 1 \\ 0 & 2 & 2 & 2 & 1 & 2 & 2 & 1 & 2 & 1 \\ 0 & 0 & 2 & 2 & 0 & 2 & 2 & 1 & 2 & 1 \\ 0 & 0 & 0 & 2 & 0 & 0 & 2 & 0 & 2 & 1 \\ \hline 0 & 0 & 0 & 0 & 1 & 2 & 2 & 1 & 2 & 1 \\ 0 & 0 & 0 & 0 & 0 & 2 & 2 & 1 & 2 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 2 & 1 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 1 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right)$$

I was able to come up with this $$O(nk^2)$$ algorithm.

We need to find $$A^n \bf 1$$ (its first component is the solution). Do this by initializing the vector $$v_0 = \bf 1$$ and iteratively computing $$v_{j+1} = Av_j$$. Start the computation of $$v_{j+1}$$ from the last component upwards and notice that the row $$i$$ of the matrix is mostly equal (in the blocks to the left of the diagoal one) to the corresponding row one block-level below. (To see why this is true look at the states $$(m, M)$$ and $$(m, M+1)$$). Now to do the computation, keep a running total for the current diagonal block and add the rest from the corresponding (already calculated) value from $$v$$.

• Comments are not for extended discussion; this conversation has been moved to chat. Commented Jul 29, 2022 at 2:58

Not an answer but an elaboration on P. Quinton's remark.

A pair of sequences $$a$$ and $$b$$ is solvable if and only if the pair of sequences $$(\min (a_1,b_1),\ldots, \min(a_n,b_n))\quad\mbox{and}\quad (\max (a_1,b_1),\ldots,\max(a_n,b_n))$$ is solved.

Proof sketch. $$\Rightarrow$$ Say $$\min (a_1,b_1) > \min (a_2,b_2)$$, then $$a_1,b_1 > \min (a_2,b_2)$$ contradicting solvability. Similar argument for the maximums. $$\Leftarrow$$ Winning strategy is clear.

Call a pair of sequences a pair of min/max sequences if it is invariant with respect to the min/max strategy. A pair of min/max sequences can be scrambled in $$2^n$$ different ways (for each index either swap or no swap). So the number of all solvable pairs of sequences is bounded above by $$2^nP(n,k)$$, where $$P(n,k)$$ is the number of pairs of min/max sequences of length $$n$$ and bound $$k$$.

There is a caveat. A pair of constant and equal sequences, for instance, is invariant with respect to scrambling. I don't know how to efficiently account for the $$a_i=b_i$$ cases that will otherwise lead to considerable overestimation.

• I don’t see how it matters that they can be solved in several ways? We start with the min/max sequences, which divides the initial sequence into equivalence classes. I.e. in your example, we would be looking at $(0,0,1)(1,1,2)$, and from that count both $(0,1,1)(1,0,2)$ and $(1,1,1)(0,0,2)$. It shouldn’t matter that the latter is already solved. However, we do need to somehow deal with the cases where $a_i=b_i$. Without those, we could just say (number of solved min/max sequences)$\cdot2^n$. Commented Jul 23, 2022 at 7:16
• @Milten Ah ok, you are identifying sequences if they lead to the same min/max sequences whether or not either of them is already solved. Commented Jul 23, 2022 at 7:23
• Exactly, that’s what I thought Commented Jul 23, 2022 at 7:27
• @Milten Thought about it some more, revised. I understand now what the problem is, but don't know how to solve. Commented Jul 23, 2022 at 8:13