Understanding two "triangular" sequences

Question

Just playing around doodling today and I happened across two related sequences of numbers and I'm reaching out to understand what exactly is going on.

Sequence 1

The $n$th term of Sequence 1, $a_n$, is created by (illustration follows):

• Writing $1,\ldots,n$, then $n-1,\ldots,1$ as the angled sides of an isosceles triangle.
• Cells to the left of $n$ are equal to the sum of the two numbers below and to the left; cells to the right of $n$ are equal to the sum of the two numbers below and to the right.
• Cells above $n$ are equal to the sum of the three numbers to the right, left, and below.
• $a_n$ is the entry in the final cell--directly above $n$ and in line with both 1s.

For example, when $n=3$ we can fill in the triangle recursively like so:

1       1    1 3   3 1     1 3 13 7 1
  2   2   ->   2 7 2   ->    2 7  2   -> a_3 = 13
    3            3             3

The first 7 terms of $a_n$ are 1, 4, 13, 36, 91, 218, and 505. This came up in OEIS as A221882:

The number of order-preserving or order-reversing full contraction mappings of an $n$-chain

With general form: $a_n=(n+1)2^{n-1}-n$.

For Sequence 1, I've got two questions:

1. How could one prove the general form from the construction of $a_n$ that I've given?
2. What is the relationship of this triangular sequence to the sequence described? (I have no idea what that description means) -or- is there any practical appearance of this sequence?

Sequence 2

Sequence 2, $b_n$, is almost identical to Sequence 1, except that on the right-hand side we continue counting up instead of counting down, that is, we fill in the bottom edges of the triangle with $1,\ldots,n,\ldots,2n-1$, then proceed to calculate $b_n$ as the final filled cell:

1       5    1 3   9 5     1 3 21 9 5
  2   4   ->   2 9 4   ->    2 9  4   -> b_3 = 21
    3            3             3

The first 7 terms of $b_n$ are 1, 6, 21, 60, 155, 378, and 889. This came up in OEIS as A066524; there's no simple description of this one. One of the candidate matches involves triangles, but I think constructed in a different way:

Form a triangle in which interior members $T(i,j) = T(i-1,j-1) + T(i-1,j)$. The exterior members are given by $1,2,3,\ldots,2n-1$: $T(1,1)=n, T(2,1)=n-1, T(3,1)=n-2, \ldots, T(n,1)=1$ and $T(2,2)=n+1, T(3,3)=n+2, ..., T(n,n)=2n-1$. The sum of all members will reproduce this sequence. For example, with $n=4$ the exterior members are 1 to 7: row(1)=4; row(2)=3,5; row(3)=2,8,6; row(4)=1,10,14,7. The sum of all these members is 60, the fourth term in the sequence. - J. M. Bergot, Oct 16 2012

The closed form for this is: $$b_n=n(2^n-1)$$ My questions for Sequence 2 are:

1. How can one prove the closed form above? Is there a direct relationship to $a_n$ above?
2. What is the relationship between this and the other appearances of this sequence mentioned on OEIS? Any practical use?

Answer 1

Answer to the First Question for Sequence Two

Let $b_n=n2^n$. Then, we have

$$\begin{align} b_n-2b_{n-1}&=n2^n-2(n-1)2^{n-1}\\\\ &=2^n \end{align}$$

Note that we can add to $b_n$ any multiple of $2^n$ and satisfy the difference equation $b_n-2b_{n-1}=2^n$. Therefore, the general solution to the difference equation $b_n-2b_{n-1}=2^n$ is given by

$$b_n=n\,2^n+b_0\,2^n$$

Answer 2

For now I’ll deal only with the first question. What follows works, but it’s not at all elegant; I haven’t time now to clean it up nicely, and in any case I thought that it might be useful to see an argument that for the most part follows the way in which I approached the problem.

Let me first modify the construction slightly. For each $n$ we’ll build a triangle like this:

$$\begin{array}{ccc} 1&\\ 2&t_{2,2}^{(n)}\\ 3&t_{3,2}^{(n)}&t_{3,3}^{(n)}\\ \vdots\\ n-1&t_{n-1,2}^{(n)}&t_{n-1,3}^{(n)}&\ldots&t_{n-1,n-1}^{(n)}\\ n&t_{n,2}^{(n)}&t_{n,3}^{(n)}&\ldots&t_{n,n-1}^{(n)}&t_{n,n}^{(n)} \end{array}$$

Each triangle is filled from top to bottom and left to right according to the recurrences

$$t_{k,\ell}^{(n)}=t_{k,\ell-1}^{(n)}+t_{k-1,\ell-1}^{(n)}$$

if $2\le\ell\le k< n$, and

$$t_{n,\ell}^{(n)}=t_{n,\ell-1}^{(n)}+2t_{n-1,\ell-1}^{(n)}$$

if $2\le\ell\le n$. It’s not hard to check that $a_n=t_{n,n}^{(n)}$. Here are the triangles for $n=3$ and $n=4$:

$$\begin{array}{ccc} 1\\ 2&3\\ 3&7&13\\ & \end{array}\qquad\qquad \begin{array}{ccc} 1\\ 2&3\\ 3&5&8\\ 4&10&20&36 \end{array}$$

In this form it’s clear that the first $n-2$ rows of the triangle for $n+1$ are identical to the first $n-1$ rows of the triangle for $n$.

Now consider the infinite triangle constructed according to the first recurrence. Here are its first six rows:

$$\begin{array}{ccc} 1\\ 2&3\\ 3&5&8\\ 4&7&12&20\\ 5&9&16&28&48\\ 6&11&20&36&64&112\\ \end{array}$$

If we denote the entry in row $r$, column $c$ (indexed from $1$) by $T(r,c)$, we have $T(r,1)=r$ for $r\in\Bbb Z^+$ and $T(r,c)=T(r,c-1)+T(r-1,c-1)$ for $2\le c\le r$. It’s not hard to show by induction that $T(r+1,c)=T(r,c)+2^{c-1}$ for $r\ge c$. From that we can further show by induction on $r$ that $T(r,r)=(r+1)2^{r-2}$ for $r\ge 2$, and the closed form $a_n=(n+1)2^{n-1}-n$ will follow if we can show that $a_n=2T(n,n)-n$.

Consider the triangle for computing $a_n=t_{n,n}^{(n)}$; for $1\le c\le r\le n-1$ we have $t_{r,c}^{(n)}=T(r,c)$. Thus, for $1\le c<n$ we must have

$$t_{n,c+1}^{(n)}=t_{n,c}^{(n)}+2t_{n-1,c}^{(n)}=t_{n,c}^{(n)}+2T(n-1,c)\;.$$

Now clearly

$$t_{n,1}^{(n)}=n=2n-n=2T(n,1)-n\;.$$

Suppose that $1\le c<n$, and

$$t_{n,c}^{(n)}=2T(n,c)-n\;;$$

then

$$\begin{align*} t_{n,c+1}&=\big(2T(n,c)-n\big)+2T(n-1,c)\\ &=2\big(T(n,c)+T(n-1,c)\big)-n\\ &=2T(n,c+1)-n\;, \end{align*}$$

so by induction we have

$$a_n=t_{n,n}^{(n)}=2T(n,n)-n\;,$$

as desired.

I’ve not yet had time to see how the calculation directly corresponds to the sequence OEIS A221882. Indirectly it’s clear that it must be the same sequence once we know that it has the same closed form. In the first part of this answer I’ve justified that form for your sequence. The justification for OEIS A221882 can be found in A.D. Adeshola and A. Umar, Combinatorial results for certain semigroups of order-preserving full contraction mappings of a finite chain; the notation is quite involved and takes some getting used to, but the results themselves aren’t terribly difficult. Specifically, it’s Corollary $\mathbf{3.6}$. (I suspect that with some effort a direct correspondence can be dug out of the results in this paper; if I have time, I’ll give it a go.)

Finally, here is a brief explanation of what is being counted by OEIS A221882. As usual let $[n]=\{1,\ldots,n\}$. In this context you can think of an $n$-chain as simply the sequence $\langle 1,2,\ldots,n\rangle$. You can think of a full mapping as an $n$-tuple $\langle d_1,\ldots,d_n\rangle$ of elements of $[n]$; the mapping in question is $k\mapsto d_k$. It is order-preserving if $d_1\le d_2\le\ldots\le d_n$ and order-reversing if $d_1\ge d_2\ge\ldots\ge d_n$. Finally, it’s a contraction if $|d_k-d_\ell|\le|k-\ell|$ for each $k,\ell\in[n]$.

As an example, take $n=3$. For simplicity I’ll write the $3$-tuples without commas. The order-preserving or order-reversing full contraction mappings of the $3$-chain $123$ are:

$$111,112,211,122,221,123,321,222,223,233,322,332,333\;.$$

(The three constant mappings are both order-preserving and order-reversing.)

Added: I can now add a more direct relationship between your sequence and OEIS A221882. It’s not hard to show (and is shown in the paper by Adeshola and Umar) that the order-preserving full contractions on $[n]$ are essentially just the $n$-tuples $\langle d_1,\ldots,d_n\rangle$ of elements of $[n]$ such that $d_1\le d_2\le\ldots\le d_n$, and $d_{k+1}-d_k\le 1$ for $k=1,\ldots n-1$. I will call such $n$-tuples continuous, since they have no gaps.

Let $\langle b_n:n\in\Bbb N\rangle$ be OEIS A221882, and let $c_n$ be the number of continuous order-preserving $n$-tuples $\langle d_1,\ldots,d_n\rangle$ of elements of $n$; clearly there are also $c_n$ continuous order-reversing $n$-tuples of elements of $[n]$, and the $n$ constant $n$-tuples are both order-preserving and order-reversing, so $b_n=2c_n-n$. I’ll show that $c_n=T(n,n)$ and hence that $b_n=2T(n,n)-n=a_n$. Thus, the auxiliary triangular array $T$ provides a fairly natural connection between your sequence and OEIS A221882.

Suppose for some $n$ that $c_n=T(n,n)$. Each continuous order-preserving $n$-tuple $\langle d_1,\ldots,d_n\rangle$ from $[n]$ can be extended to two continuous order-preserving $(n+1)$-tuples from $[n+1]$ by appending either $d_n$ or $d_n+1$; this accounts uniquely for every continuous order-preserving $(n+1)$-tuple from $[n+1]$ whose penultimate term is not $n+1$. It only remains to count the continuous order-preserving $n$-tuples $\langle d_1,\ldots,d_{n-1},n\rangle$ from $[n+1]$ whose last term is $n+1$.

The $n$-tuple $\langle d_1,\ldots,d_{n-1},n\rangle$ is naturally divided into blocks of identical terms. Say that there are $m$ blocks, of lengths $\ell_1,\ldots,\ell_m$; clearly $\ell_1+\ldots+\ell_m=n$; continuity of the $n$-tuple ensures that it is uniquely determined by the numbers $m$ and $\ell_1,\ldots,\ell_m$.

For example, if $n=7$, $m=3$, $\ell_1=2$, $\ell_2=1$, and $\ell_3=4$, the $7$-tuple must be $\langle 5,5,6,7,7,7,7\rangle$.

Clearly $\ell_1+\ldots+\ell_m$ is a composition of $n$. Conversely, each composition of $n$ determines a unique continuous order-preserving $n$-tuple from $[n+1]$ whose last term is $n+1$. It’s well known that $n$ has $2^{n-1}$ compositions, so there are $2^{n-1}$ such $n$-tuples. Thus,

$$\begin{align*} c_{n+1}&=2c_n+2^{n-1}\\ &=2T(n,n)+2^{n-1}\\ &=(n+1)2^{n-1}+2^{n-1}\\ &=(n+2)2^{n-1}\\ &=T(n+1,n+1)\;, \end{align*}$$

and the result follows by induction.

Added₂: The relationship between the two sequences is fairly straightforward. I’ll illustrate for the case $n=4$. Subtract the triangular array for the first sequence from that for the second:

$$\begin{align*} \begin{array}{ccc} 1&3&8&60&24&13&7\\ &2&5&28&11&6\\ &&3&12&5\\ &&&4 \end{array}\quad&-\quad \begin{array}{ccc} 1&3&8&36&8&3&1\\ &2&5&20&5&2\\ &&3&10&13\\ &&&4 \end{array}\\\\ &=\quad\begin{array}{ccc} 0&0&0&24&16&10&6\\ &0&0&8&6&4\\ &&0&2&2\\ &&&0 \end{array} \end{align*}$$

In general it’s clear that the lefthand wings of the two triangles will always be identical, so the lefthand wing of the difference triangle will contain only $0$s. It’s also not hard to check that the righthand edge of the difference triangle for $n$ will be $0,2,4,\ldots,2(n-1)$ from bottom to top.

Now remove the lefthand wing of $0$s, rotate the remaining triangle $45^\circ$ clockwise, and flip it over the horizontal axis:

$$\begin{array}{ccc} 0&&2&&4&&6\\ &2&&6&&10\\ &&8&&16\\ &&&24 \end{array}$$

The number at the bottom is $b_4-a_4$ in your notation, and each entry in this triangle is the sum of the two numbers immediately above it.

More generally, the process yields for $n$ a triangle whose top row is $0,2,4,\ldots,2(n-1)$ and that is constructed like Pascal’s triangle. This construction ensures that the bottom number, which in your notation is $b_n-a_n$, is given by

$$\begin{align*} b_n-a_n&=\sum_{k=0}^{n-1}2k\binom{n-1}k\\ &=2\sum_{k=0}^{n-1}k\binom{n-1}k\\ &=2(n-1)\sum_{k=0}^{n-1}\binom{n-2}{k-1}\\ &=2(n-1)2^{n-2}\\ &=(n-1)2^{n-1}\;. \end{align*}$$

Since we already know that $a_n=(n+1)2^{n-1}-n$, we have

$$b_n=a_n+(n-1)2^{n-1}=(n+1)2^{n-1}-n+(n-1)2^{n-1}=n\left(2^n-1\right)\;.$$