Count number of pair of sequences

Question

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$.

Answer 1

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.

Answer 2

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$.