Cathodoluminescence of N-doped SnO₂ nanowires and microcrystals

1.   Introduction

In recent years, there has been tremendous interest in developing new combinatorial model for classical sequences, such as the Catalan numbers ^[1], the Euler numbers ^[2,3,4,5] and so on. In a paper by Guo-Niu Han, he introduced "a large family of combinatorial objects, called standard puzzles" ^[6]. After computing a large number of standard puzzle sequences, he found that only a small part of them already appear in OEIS ^[7], and then he gave combinatorial proofs of some of them. In 2020, Donald Knuth ^[8] was concerned with a special case of standard puzzles, the support of which is a set of "vortices—that is, it travels a cyclic path from smallest to largest, either clockwise or counterclockwise". In the end, he found and proved that this sequence is exactly $ 2n U_n $, in which $ U_n $ is a familiar sequence in OEIS ^[7], entry A122647.

However, in spite of quite a number of contributions dealing with the standard puzzle sequences, there are still a great many standard puzzles that have not been enumerated yet. In this paper, we propose a skeleton model, which leads us to proofs for a series of standard puzzle sequences and additionally we get some equations in enumerating problems of standard puzzle.

One question raised in Han's article is whether there is a standard puzzle sequence in which the secant sequence exists. Using our skeleton model, we define simple pieces in Section 3.1, which are particular sets of standard pieces. And then we find the sequence of a simple piece $ \{A, B, D, G, H\} $ (by the notation in ^[6]) is exactly the secant sequence. Besides we divide all simple pieces into four classes 1, 2, 3 and 4 according to the relations in each columns. Each class has 20 kinds of simple pieces in it (we count it in the penultimate paragraph of Section 3.1) and the standard puzzle sequences of all 80 simple pieces have already been enumerated. (Some are trivial or proved by Han ^[6], while the others are shown in this paper.) In addition, we enumerate the sequences of standard puzzles, which satisfy the following conditions respectively (only one case in (1) and (2) hasn't been enumerated):

(1) the union of a $ 1 $-simple or $ 4 $-simple piece and a set of $ B_i $ or $ C_i $ forms its support;

(2) the union of a $ 1 $-simple and a $ 4 $-simple piece and a set of $ B_i $ or $ C_i $ forms its support.

We let $ \alpha_i $ and $ \beta_i $ be a $ 1 $-simple piece and $ 4 $-simple piece respectively according to the order in Table 1, for $ i $ in $ \{1, 2, 3, 4\} $. Then what we enumerate in this paper can be formalized in the following formulas, that is, we enumerate the sequence of each term of the formulas when it is fully expanded, in which $ 1 $ is the empty set.

So the number of standard puzzle sequences that our skeleton model can enumerate is:

case (1) $ (20-1)\cdot2\cdot(2^6\cdot2-1) = 4826 $;

case (2) $ (20-1)\cdot(20-1)\cdot(2^6\cdot2-1) = 45847 $.

To sum up, we enumerate $ 4826+45847 = 50673 $ standard puzzle sequences using this skeleton model.

This paper is organized as follows. We devote Section 2 to recalling the definition of standard puzzles and define some notation to be used in this paper. In Section 3, we propose the skeleton model and by this model we define simple pieces and enumerate the sequences of all kinds of simple pieces. Besides, we enumerate some other standard puzzles by the skeleton model in Section 4. Finally, the proofs of some identities for standard puzzle sequences are presented in Section 5.

2.   Definition and notation

Although Han proposed the definition of the standard puzzle combinatorial object in ^[6], we recall it here to make the paper self-contained.

Definition 2.1. A piece denotes a square that has four numbers, called labels, written on its corners. And a puzzle is a connected arrangement of pieces in the $ \mathbb{Z} \times \mathbb{Z} $-plane such that the joining corners of all the pieces have the same labels. A puzzle such that the set of all its labels is simply $ \{1, 2, \ldots, m\} $ is called a standard puzzle. In this case, $ m $ is the number of vertices of the puzzle.

Remark 2.1. In this paper, we focus our attention on the standard puzzles of a special shape, which are $ n $ standard pieces concatenated in a row. We call these puzzles standard $ n $-puzzles.

By definition, we can see that the four labels of a piece occurring in a standard puzzle are distinct. This means that we can replace the four labels with $ \{1, 2, 3, 4\} $ respecting the label ordering which yields a standard piece. We represent this operation with a reduction. Apparently, there are $ 4! = 24 $ different standard pieces. All of these $ 24 $ standard pieces form a set, called $ \mathcal{S}\mathcal{P} $. For convenience, we have divided the $ 24 $ types of standard pieces into four categories $ A $, $ B $, $ C $, and $ D $ according to the order of two numbers in each column. And within each category, we have labeled them with numbers 1 to 6, as shown in Table 2.

Definition 2.2. Given a standard puzzle $ \alpha $, a set $ \mathcal{P} $ of standard pieces is called a support of the puzzle $ \alpha $ if the reduction of each piece occurring in the puzzle $ \alpha $ is an element of $ \mathcal{P} $ and the minimal support of $ \alpha $ is the set of all different pieces of $ \alpha $ after reduction.

For convenience, standard puzzles will be represented by two-row matrices. For example, $ \left[

$$\begin{smallmatrix}3 & 6 & 8 & 7\\ 1 & 2 & 4 & 5\end{smallmatrix}$$ \right] $ stands for Figure 1. This puzzle contains three pieces, but only two of them are different as standard pieces which are $ \left[ $$\begin{smallmatrix} 3 & 4\\1 & 2 \end{smallmatrix}$$ \right] $ and $ \left[ $$\begin{smallmatrix} 4 & 3\\1 & 2 \end{smallmatrix}$$ \right] $. So the minimal support is the set $ \left\{ \left[ $$\begin{smallmatrix} 3 & 4\\1 & 2 \end{smallmatrix}$$ \right], \left[ $$\begin{smallmatrix} 4 & 3\\1 & 2 \end{smallmatrix}$$ \right]\right\} $ and each set of pieces containing these two pieces is a support of the puzzle.

Remark 2.2. In Table 2, the three columns of each expression represent the notation used in this paper, the notation used in Guo-Niu Han's paper ^[6] and the matrix representation of standard pieces respectively. Additionally, notice that all the standard pieces $ B_i $ and $ C_i $ $ (1\leq i\leq6) $ have opposite relations in the left and right columns so we call $ B_i $ and $ C_i $ a $ B $-converter and $ C $-converter respectively.

Then, let us define the standard puzzle sequence.

Definition 2.3. Let $ \mathcal{P} $ be a subset of $ \mathcal{S}\mathcal{P} $. For $ n\in \mathbb{N}^+ $, we denote by $ S_n(\mathcal{P}) $ the set of the standard $ n $-puzzles, each of which has $ \mathcal{P} $ as its support, and let $ s_n(\mathcal{P}): = \bigl|S_n(\mathcal{P})\bigr| $ be the cardinality of $ S_n(\mathcal{P}) $. In addition, we call $ \{s_n(\mathcal{P})\}_{n\ge 1} $ the standard puzzle sequence of $ \mathcal{P} $.

Example 2.1. Let $ \mathcal{P} = \{A_2, A_3\} = \bigl\{ \left[

$$\begin{smallmatrix}3 & 4 \\ 1 & 2\end{smallmatrix}$$ \right], \left[ $$\begin{smallmatrix}2 & 4 \\ 1 & 3\end{smallmatrix}$$ \right] \bigr\} $. Then,

Indeed, the standard puzzle sequence of $ \{A_2, A_3\} $ is shown in ^[6] to be the sequence of Catalan numbers:

Moreover, Guo-Niu Han defined three basic transformations and now we rephrase them here using our notation. The original statement of these transformations can be found in ^[6], which are as follows:

(T1) exchanging left column and right column in every piece;

(T2) exchanging top row and bottom row in every piece;

(T3) replacing each label $ a $ by $ (5 - a) $ in every piece.

Definition 2.4. (1) We denote by $ F_1 $ the map: $ \mathcal{S}\mathcal{P}\mapsto \mathcal{S}\mathcal{P} $, which sends the element $ A_i, B_i, C_i $ and $ D_i $ to $ A_{i+3}, C_{i+3}, B_{i+3} $ and $ D_{i+3} $ respectively, for $ i\in\{1, 2, 3, 4, 5, 6\} $, and we make the convention that $ X_j $ is equal to $ X_{k} $ iff $ j \equiv k\pmod 6 $ $ (X\in \{A, B, C, D\}) $;

(2) we denote by $ F_2 $ the map: $ \mathcal{S}\mathcal{P}\mapsto \mathcal{S}\mathcal{P} $, which sends the element $ A_i, B_i, C_i $ and $ D_i $ to $ D_i, C_i, B_i $ and $ A_i $ respectively, for $ i \in \{1, 2, 3, 4, 5, 6\} $;

(3) we denote by $ F_3 $ the map: $ \mathcal{S}\mathcal{P}\mapsto \mathcal{S}\mathcal{P} $, which sends the element $ X_i $ to $ Y_j $, for $ X\in\{A, B, C, D\} $, $ i \in \{1, 2, 3, 4, 5, 6\} $. $ Y $ and $ j $ are defined as follows.

This definition naturally gives rise to the following proposition.

Proposition 2.1. For a map $ F_i (i\in\{1, 2, 3\}) $, let $ \mathcal{P} $ be a subset of $ \mathcal{S}\mathcal{P} $, and we have:

Proof. By the definition of Guo-Niu Han's transformations, we can easily see that these operations are all bijections between $ S_n(\mathcal{P}) $ and $ S_n(F_i (\mathcal{P})) $. Hence the cardinality $ s_n(\mathcal{P}) $ is equal to $ s_n(F_i(\mathcal{P})) $.

3.   Simple puzzles defined by the skeleton model

In this section, we will propose the definition of a skeleton and simple piece. And then we will enumerate the standard puzzle sequence of all kinds of simple piece.

3.1.   The definition of a skeleton model and a simple puzzle

Notice that a standard puzzle can be seen as a graph. And if we use the directions on a graph to represent the relations between numbers in a standard puzzle, we can get a directed graph. Then the idea of the skeleton model is born. In fact this idea is inspired by a proof in ^[6]. Here are some definitions of a skeleton and a simple piece.

Definition 3.1. Given a simple directed graph with four vertices $ a $, $ b $, $ c $ and $ d $, we fix the four vertices on a square as shown in Figure 2. We call this graph a basic skeleton (denoted by $ B(a, b, c, d) $), if it satisfies the following conditions.

(1) It doesn't have a directed circle.

(2) If there are more than one directed path between two vertices, then they have the same length.

Remark 3.1. By definition, we can see that each basic skeleton $ B(a, b, c, d) $ is the Hasse diagram of a certain poset. We call this poset the poset of $ B $. The definition of the Hasse diagram can be seen in ^[9].

Definition 3.2. A basic skeleton is called an $ i $-basic skeleton, if it meets the following condition $ (i) $, for $ 1\leq i \leq 4 $:

(1) there is a directed path from $ b $ to $ a $ and from $ d $ to $ c $ respectively;

(2) there is a directed path from $ b $ to $ a $ and from $ c $ to $ d $ respectively;

(3) there is a directed path from $ a $ to $ b $ and from $ d $ to $ c $ respectively;

(4) there is a directed path from $ a $ to $ b $ and from $ c $ to $ d $ respectively.

Definition 3.3. Given an $ i $-basic skeleton $ B(a, b, c, d) $, an $ i $-simple piece generated by $ B $ is a subset of $ \mathcal{S}\mathcal{P} $ (denoted by $ \mathcal{P}(B) $). A standard piece is in $ \mathcal{P}(B) $ if and only if its poset is a linear extension of the poset of $ B $. Then a puzzle which has $ \mathcal{P}(B) $ as its support is a simple puzzle generated by $ B $.

Example 3.1. Let $ B $ be a $ 1 $-basic skeleton as shown in Figure 3. Then a $ 1 $-simple piece generated by $ B $ is $ \mathcal{P}(B) = \{A_1, A_2, A_3, A_4, A_5\} $ and each standard puzzle of $ S(\mathcal{P}(B)) $ is a simple puzzle generated by $ B $.

Remark 3.2. Similar to the definition of the basic skeleton, we can draw a Hasse diagram to descibe the relations between numbers in certain standard $ n $-puzzle. If there is a directed path from $ x $ to $ y $ it means $ y > x $. We call this graph a skeleton. So a skeleton is the concatenation of several basic skeletons.

Definition 3.4. Let $ \mathcal{P} $ be a subset of $ \mathcal{S}\mathcal{P} $. $ \mathcal{P} $ has a skeleton if and only if there exists a skeleton $ \mathcal{K} $ satisfing the following conditions:

(1) each element of $ S_n(\mathcal{P}) $ meets the relations of $ \mathcal{K} $;

(2) each standard $ n $-puzzle that meets the relations of $ \mathcal{K} $ is an element of $ S_n(\mathcal{P}) $.

Remark 3.3. By definitions, each simple piece has a skeleton.

For example, in Example 3.1 the skeleton of $ \{A_1, A_2, A_3, A_4, A_5\} $ is shown in Figure 4.

In addition, both a $ 2 $-simple piece and a $ 3 $-simple piece have opposite relations in the left and right columns. This means that we can not concatenate any one of them in a line. So for a $ 2 $-simple or $ 3 $-simple piece $ \mathcal{P}(B) $, $ s_n(\mathcal{P}(B)) = 0 $ for $ n\geq 2 $. And by Proposition 2.1, for any $ 4 $-simple piece $ \mathcal{P}(B) $, we can find a $ 1 $-simple piece $ F_2(\mathcal{P}(B)) $such that

Therefore, in this section we will concentrate on $ 1 $-simple puzzles to get the properties of all four kinds of simple puzzles.

By definition, we can learn that there are twenty^* kinds of $ 1 $-simple pieces in total. Besides, we can simply exchange the numbers in column(s) of $ i $-simple piece and get $ j $-simple piece, for any $ i $, $ j $ in $ \{1, 2, 3, 4\} $, and this operation is easily seen to be invertible. So for each $ i $ in $ \{1, 2, 3, 4\} $, the number of $ i $-simple pieces is twenty.

^* By definition of basic skeletons, we just have to think about the four edges in a $ 4 $-vertices digraph except the edges $ ab $ and $ cd $ (see Figure 2). Then we count the number of $ 1 $-simple pieces according to the number of directed edges in the skeletons and it is $ 1+8+9+2 = 20 $.

In the following subsections, we will prove the sequences of all twenty simple pieces as shown in Table 1. (Some proofs have been given by Han in ^[6] or trivial, and we list them at the last column as a remark.)

3.2.   Secant numbers

In Guo-Niu Han's paper ^[6], he found the tangent number sequence occurs in the standard puzzle sequence of $ \{A_1, A_5, B_1, B_2\} $ and "developed a computer programme to generate the puzzle sequences up to order $ \lvert \mathcal{P}\rvert = 4 $" ^[6], finding no secant number sequence. Then he asked a question about whether and where the secant numbers exist.

However, when we are concerned with the standard puzzle sequence of the simple piece in Example 3.1, we were surprised to find that this sequence is exactly the secant sequence. That is the following theorem.

Theorem 3.1. Let $ \mathcal{P} = \{A_1, A_2, A_3, A_4, A_5\} $, then we have,

in which $ S(n) $ is the $ n $-th secant number; see OEIS^[7], entry A000364.

Proof. Firstly, for the $ 1 $-basic skeleton $ B(a, b, c, d) $ as shown in Figure 3. We check the $ i $-simple piece generated by $ B $ and find it is $ \{A_1, A_2, A_3, A_4, A_5\} $ exactly.

Additionally, in 1879 Désiré André ^[2] proved that the secant numbers is the number of down-up permutations of $ [2n] $. Therefore, the aim is to find a one-to-one correspondence between a standard $ n $-puzzle of $ \mathcal{P} $ and a down-up permutation of $ [2n+2] $.

On the one hand, we read the numbers of a standard puzzle of $ \mathcal{P} $ from the top left to the bottom right, through south $ \rightarrow $ northeast $ \rightarrow $ south $ \rightarrow $ northeast $ \ldots $ Therefore, by definition we get a permutation $ \pi $ of length $ 2n+2 $, which satisfies $ \pi(i) > \pi(i+1) $, where $ i = 2k+1 $, and $ \pi(i) < \pi(i+1) $, where $ i = 2k $ ($ k\in\{0, 1, 2, \ldots, n\} $ and we make the convention that $ \pi(0) = 0 $.). So, it's a down-up permutation.

On the other hand, given a down-up permutation of $ [2n+2] $, we can place the permutation at the vertices of the puzzle in the way shown above. Obviously, this puzzle is a simple puzzle of $ \{A_1, A_2, A_3, A_4, A_5\} $.

Hence, the proof is completed.

3.3.   Double factorial of odd and even numbers

In this subsection we are concerned with $ 1 $-basic skeletons as shown in Figure 5(a), (b). After checking the simple pieces generated by them, we find that they are $ \{A_1, A_2, A_3\} $ and $ \{A_1, A_2\} $ respectively.

Theorem 3.2. Let $ \mathcal{P} = \{A_1, A_2, A_3\} $ and $ \mathcal{Q} = \{A_1, A_2\} $, then

In this paper, we present two proofs of this theorem, which are as follows.

3.3.1.   The first method

Proof. To begin with, we observed that each piece of $ S_n(\mathcal{P}) $ and $ S_n(\mathcal{Q}) $ meets the minimum number in its lower left corner. On this basis, the proof of this theorem is constructed.

For Eq (3.2), we put the smallest number one in $ [2n+2] $ on the lower left of the puzzle, and then at the top of the number one, we have $ 2n+1 $ choices from 2 to $ 2n+2 $. After selecting these two numbers in the leftmost column, the second column performs the same action: place the smallest of the remaining numbers at the bottom of the second column and then select one of the remaining numbers and place it on the top of the column, with $ (2n-1) $ options. A clear induction gives $ (2n+1)(2n-1)\cdot\ldots\cdot 3\cdot 1 = (2n+1)!! $ puzzles that meet the above conditions.

Now, all we need to do is prove that the support of puzzles which meet the above properties is accurately $ \{A_1, A_2, A_3\} $. Check all the standard pieces, and pieces satisfying the above conditions are only $ A_1, A_2 $ and $ A_3 $.

So Eq (3.2) has been shown and we can prove Eq (3.3) in a similar way. Notice that each piece of $ S_n(\mathcal{Q}) $ satisfies that the upper-left number is larger than the lower-right number, in addition to the above conditions. Therefore, after setting the number one in the lower left corner, the number above the number one has only $ 2n $ conditions from $ 3 $ to $ 2n+2 $. Then the second column list $ (2n-2) $ possibilities. By recursion, the number of the element in $ S_n(\mathcal{Q}) $ is $ (2n)!! $, which completes the proof of Theorem 3.2.

3.3.2.   The second method

In this subsection, we provide an alternative method for proving Theorem 3.2.

Proof. Proceed by induction on length of $ S_n(\mathcal{P}) $. If $ n = 1 $, then this puzzle is $ A_1 $ or $ A_2 $ or $ A_3 $. So, $ s_1(\mathcal{P}) = 3 = (2\cdot 1+1)!! $. This establishes the base case of the induction. Suppose the claim holds for puzzles of length less than $ k $. Then we construct a $ 1-to-(2n+1) $ map from $ S_{n-1}(\mathcal{P}) $ to $ S_n(\mathcal{P}) $.

For any puzzle of $ S_{n-1}(\mathcal{P}) $, there are $ n $ numbers on the top line. We choose one of them and there are $ n $ different options. Then let's put it on the second line such that it is bigger than the number to its left, and smaller than the number to its right. In other words, rearrange the columns according to the size of the rows below. After the operation, we can see two empty seats in the first row. One of them is the original position of the number taken out, and the other is the empty seat above its new position. After this, we put the two number $ 2n+1 $ and $ 2n+2 $ in these two space in two ways. Additionally, we can put the number $ 2n+1 $ and $ 2n+2 $ to the bottom right and top right corners of this puzzle respectively and then we can get another puzzle in $ S_n(\mathcal{P}) $. Besides, this construction is easily seen to be invertible and then the proof is completed.

To prove Eq (3.3), we need to use the skeleton model in the next section, so the proof of it is postponed until Section 4.1.

3.4.   The sequence in OEIS, entry A227656

Theorem 3.3. Let $ \mathcal{P} = \{A_1, A_2, A_4, A_5\} $. Then we have,

where $ L(n) $ is number of lattice paths from $ \{2\}^n $ to $ \{0\}^n $ using steps that decrement one component by 1 such that for each point $ (p_1, p_2, \ldots, p_n) $ we have $ \bigl|p_{i}-p_{i+1}\bigr| \leqslant 1 $; see OEIS ^[7], entry A227656.

Proof. First of all, we draw the skeleton of $ \{A_1, A_2, A_4, A_5\} $.

The trick of the proof is to find a bijection between any element of $ S_n(\mathcal{P}) $ and the path meeting the above conditions of length $ n+1 $.

Then, we construct a combinatorial proof of bijection. Check the positions of the numbers in the standard puzzle, from $ 1 $ to $ 2n+2 $ one by one. If the number is in column $ i $, we will change $ (p_1, p_2, \ldots, p_i, \ldots, p_{n+1}) $ into $ (p_1, p_2, \ldots, p_i-1, \ldots, p_{n+1}) $. And the initial point is $ \{2\}^n $. This construction is easily seen to be invertible. Then we only need to show this kind of puzzle is exactly $ S_n(\mathcal{P}) $.

Notice that the $ j $-th step of the path is equal to an $ n $-set which count the number greater than $ j $ in each column of an element of $ S_n(\mathcal{P}) $. Then that each point $ (p_1, p_2, \ldots, p_n) $ satisfies $ \bigl|p_{i}-p_{i+1}\bigr| \leqslant 1 $ is the same thing as it that the puzzle satisfies that each number on the top row of the puzzle is greater than the numbers below it and below it's adjacent numbers. Therefore, it is equivalent to it that $ \{A_1, A_2, A_4, A_5\} $ is a support of the puzzle by Figure 6.

3.5.   Fibonacci sequence

In this subsection, we enumerate the standard puzzle sequence of $ \{A_1, B_1, C_1\} $ which is a Fibonacci sequence. Although this puzzle is not one of $ 1 $-simple puzzles, we list it here for Theorem 5.3 to be complete.

Before we state and prove the theorem, we will need a lemma.

Lemma 3.4. The number of subsets of $ S(n) = \{1, 2, \ldots, n\} $ that contain no consecutive integers is equal to $ F(n+2) $, where $ F(n) $ is the $ n $-th Fibonacci number for F(0) = 0, F(1) = 1.

Proof. We denote by $ s(n) $ the number in this lemma. And supposing the length of $ S(n) $ is 1 and 2, we count the number of its subset satisfying the above properties, which is accurately equal to $ F(3) $ and $ F(4) $. Then we only need to show that $ s(n+2) = s(n+1) + s(n) $, for all positive integers $ n $.

We enumerate the number of subsets of $ S(n+2) $ meeting the conditions. Discuss it in two ways whether the number $ n+2 $ is in the subset or not. Suppose that the number $ n+2 $ is not in the subset, and then this subset is made up of $ \{1, 2, \ldots, n+1\} $, that is, it is a subset of $ S(n+1) $.

Then we suppose the number $ n+2 $ is in the subset. According to the definition of the subset, the number $ n+1 $ is not in this subset, and other numbers are all made up of $ \{1, 2, \ldots, n\} $. This means the set is a union of a subset of $ S(n) $ and $ \{n+2\} $.

Combining the above two points, the proof of Lemma 3.4 is completed.

Theorem 3.5. Let $ \mathcal{P} = \{A_1, B_1, C_1\} $. Then the standard puzzle sequence of $ \mathcal{P} $ is equal to the Fibonacci sequence.

That is,

where $ F(n) $ is the $ n $-th Fibonacci number for $ F(0) = 0 $, $ F(1) = 1 $; see OEIS^[7], entry A000045.

Proof. We think of a mapping similar to the mapping in Theorem 3 of ^[6], called the flip map. Let $ X $ be a subset of $ \{1, 2, \ldots, n+1\} $. The flip map $ \phi_X : \alpha \mapsto \beta $ is a transformation which maps a puzzle $ \alpha = \bigl[

$$\begin{smallmatrix}x_1 & x_2 & \ldots & x_{n+1}\\ y_1 & y_2 & \ldots & y_{n+1}\end{smallmatrix}$$ \bigr] $ onto $ \beta = \bigl[ $$\begin{smallmatrix}a_1 & a_2 & \ldots & a_{n+1}\\ b_1 & b_2 & \ldots & b_{n+1}\end{smallmatrix}$$ \bigr] $ such that $ a_i = x_i $, $ b_i = y_i $ for $ i \notin X $ and $ a_i = y_i $, $ b_i = x_i $ for $ i \in X $.

Notice that a map $ \phi_X $ can convert a piece $ A_1 $ into $ B_1 $ or $ C_1 $ or $ D_1 $, for any $ X $. However, the support of the image of a puzzle of $ S_n(A_1) $ under the maping $ \phi_X $ is $ S_n(\mathcal{P}) $ if and only if there are no adjacent elements in $ X $. This is because if suppose $ X $ has adjacent elements $ i $ and $ i+1 $, then the reduction of the piece $ \bigl[

$$\begin{smallmatrix} x_i&x_{i+1}\\ y_i&y_{i+1} \end{smallmatrix}$$ \bigr] $ is exactly $ D_1 $ which is not in $ \{A_1, B_1, C_1\} $. And vice versa.

So, the number $ s_n(\mathcal{P}) $ is equivalent to the number of subsets of $ \{1, 2, \ldots, n+1\} $ such that there is no adjacent number in it. Notice that the number $ s_1(A_1) $ is exactly one, and according to Lemma 3.4, this theorem has been proved.

4.   Standard puzzles enumerated by the skeleton model

In this section, we enumerate a number of standard puzzle sequences by our skeleton model.

4.1.   Standard puzzles relating to double factorials

In this subsection, we dicuss about a kind of special standard puzzles such that $ \{A_1, A_2, A_3\} $ or $ \{A_1, A_2\} $ united with $ B $-converters (resp. $ C $-converters) forms its support. Notice that any two $ B $-converters (resp. $ C $-converters) can't appear at the same time in this kind of puzzles. We can simply enumerate the standard puzzle sequences of the unions of $ \{A_1, A_2, A_3\} $ or $ \{A_1, A_2\} $ and a $ B $-converter (resp. $ C $-converter). And we can sum them and subtract out the double counting to get all this kind of puzzles.

Before enumerating these kinds of puzzles, we need some theorems as follows.

Definition 4.1. Let $ \mathcal{P} $ be a set of standard pieces and $ S_n(\mathcal{P}_x) $ (resp. $ S_n(\mathcal{P}^x) $) denotes the set of all standard $ n $-puzzles, each of which has $ \mathcal{P} $ as its support and the number $ x $ is in the bottom right corner (resp. top right corner). And let $ s_n(\mathcal{P}_x): = \bigl|S_n(\mathcal{P}_x)\bigr| $ (resp. $ s_n(\mathcal{P}^x): = \bigl|S_n(\mathcal{P}^x)\bigr| $) be the cardinality of $ S_n(\mathcal{P}_x) $ (resp. $ S_n(\mathcal{P}^x) $).

Theorem 4.1. Let $ \mathcal{P} $ be $ \{A_1, A_2, A_3\} $, then we have,

where $ T(n, k) $ is the sum of the weights of all vertices labeled $ k $ at depth $ n $ in the Catalan tree $ (1 \leqslant k \leqslant n+1, n \geqslant 0) $; see OEIS ^[7] entry A102625.

Proof. By definition of $ T(n, k) $, let $ T(m, 0) = 0 $ for any positive integer $ m $, and then we can know that $ T(n, k) $ satisfies the following equation:

Then, let a standard puzzle of $ S_n(\mathcal{P}) $ with $ 2n+2-k $ and $ j $ in the bottom and top right hand corner respectively, for $ 2n+3-k \leqslant j \leqslant 2n+2 $. Then we get rid of the rightmost column of this puzzle, and replace all the numbers by $ \{1, 2, \ldots, 2n\} $ respecting the label ordering. Thus, we get a standard puzzle in $ S_{n-1}(\mathcal{P}_{2n-i}) $ for $ k-1 \leqslant i \leqslant n $ by observing the skeleton of $ \mathcal{P} $. Besides, each element of $ S_{n-1}(\mathcal{P}_{2n-i}) $ can be produced by $ k $ different elements of $ S_n(\mathcal{P}_{2n-k+2}) $ for the number $ j $ has $ k $ choices.

That is,

Then the recurrence relation has been shown. So we only need to check (4.1) for $ n = 1 $. Because of $ s_1(\mathcal{P}_{3}) = 1 = T(1, 1) $ and $ s_1(\mathcal{P}_{2}) = 2 = T(1, 2) $, the proof of Theorem 4.1 is completed.

Then, we check it in OEIS ^[7], and find the formula of it:

At this point, we can give second proof of Theorem 3.2.

Proof of Theorem 3.2. Let $ \mathcal{P} $ and $ \mathcal{Q} $ denote $ \{A_1, A_2\} $ and $ \{A_1, A_2, A_3\} $ respectively and now we draw the skeletons of $ S_n(\mathcal{P}) $ and $ S_n(\mathcal{Q}) $.

By contrast, we can find the skeletons of $ S_n(\mathcal{P}) $ and $ S_n(\mathcal{Q}) $ are very similar. Let us do a simple operation on $ S_n(\mathcal{P}) $: shift the top row of numbers to the right by one space. Then, we will find it incredible that $ S_n(\mathcal{P}) $ and $ S_{n-1}(\mathcal{Q}) $ are the same in the middle, except that $ S_n(\mathcal{P}) $ has two more leftmost and rightmost digits than $ S_{n-1}(\mathcal{Q}) $. The leftmost number of $ S_n(\mathcal{P}) $ is accurately number one, while the rightmost number is uncertain. Given a puzzle of $ S_{n-1}(\mathcal{Q}) $ we add one to each label of it, and put the number one at the lower left corner in the puzzle. And then, we consider the number at the lower right corner after changing denoted by $ 2n+1-k $ for $ k \in\{1, 2, \ldots, n\} $. Then, we choose a number $ j \in\{2n+2-k, 2n+3-k, \ldots, 2n+2\} $. We can know that there are $ k+1 $ kinds of way to choose the number for given $ k $. Then, we put this number on the top right corner of the new puzzle and add one to each number no less than the number $ j $ after the first change. Then shift the top row of numbers to the left by one space. A puzzle $ S_n(\mathcal{P}) $ has been constructed. Besides, this construction is easily seen to be invertible.

Thus, we get the number $ s_n(\mathcal{P}) $, that is,

We substitute Eq (4.1) into Eq (4.5), and get the following equation:

Notice that the right-hand side of the equation is a hypergeometric series. The study of the hypergeometric identities ^[10,11] has been going on for decades, and now "the discoveries and the proofs of hypergeometric identities have been very largely automated" ^[11]. We simplified this hypergeometric series by computer and got that,

By Eqs (4.6) and (4.7), the proof of Theorem 3.2 is completed.

Now, we enumerate the standard puzzle sequences of the unions of $ \{A_1, A_2, A_3\} $ or $ \{A_1, A_2\} $ and $ B_i $ (resp. $ C_i $), for $ i\in\{1, 2, 3, 4, 5, 6\} $.

Theorem 4.2. Let $ \mathcal{P} = \{A_1, A_2, A_3\} $.

Proof. The puzzle with $ \mathcal{P}\cup B_i $ as support, can be simply divided into two categories, whether it contains $ B_i $ as its minimal support or not. If $ B_i $ is not a member of its minimal support, this puzzle will degenerate into $ S_n(\{A, B, D\}) $, which has been shown in Section 3.3. Then we just need to count the standard puzzle sequences with $ \mathcal{P}\cup B_i $ as its minimal support.

Firstly, for Eq (4.8) we switch the order of the top and bottom of the last column of these three standard puzzles. Then we notice that these puzzles are changed into $ S_n(\mathcal{P}) $ ending with $ A_1, A_2 $ and $ A_3 $ respectively.

Therefore we just need to show that the number of $ \{A, B, D\}^n $ ending with $ A, B $ and $ D $ are equal and equal to one third of $ \bigl|\{A, B, D\}^n\bigr| $. Simply switch the three digits in the upper right corner, and then Eq (4.8) can be shown.

Secondly we give a proof of Eq (4.10). To see clearly the relation between the numbers, we draw the skeleton of $ S_n(\mathcal{P}\cup B_6) $ with $ B_6 $ as shown in Figure 8. Then we find it only has two numbers less than the lower right number $ 2n-k $ of $ S_{n-1}(\mathcal{P}_{2n-k}) $ plus 2. Therefore, we have the following equation:

Lastly, for Eq (4.9), by swaping the upper left and the lower right of piece on the rightmost side of $ S_n(\mathcal{P}\cup B_4) $, we can get a puzzle $ S_n(\mathcal{P}\cup B_5) $. And vice versa. Then, the equivalence property has been shown. Additionally, notice that

So we just need to count the numbers $ s_n(\mathcal{P}\cup B_4 \cup B_5) $. We draw the skeleton to observe it.

According to this skeleton, we can write the following equation:

In the end, we simplify the right-hand side of Eqs (4.11) and (4.13) by computer and get the following equations:

Hence, Theorem 4.2 is proved.

After that, we give some conclusions about the standard puzzle sequences of $ \{A_1, A_2\}\bigcup B_i $.

Theorem 4.3. Let $ \mathcal{Q} = \{A_1, A_2\} $. Then we have,

Proof. Similar to the proof of the previous theorem, we can get the following equations:

And then by calculation, we can get equations as follows:

Hence, the proof of Theorem 4.3 is completed.

Analogously, the standard puzzle sequences of the unions of $ \{A_1, A_2, A_3\} $ or $ \{A_1, A_2\} $ and $ \{C_i\} $ $ (i\in\{1, 2, 3, 4, 5, 6\}) $ can be enumerated as follows. And no proof will be given.

Theorem 4.4. Let $ \mathcal{P} = \{A_1, A_2, A_3\} $ and $ \mathcal{Q} = \{A_1, A_2\} $. Then we have,

4.2.   Standard puzzles relating to Catalan numbers

Similar to the last subsection, in this subsection, we enumerate the standard puzzle sequences of the unions of $ \{A_2, A_3\} $ or $ \{A_2\} $ and $ B_i $ (resp. $ C_i $) for $ 1\leq i\leq6 $.

Theorem 4.5. Let $ \mathcal{P} $ be $ \{A_2, A_3\} $. Then we have,

where $ t(n, k) $ is the Catalan's triangle, for $ 0 \leqslant k \leqslant n $; see OEIS ^[7] entry A009766.

Proof. By definition of $ t(n, k) $, we make the convention $ t(n, n+1) = 0 $ and can get $ t(n, k) = \sum_{j = 0}^{k} t(n-1, j) $.

Moreover, for a puzzle in $ S_{n}(\mathcal{P}_{n+k+1}) $, the number on the left of $ n+k+1 $ can be $ \{n, n+1, \ldots, n+k\} $. Given the number on the left of the number $ n+k+1 $, we get rid of the rightmost column of this puzzle, and replace all the numbers by $ \{1, 2, 3, \ldots, 2n\} $ respecting the label ordering. Then we get a standard puzzle in

$ S_{n-1}(\mathcal{P}_{n+j}) $ for $ 0 \leqslant j\leqslant n-1 $. Besides, each element of $ S_{n-1}(\mathcal{P}_{n+j}) $ can be produced by only one elements of $ S_{n}(\mathcal{P}_{n+k+1}) $.

Then we have,

Then the recurrence relation is proved. By checking Eq (4.19) for $ n = 1 $ and this theorem is shown.

Then, by checking in OEIS, we can get the following formula:

Theorem 4.6. Let $ \mathcal{P} $ be $ \{A_2, A_3\} $. Then,

Proof. The proof of this result is quite similar to the proof for Theorem 4.2. So we just give a proof of Eq (4.25) to be an example. Furthermore, we have listed all the results as follows:

For Eq (4.25), notice that $ L $ and $ J $ can not appear in the $ S_n(\mathcal{P}\cup B_4\cup B_5) $ at the same time. So we get,

As with the previous theorem, let's draw the skeleton of $ S_n(\mathcal{P}\cup B_4\cup B_5) $ first.

From this picture, we can get,

Then, according to Eqs (4.33) and (4.34), we can get the following equation:

And then we can get the equations. Furthermore, an argument similar to Theorem 4.2 and 4.6 shows that:

Theorem 4.7. Let $ \mathcal{Q} $ be $ \{A_2\} $. Then,

Remark 4.1. Let $ \mathcal{P} = \{A_2, A_3\} $ and $ \mathcal{Q} = \{A_2\} $. Notice that:

$ \forall i \in \{1, 2, 3, 4, 5, 6\} $, $ \exists j \in \{1, 2, 3, 4, 5, 6\} $, such that,

That is, $ s_n(\mathcal{P}\cup C_i) = s_n(\mathcal{P}\cup B_j) $ and $ s_n(\mathcal{Q}\cup C_i) = s_n(\mathcal{Q}\cup B_j) $. Therefore, we can enumerate $ s_n(\mathcal{P}\cup C_i) $ and $ s_n(\mathcal{Q}\cup C_i) $ by $ s_n(\mathcal{P}\cup B_j) $ and $ s_n(\mathcal{Q}\cup B_j) $ respectively which we have enumerated before.

4.3.   Standard puzzles relating to Entringer numbers

In 1966, Entringer ^[3] enumerated the down–up permutations according to the first element called Entringer numbers. Additionally, in the past two decades, a great deal of mathematical effort has been devoted to the study of Entringer numbers ^[12,13].

In this subsection, we enumerate a class of standard puzzle sequences which is related to Entringer numbers. That is, the standard puzzles with $ \{A_1, A_2, A_3, A_4, A_5\} $ united with a converter as a support. With Proposition 2.1, the standard puzzle sequences with $ \{A_1, A_2, A_4, A_5, A_6\} $ united with a converter as a support is the same as this condition. Before we state and prove the theorem, we need a lemma as follows:

Lemma 4.8. Let $ \mathcal{P} $ be $ \{A_1, A_2, A_3, A_4, A_5\} $. Then we have,

where $ E(n, k) $ is the number of down-up permutations of $ n+1 $ starting with $ k+1 $; see OEIS ^[7] entry A008282.

Proof. By the definition of the Entringer numbers and the proof of Theorem 3.1, it is straightforward to show this lemma. So the proof will be omitted.

Theorem 4.9. Let $ \mathcal{P} $ be $ \{A_1, A_2, A_3, A_4, A_5\} $. For $ n\geq 2 $, we have,

where $ E(n, k) $ is the number of down-up permutations of $ n+1 $ starting with $ k+1 $, and $ S(n) $ is the $ n $-th secant number; see OEIS ^[7] entry A008282 and A000364, respectively.

Proof. The proof of this result is quite similar to Theorem 4.2 and 4.6 and so is omitted.

Remark 4.2. Let $ \mathcal{P} = \{A_1, A_2, A_3, A_4, A_5\} $. Notice that:

$ \forall i \in \{1, 2, 3, 4, 5, 6\} $, $ \exists j \in \{1, 2, 3, 4, 5, 6\} $ such that,

where $ F_k $ $ (k\in\{1, 2, 3\}) $ is defined in Definition 2.4. And by Proposition 2.1, we have $ s_n(\mathcal{P}\cup C_i) = s_n(\mathcal{P}\cup B_j) $. Therefore, we can enumerate $ s_n(\mathcal{P}\cup C_i) $ by $ s_n(\mathcal{P}\cup B_j) $ which we have enumerated in Theorem 4.9.

4.4.   A large class of Standard puzzles

Theorem 4.10. Let $ \mathcal{P} $, $ \mathcal{Q} $ be the $ x $-th and $ z $-th simple pieces in Table 3 (maybe the same simple piece), $ \mathcal{T} $ be a standard piece $ B_y $. Let $ \overline{\mathcal{Q}} $ be the image of Q passing through the function $ F_1 \circ F_2 $ in Definition 2.4.

Then we have,

in which $ i, j, k, l, m, p \in \mathbb{Z}_+ $, $ P_x(i, j, m) $ denotes the $ x $-th standard puzzle of length $ m $ after given the rightmost two digits $ i $ and $ i + j $. The same thing with the definition of $ P_z(k, l, p) $.

To prove the theorem, we need a lemma as follows:

Lemma 4.11. Let $ N = \{1, 2, \ldots, 2n+2\} $, and partition the set N into two parts $ A $ and $ B $. Sort the elements in $ A $ and $ B $ from the smallest to the largest. Given the positive integers $ i $, $ j $, $ k $, $ l $, $ m $, $ p $, satisfying $ i+j\leq 2m, k+l\leq 2p $ and $ m+p = n+1 $. $ A = \{a_1, a_2, \ldots, a_{2m}\} $ and $ B = \{b_1, b_2, \ldots, b_{2p}\} $. Then

a) The number of ways to partition the set $ N $ into $ A $ and $ B $ satisfying $ a_i < b_k < b_{k+l} < a_{i+j} $ is $ Q_1(i, j, k, l, m, p) $ which is,

b) The number of ways to partition the set $ N $ into $ A $ and $ B $ satisfying $ a_i < b_k < a_{i+j} < b_{k+l} $ is $ Q_2(i, j, k, l, m, p) $ which is,

c) The number of ways to partition the set $ N $ into $ A $ and $ B $ satisfying $ a_i < a_{i+j} < b_k < b_{k+l} $ is $ Q_3(i, j, k, l, m, p) $ which is,

Proof. The proofs of these three formulas are similar, and we will only deal here with the proof of Eq (4.43), which is as follows.

We consider the numbers $ a_i $, $ b_k $ and $ a_{i+j} $. The number $ a_i $ has $ k $ choices $ i, i+1, \ldots, i+k-1 $ and then $ b_k $ has $ j $ choices $ i+k, i+k+1, \ldots, i+j+k-1 $ and $ a_{i+j} $ has $ l $ choices $ i+j+k, i+j+k+1, \ldots, i+j+k+l-1 $. Otherwise, the inequality will not hold. And these conditions are independent of each other. Let $ a = a_i -i $, $ b = b_k-i-k $, $ c = a_{i+j}-i-j-k $, and then we enumerate the number of partitions meeting these conditions and get the equation.

Proof of Theorem 4.10. Notice that $ C_\alpha \notin \mathcal{P} \cup \mathcal{T} \cup\overline{\mathcal{Q}} $, for any $ \alpha\in\{1, 2, 3, 4, 5, 6\} $. Then for a standard puzzle of $ S_n(\mathcal{P} \cup \mathcal{T} \cup\overline{\mathcal{Q}}) $ if the bottom number in one column is greater than the top number, then the bottom number in each subsequent column is greater than the top number. Therefore, the puzzle has three possible situations.

1) The number at the top of each column is greater than the number at the bottom. Then its an element of $ S_n(\mathcal{P}) $.

2) The numbers at the bottom of each column are greater than the numbers at the top. Then its an element of $ S_n(\overline{\mathcal{Q}}) $.

3) There exists a number $ m $ $ (1\leq m\leq n) $. Then in the first $ m $ column(s), the top number is larger than the bottom number and the subsequent columns are the opposite.

For the situation 1) and 2), it is a puzzle of $ S_n(\mathcal{P}) $ and $ S_n(\overline{\mathcal{Q}}) $. Then we just have to think about the situation 3). In this situation, we can cut this puzzle between the $ m $-th column and the ($ m+1 $)-th column, and get two simple puzzle of $ S_m(\mathcal{P}) $ and $ S_p(\mathcal{\overline{Q}}) $ ($ p = n+1-m $). Besides, for two simple puzzle P and $ \overline{Q} $ of $ S_m(\mathcal{P}) $ and $ S_p(\mathcal{\overline{Q}}) $, let $ i $ and $ i+j $ be the number in the lower and top right corner of P, $ k $ and $ k+l $ be the number in the top and lower left corner of $ \overline{Q} $, respectively.

We can get a partition of $ \{1, 2, \ldots, 2n+2\} $ into two parts, $ A $ and $ B $. $ A $ is $ \{a_1, a_2, \ldots, a_{2m}\} $ and $ B $ is $ \{b_1, b_2, \ldots, b_{2p}\} $ are sorted from the smallest to the largest. For given $ i $, $ j $, $ k $, $ l $, we let $ a_i < b_k < b_{k+l} < a_{i+j} $ and replace the number $ \alpha $ in P and $ \beta $ in $ \overline{Q} $ by $ a_\alpha $ and $ b_\beta $, respectively. Then we get a puzzle $ \mathcal{P} \cup B_1 \cup\overline{\mathcal{Q}} $. Sum over all $ i, j, k, l $ that satisfy $ i+j\leq 2m $ and $ k+l\leq2p $ and Eq (4.41) is set up for $ i = 1 $ with $ T_1(i, j, k, l, m, p) = Q_1(i, j, k, l, m, p) $. Analogously, for $ y\in\{1, 2, 3\} $, Eq (4.41) holds and we have,

for $ y\in\{1, 2, 3\} $.

For $ \mathcal{T} = B_y $, $ y\in\{4, 5, 6\} $, we use Proposition 2.1 about the map $ F_1 $ and $ F_2 $ in Definition 2.4 and get the following equation:

where $ \mathcal{\overline{T}} = B_{y-3} $ for $ y\in\{4, 5, 6\} $. We reuse Eqs (4.41) and (4.45) for $ y\in\{1, 2, 3\} $, and then (4.41) is proved for all $ i\in\{1, 2, 3, 4, 5, 6\} $. And for $ i\in\{1, 2, 3\} $ we have,

Hence the proof is completed.

Additionally, we list all the $ P_x(i, j, m) $ $ (1\leq x\leq 20, x\in \mathbb{Z}) $ in Table 3. For $ x\in\{1, 2, 3, 15, 16\} $, the conclusions are trivial and for $ x\in\{5, 6, 12, 14\} $ they are corollaries of Theorem 3.2. For $ x\in\{4, 7, 11, 13\} $ and $ x\in \{17, 18, 19, 20\} $ they are corollaries of Theorem 4.1 and Theorem 4.5 respectively. When $ x = 8 $ and $ x = 9 $, we can get the function by the proof of Theorem 3.1 and the definition of the Euler-Bernoulli or Entringer numbers in OEIS ^[7] entry A008282.

Using Theorem 4.10 and Proposition 2.1, we have the following corollary.

Corollary 4.1. Let $ \mathcal{P} $, $ \mathcal{Q} $ be the $ x $-th and $ z $-th simple pieces in Table 3 (maybe the same simple piece), $ \mathcal{T}' $ be a standard piece $ C_y $. Let $ \mathcal{Q}' $ and $ \mathcal{\overline{Q}} $ be the image of Q passing through the function $ F_2 $ and the function $ F_1 \circ F_2 $ in Definition 2.4 respectively. Then we have,

in which $ i, j, k, l, m, p \in \mathbb{Z}_+ $, $ P_x(i, j, m) $ denotes the $ x $-th standard puzzle of length $ m $ after given the rightmost two digits $ i $ and $ i + j $. The same thing with the definition of $ P_z(k, l, p) $.

5.   Identities for standard puzzle sequences

Theorem 5.1. Let $ \mathcal{P}_i \in \{A_i, B_i\} $, $ \mathcal{Q}_i \in \{C_i, D_i\} $ for $ i\in\{1, 2, 3, 4, 5, 6\} $ and let $ \alpha $ be a subset of $ \{1, 2, 3, 4, 5, 6\} $.

So, we have

Proof. By Proposition 2.1 in Section 2, we can know that

Besides, $ A_i\in\{A_i, B_i\} $ and $ D_i\in\{C_i, D_i\} $, so we only need to show that

$ s_n\bigl(\bigl(\bigcup_{i\in\alpha}\mathcal{P}_i\bigr)\bigcup\bigl(\bigcup_{i\in\alpha}\mathcal{Q}_i\bigr)\bigr) $ are equal for any $ \alpha\subset \{1, 2, 3, 4, 5, 6\} $, and any $ \mathcal{P}_i \in \{A_i, B_i\} $, $ \mathcal{Q}_i \in \{C_i, D_i\} $.

Notice that the right-hand column of $ \{A_i, B_i\} $ (resp. $ \{C_i, D_i\} $) is the same. Then we check the reduction of each piece of a puzzle in $ S_n\bigl(\bigl(\bigcup_{i\in\alpha}A_i\bigr)\bigcup\bigl(\bigcup_{i\in\alpha}D_i\bigr)\bigr) $ from right to left. If the piece does not belong to $ \bigl(\bigcup_{i\in\alpha}\mathcal{P}_i\bigr)\bigcup\bigl(\bigcup_{i\in\alpha}\mathcal{Q}_i\bigr) $ as a standard puzzle, we turn the left-hand column of this pieces upside down and continue to retrieve until the research is complete. Because of this operation can swap $ A_i $ with $ B_i $, and swap $ C_i $ with $ D_i $, we can get a puzzle in $ \bigl(\bigcup_{i\in\alpha}\mathcal{P}_i\bigr)\bigcup\bigl(\bigcup_{i\in\alpha}\mathcal{Q}_i\bigr) $. Besides, this mapping is easily seen to be invertible. Hence the proof is completed.

Remark 5.1. In fact, this idea is inspired by a proof in ^[6].

According to Theorem 5.1 and using Proposition 2.1 about the map $ F_2 $, we can get the following corollary easily.

Corollary 5.1. Let $ \mathcal{P}_i \in \{A_i, C_i\} $, $ \mathcal{Q}_i \in \{B_i, D_i\} $ for $ i\in\{1, 2, 3, 4, 5, 6\} $ and $ \alpha $ be a subset of $ \{1, 2, 3, 4, 5, 6\} $. We have,

By Theorem 5.1 and Corollary 5.1, we can get many standard puzzle sequences from known sequences. For example, in Donald Knuth's paper ^[8], he has shown the standard puzzle sequence of $ \{A_1, A_4, B_3, B_6, C_3, C_6, D_1, D_4\} $, which is as follows:

Theorem 5.2. For $ n\ge 1 $, we have

where $ W(n) $ is the number of permutations $ \pi $ of $ \{1, \ldots, 2n\} $ such that $ \pi(2k-1) < \pi(2k) $ if and only if $ \pi(2k) < \pi(2k+1) $; see OEIS ^[7], entry A261683.

Then, we get the following corollary by Theorem 5.1.

Corollary 5.2. Let $ \mathcal{P}_i \in \{A_i, B_i\} $, $ \mathcal{Q}_i \in \{C_i, D_i\} $ and $ i\in\alpha = \{1, 3, 4, 6\} $. We have

Theorem 5.3. Let $ \mathcal{P} $ be a subset of $ \{A, B, C, D\} $, $ \alpha $ be a subset of $ \{1, 2, 3, 4, 5, 6\} $. Then we have the following equation:

The proof of this result is quite similar to that of Theorem 3.5 and so is omitted.

Additionally, we have determined all the standard puzzle sequence of $ \bigcup_{X\in\mathcal{P}}X_1 $. That is, if the cardinality of $ \mathcal{P} $ is 1 or 2 or 4, the sequence is trivial. And for $ \bigl|\mathcal{P}_1\bigr| = 3 $, we have:

With the help of Theorem 3.5 and Proposition 2.1 about the map $ F_2 $, we can prove (5.6). And (5.7) is trivial so the proof will be omitted.

6.   Conclusions

In conclusion, the following enumerative problems have been solved except one kind of questions in cases b) and c):

a) the sequences of all 80 simple pieces;

b) the sequences of a $ 1 $-simple or $ 4 $-simple piece with $ i $-converter(s), for $ i\in\{B, C\} $;

c) the sequences of a $ 1 $-simple piece united with a $ 4 $-simple piece and $ i $-converter(s), for $ i\in\{B, C\} $.

The unique unsolved case is the standard puzzle sequences of $ \{A_1, A_2, A_4, A_5\} $ with $ i $-converter(s) (resp. with $ i $-converter(s) and another $ 4 $-simple piece), $ i\in\{B, C\} $. In addition, with the help of identities for standard puzzle sequences proposed in Section 5, we can enumerate much more sequences.

Although we have enumerated tens of thousands of sequences, a lot of sequences are given in the form of hypergeometric series and we expect to simplify them. Moreover, the sequences of the unions of several $ 1 $-simple pieces haven't been enumerated, some of which are conjectures proposed by Guo-Niu Han in ^[6] such as the sequences of $ \{A_1, A_3\} $, $ \{A_2, A_5\} $ and so on.

Finally, as G.-N. Han has remarked in ^[6], standard puzzles is "a large family of combinatorial objects", "defined by very simple rules". After our research and previous studies, many classical sequences have been interpreted by standard puzzles, like double factorial numbers, secant numbers, Fibonacci numbers, Catalan numbers ^[6], tangent numbers ^[6], the numbers of up-up-or-down-down permutations ^[8] and so on. However, there are still tens of millions (about $ 2^{4!} = 16, 777, 216) $ of sequences that haven't been enumerated. This is an issue for future research to explore.

Acknowledgments

We wish to thank the anonymous referee for several valuable suggestions that help to clarify certain definitions and enhance the overall readability of our paper. The On-Line Encyclopedia of Integer Sequences ^[7] was an invaluable resource for our work, so we would like to extend our sincere thanks to Neil Sloane and the OEIS Foundation, Inc.

The first author was partly supported by the National Natural Science Foundation of China grant 12171059 and the Natural Science Foundation Project of CQ CSTC (No. cstc2021jcyj-msxmX0693).

Conflict of interest

The authors declare there is no conflicts of interest.