## Return to Answer

4 slight improvement

But I don't have a clear proof that the sequence always terminates in a loop. – Martin Erickson

Here is a proof that the sequence always terminates in a loop.

Let $A', A, A, B$ be three consecutive arrays in the sequence, and c(X) denote the number of columns in array X.

Claim 1. $c(A) \leq c(B)$.

Proof. Trivial.

Claim 2. $$\sum_{i=1}^{c(B)} B[2,i] = 2 c(A).$$

Proof. By the sequence definition, the second row of each subsequent array contains the multiplicities of elements of the preceding array, and thus the sum of multiplicities equals the total number of elements in the preceding array. QED

Now, let $A', A, B$ be three consecutive arrays in the sequence.

Claim 3. Let $m\geq 7$ 5$be an odd integer such that no element$B$exceeds$m$. Then no element larger than$m$can appear in subsequent arrays (while their size may eventually grow up to$2\times m$). Proof. Assume that a larger element$m'\geq m+1$appears. Without loss of generality suppose that this happens in (the bottom row of) array$C$that immediately follows$B$. By Claim 1, we have$c(A)\leq c(B)\leq c(C)\leq m$. By Claim 2 and since$C$contains$m'\geq m+1$(while the other elements are at least 1), $$m + c(C) \leq m' + (c(C)-1) \leq \sum_{i=1}^{c(C)} C[2,i] = 2c(B) \leq 2c(C)\leq 2m$$ implying that$c(B)=c(C)=m$and$m'=m+1$. Therefore, the top row of both$B$and$C$contains all integers from 1 to$m$. The bottom row of$C$consists of one number$m'=m+1$and$m-1$ones. If$m'$appear under the number$k$, then bottom row of$B$contains at least$m$numbers$k$, whose sum must not exceed$2c(A)\leq 2m$, implying that$k\leq 2$. Consider two cases: If$k=1$then the bottom row of$B$consists of all ones, implying that the elements of$A$are the integers from$1$to$m$without repetitions, and hence$m$is even, a contradiction proving that no element larger than$m$may appear. If$k=2$then the bottom row of$B$consists of all twos, implying by Claim 2 that$c(A)=m$. Therefore, c(A)=m$ and $A$ contains in each row all integers from 1 to $m$ two times with so that the sum of its bottom row not less than equal $$1+1+2+2+\dots+(m-1)/2+(m-1)/2+(m+1)/2 1+2+\dots+m = (m+1)^2/4.$$ m(m+1)/2.$The inequality$(m+1)^2/4 m(m+1)/2 \leq 2c(A') \leq 2c(A) = 2m$then implies that$m\leq 5$3$, that is not the case.

QED

Claim 4. The sequence always terminates in a loop.

Proof. By Claim 3, there exists an integer $m$ such that elements of the arrays in the sequence do not exceed $m$. By Claim 1 and since $c(X)\leq m$ for all $X$ in the sequence, the size (and hence the top row) of arrays stabilizes to a certain $c(X)=n$. Then by Claim 2, the sum of the bottom row stabilizes to $2n$. Since, there are only a finite number of compositions of $2n$ into the sum of $n$ positive integers (namely, $\binom{2n-1}{n}$), there exists only a finite number of distinct arrays that may appear after the size stabilization, implying that the sequence loops. QED

Claim 5. The length of the terminal loop is bounded by $\binom{2m-1}{m}$, where $m$ is defined as in Claim 3.

Proof. See proof of Claim 4.

3 corrected

Let $A,B$ A', A, B$be three consecutive arrays in the sequence, and c(X) denote the number of columns in array X. Claim 3. Let$m$m\geq 7$ be an odd integer such that no element $B$ exceeds $m$. Then no element larger than $m$ can appear in subsequent arrays (while their size may eventually grow up to $2\times m$).

The element $m'=m+1$ may appear in the bottom row of $C$ nowhere else but consists of one number $m'=m+1$ and $m-1$ ones. If $m'$ appear under the number 1, while the remaining elements of this $k$, then bottom row are all 1of $B$ contains at least $m$ numbers $k$, whose sum must not exceed $2c(A)\leq 2m$, implying that $k\leq 2$. Then Consider two cases:

If $k=1$ then the bottom row of $B$ must consist consists of all ones, implying that the elements of $A$ are the integers from $1$ to $m$ without repetitions, and hence $m$ is even, a contradiction proving that no element larger than $m$ may appear.

If $k=2$ then the bottom row of $B$ consists of all twos, implying by Claim 2 that $c(A)=m$. Therefore, $A$ contains all integers from 1 to $m$ two times with the sum of bottom row not less than$$1+1+2+2+\dots+(m-1)/2+(m-1)/2+(m+1)/2 = (m+1)^2/4.$$The inequality $(m+1)^2/4 \leq 2c(A') \leq 2m$ then implies that $m\leq 5$, that is not the case.

2 added 31 characters in body; added 152 characters in body

But I don't have a clear proof that the sequence always terminates in a loop. – Martin Erickson

Here is a proof that the sequence always terminates in a loop.

Let $A,B$ be consecutive arrays in the sequence, and c(X) denote the number of columns in array X.

Claim 1. $c(A) \leq c(B)$.

Proof. Trivial.

Claim 2. $$\sum_{i=1}^{c(B)} B[2,i] = 2 c(A).$$

Proof. By the sequence definition, the second row of each subsequent array contains the multiplicities of elements of the preceding array, and thus the sum of multiplicities equals the total number of elements in the preceding array. QED

Claim 3. Let $m$ be an odd integer such that no element $B$ exceeds $m$. Then no element larger than $m$ can appear in subsequent arrays (while their size may eventually grow up to $2\times m$).

Proof. Assume that a larger element $m'\geq m+1$ appears. Without loss of generality suppose that this happens in (the bottom row of) array $C$ that immediately follows $B$. By Claim 1, we have $c(A)\leq c(B)\leq c(C)\leq m$.

By Claim 2 and since $C$ contains $m'\geq m+1$ (while the other elements are at least 1), $$m + c(C) \leq m' + (c(C)-1) \leq \sum_{i=1}^{c(C)} C[2,i] = 2c(B) \leq 2c(C)\leq 2m$$ implying that $c(B)=c(C)=m$ and $m'=m+1$.

Therefore, the top row of both $B$ and $C$ contains all integers from 1 to $m$. The element $m'=m+1$ may appear in the bottom row of $C$ nowhere else but under the number 1, while the remaining elements of this row are all 1. Then the bottom row of $B$ must consist of all ones, implying that the elements of $A$ are the integers from $1$ to $m$ without repetitions, and hence $m$ is even, a contradiction proving that no element larger than $m$ may appear. QED

Claim 4. The sequence always terminates in a loop.

Proof. By Claim 3, there exists an integer $m$ such that elements of the arrays in the sequence do not exceed $m$. By Claim 1 and since $c(X)\leq m$ for all $X$ in the sequence, the size (and hence the top row) of arrays stabilizes to a certain $c(X)=n$. Then by Claim 2, the sum of of the bottom row stabilizes to 2n. $2n$. Since, there are only a finite number of composition compositions of $2n$ into the sum of $n$ positive integers , (namely, $\binom{2n-1}{n}$), there exists only a finite number of distinct arrays that may appear after the size stabilization, implying that the sequence loops. QED

Claim 5. The length of the terminal loop is bounded by $\binom{2m-1}{m}$, where $m$ is defined as in Claim 3.

Proof. See proof of Claim 4.

1