Abstract
A method to classify one-dimensional binary sequences using three parameters intrinsic to the sequence itself is introduced. The classification scheme creates combinatorial patterns that can be arranged in a two-dimensional triangular structure. Projections of this structure contain interesting properties related to the Pascal triangle numbers. The arrangement of numbers within the triangular structure has been named “triangular numbers”, and the essential parameters, elementary equation, and sequencing schemes are discussed as well as visualizations of sample distributions, special cases, and search results. We believe this to be a novel finding as sequences generated using this method are not contained in the On-Line Encyclopedia of Integer Sequences or OEIS.
This work was supported by the Key Project on Electric Information and Next Generation IT Technology of Yunnan (2018ZI002), NSF of China (61362014), Yunnan Advanced Overseas Scholar Project.
You have full access to this open access chapter, Download chapter PDF
Similar content being viewed by others
Keywords
- Binary sequence
- Classification
- Combinatorial patterns
- Triangular number
- Elementary equation
- Variant triangle
1 Introduction
Additive number theory [7], the study of integer subsets and their behavior under addition, is a branch of mathematics related to combinatorics. The simplest constructs within this field are binomial coefficients [6]. The properties of binomial coefficients have been explored by many over the history of mathematics [8, 9]. One generalization of the binomial coefficient is the multinomial coefficient [5, 8, 9]. Any multinomial coefficient can be expressed as the products of multiple binomial coefficients:
For this type of expansions, the simplest is the trinomial coefficient [10,11,12,13]:
1.1 Geometric Arrangement of Combinatorial Data
In discrete geometry [2], as the most basic 2D shape, triangular patterns are found in such series as combinatorial triangle A102639, differential triangle A194005 [1], additive triangle A035312, and Pascal triangle A007318 [8, 9, 11, 13].
This chapter proposes a novel method of classification of binary sequences that is shown to be combinatorial properties in nature. By using a simple basis of binary (0–1) sequences and applying simple classification rules, a triangular structure can be generated. The set of results has been named “Generative Triangular Numbers”. The term generative [3] is used to describe the technique of using a simple input and a repeatedly applied process, creating emergent properties through repetition. Generative science [4] is a multidisciplinary science that explores the natural world and its complex behaviors as a generative process. Generative approaches can be used to simulate describe behaviors in fractals, cellular automata, and various nonlinear systems.
The generated patterns are not currently found in the On-Line Encyclopedia of Integer Sequences (OEIS) potentially making them an interesting area for further research.
1.2 Previous Work
The current scheme is a derivative of the work of Zheng et al. [16, 17] to organize 1D 0–1 sequences as certain \(N>1\) length vectors using three parameters in variant measurement construction and classifications on hierarchical discrete phase spaces in general.
A trinomial equation is proposed as an elementary equation using three control parameters \(\{q,p,N\}\) [14, 15] to describe 0–1 vectors of N length as a subgroup, where N is the length of a vector, p indicates the number of elements with 1 values, and q records the number of changes from either 0–1 or 1–0 as the vector in a circular form to form a 2D array with nontrivial triangular numbers. This type of elementary equation can be generatively applied to make relevant triangular numbers as a geometric distribution to form a hierarchical 3D array generatively. Based on this hierarchical 3D array, different integer sequences can be observed from this type of generative triangular numbers, and one projection on p direction is collected by Vandermonde’s identities to show their correspondences to standard binomial coefficients. Main results are provided by algorithms, theorems, and corollaries. Sample cases are illustrated and possible meanings are discussed.
2 Definitions and Sample Cases
2.1 Definitions
Definition 1
Let X be a 0–1 vector, \(X=x_{N-1} \ldots x_i \ldots x_0\) with N elements as a state, \(x_i\in \{0,1\}, 0\le i< N\).
Definition 2
Let \(\varOmega (N)\) denote a vector space contained all 0–1 vectors of N length \(\varOmega (N)=\{\forall X| 0\le X < 2^{N}\}\) as an initial data set.
Definition 3
Let \(\left( {\begin{array}{c}n\\ k\end{array}}\right) \) be a binomial coefficient, it satisfies
Under this condition, \(|\varOmega (N)|=2^{N}\) forms a vector space with N length, respectively.
Definition 4
For any selected vector \(X\in \varOmega (N)\), p(X) can be determined by
Lemma 1
For a vector space \(\varOmega (N)\), p provides a complete partition on a subgroup and the number of vectors in the subgroup is a binomial coefficient.
Proof
For a given \(p, 0\le p \le N\), its combinatorial property makes a total number of \(\left( {\begin{array}{c}N\\ p\end{array}}\right) = \frac{N!}{p!\times (N-p)!}\) vectors identified to partition the vector space \(\varOmega (N)\).
Definition 5
For a circular vector \(X\in \varOmega (N)\), q(X) can be determined by
e.g., \(N=10, X=1110011001, p(X)=6 (i=\{0,3,4,7,8,9\}); q(X)=2 (i=\{2,6\})\).
2.2 Sample Cases
Under this construction, any selected vector can be evaluated by the three parameters. Applying this set of parameters to create subgroups, interesting inner structures can be identified. That is, \(N=4\), all 16 vectors in the vector space, can be distinguished as six subgroups as a pair of (q, p) values shown in Table 1.
Each subgroup is linked to their corresponding vectors in Table 2
Enumeration numbers of relevant subgroup numbers are shown in Table 3.
From Table 3, it is easy to verify that 16 vectors are sum of all possible numbers from six subgroups. Subgroup sequences of all numbers are as the same as \(N=4\) binomial coefficients. Applying this corresponding from \(N=1\)–6, six rows of original binomial coefficients can be created generatively as three-dimensional organization and each row \(\{p,N\}\) sequence corresponds a (q, p) triangular shape, respectively, shown in Table 4.
This type of relationship can be expanded on generative mechanism from special cases of \(N=1\)–6 to general conditions for any given N value. The detailed generative triangular mechanism is described in the next section.
3 Elementary Equations
Definition 6
Let f(q, p, N) denote a function for generative triangular numbers \(0\le p \le N, 0\le q \le \lfloor N/2 \rfloor \), for two initial and end subgroups \(p=\{0,N\},q=0\), let two functions of subgroups be \(f(0,0,N)=f(0,N,N)=1\).
For other subgroups, each case \(0< p< N, 0< q \le \lfloor N/2 \rfloor \) is a subgroup under a given condition. Elementary equation of generative triangular numbers is proposed to use binomial coefficient expression in Eq. 6.
Using this elementary equation, the list of values can be verified. For example, \(f(1,1,5)=\frac{5}{4}\left( {\begin{array}{c}4\\ 1\end{array}}\right) \left( {\begin{array}{c}0\\ 0\end{array}}\right) = 5; f(2,3,5)=\frac{5}{2}\left( {\begin{array}{c}2\\ 2\end{array}}\right) \left( {\begin{array}{c}2\\ 1\end{array}}\right) = 5; \ldots f(2,4,5)=\frac{5}{1}\left( {\begin{array}{c}1\\ 2\end{array}}\right) \left( {\begin{array}{c}3\\ 1\end{array}}\right) = 0\). All \(\{f(q,p,5)\}\) calculations are listed in Table 5.
Corollary 1
The elementary equation has equivalent identities on a pair of \(\{p,N-p\}\).
Proof
Using the elementary equation, we have
p parameters are in the vertical direction. In general condition for any given N, triangular numbers can be arranged in Table 6 (Fig. 1).
4 Local Propensities
It is necessary to investigate different relationships for symmetry properties from the elementary equations to distinguish functions for generative triangular numbers.
4.1 Nontrivial Areas
Corollary 2
(A pair of symmetric properties) In either \(0< q\le p \le N-q\) or \(q=0, p=\{0,N\}\), a pair of nontrivial trinomial coefficients on triangular numbers satisfies
Proof
Using the elementary equation, two cases are required.
Case 1: If \(q >0\), Eqs. 6 and 7 provide relevant combinatorial identities. Case 2: If \(q=0\), we have \(f(0,0,N)=f(0,N,N)=1\) by Definition 6.
4.2 Trivial Areas
Corollary 3
(Five areas for trivial values) If case 1—\(q > 0, 0< p <q\); case 2—\( N-q< p <N\); case 3—\(q=0, 0<p<N\); case 4—\(q > 0, p =0\); case 5—\(q>0, p=N\), then
Proof
For cases 1, 2 and 3, we have
For cases 4 and 5, we have
5 Projection Properties
5.1 Linear Projection
In this section, the algebraic properties of linear projection are investigated.
Definition 7
Let L(p, N) denote a function as a linear projection to collect all possible values for a given \(p, 0\le p \le N\).
For the case of \(N=5\), two projections and their generative triangular numbers are shown in Table 7, respectively.
Following theorems and corollaries are claimed.
Theorem 4
If \(L(p,N)=\sum _{q=1}^{p} f(q,p,N), 0<p<N\), then the projection function L(p, N) is a binomial coefficient and
Proof
For a fixed \(p, 0< p <N\), all possible \(\{f(q,p,N)\}\) are collected to form the following equation:
For a complete sequence of binomial coefficients, it is necessary to include both initial and end subgroups. Further corollaries can be established.
Corollary 5
For any given \(N>0\) under the listed condition, a set of projection function \(\{L(p,N)\}, 0\le p \le N\) is composed of the same sequence of binomial coefficients
Proof
For \(0<p<N\) condition, they are well determined by Theorem 5.1 and two end subgroups \(p=\{0,N\},\left( {\begin{array}{c}N\\ 0\end{array}}\right) =\left( {\begin{array}{c}N\\ N\end{array}}\right) =1\) by defined initial conditions.
Corollary 6
The sum of all possible \(\{L(p,N)\}_{p=0}^{N}\) is
Proof
Collecting all possible numbers by Corollary 2, we have
Corollary 7
For \(0 \le p \le N\), a pair of functions has an equivalent formula
Proof
By Corollary 2.1, both equations are equal.
Theorem 8
For any \(N>0\), the sum of all possible functions on \(\{f(q,p,N\}_{\forall p, \forall q}\) or \(\{L(p,N)\}_{p=0}^{N}\) is equal to \(2^N\)
Proof
By Corollary 6, two equations are equal.
5.2 Triangular Sequence
Definition 8
For a given \(N\ge 1\), let T(N) denote a 2D structure with all nontrivial triangular numbers.
Corollary 9
For a given N, if |T(N)| be a total number of distinguishable elements for nontrivial triangular numbers, then |T(N)| has the following equation:
Proof
By Corollary 2 for a given N, a triangular shape for nontrivial members is composed of two parts: a triangular area and two \(q=0\) points. The triangular area has \((N-1)\) length and \(\lfloor N/2 \rfloor \) high. If \(N\equiv 0, \text {(mod 2)}\), the triangular area is a regular triangle contained \(N^2/4\) elements, so the total number of the generative triangular shape is \(N^2/4 + 2\). For an odd valued N, a triangular area has additional \(\lfloor N/2 \rfloor \) members side on a regular triangle with \(\lfloor N/2 \rfloor ^2\) elements, so the total number of elements is \(\lfloor N/2 \rfloor ^2+\lfloor N/2 \rfloor + 2= (N^2 -1)/4 + 2\).
Definition 9
For a given \(N\ge 1\), let TS(N) denote an integer sequence with |T(N)| elements for all nontrivial triangular numbers in T(N)
5.3 Linear Sequence
Definition 10
For a given \(N\ge 1\), let L(N) denote a 1D structure with relevant linear numbers.
Corollary 10
For a given N, if |L(N)| be a total number of distinguishable elements for linear numbers, then |L(N)| satisfies Eq. 19.
Definition 11
For a given \(N\ge 1\), let LS(N) denote an integer sequence with |T(N)| elements for all linear numbers in L(N) (Table 8)
From the listed six groups of \(\{T(4),T(5),T(6)\}\) and \(\{L(4),L(5),L(6)\}\) structures, two integer sequences are arranged as follows:
6 Sample Cases
Two sample cases are selected for \(N=\{17,18\}\) to show their triangular numbers and generative structures in Table 9. In relation to relevant integer sequences, both \(\{L(16), L(17)\}\) and \(\{T(16),T(17)\}\) are shown in Table 9. Two integer sequences are significantly different. The triangular number sequence in this case with a total length of 140 integers is three times longer than the linear number sequence with a total length of 35 integers. Two integer sequences represent different partition results on the same number \(196608=2^{16}+2^{17}\) for generative binomial and trinomial coefficients, respectively.
7 Conclusion
Due to the proposed elementary equation of trinomial coefficients with excellent symmetric properties on a 2D grid similar to binomial coefficients on a 1D line, projecting operation makes 2D T(N) array be 1D linear L(N) array, respectively. Two types of TS(N) and LS(N) integer sequences can be generated. As the simplest expansion of multinomial coefficients, discrete 2D geometry could provide solid combinatorial foundation to support multinomial explorations.
From a combinatorial geometry viewpoint, triangular numbers provide a key construction to link between trinomial and binomial representation in mathematical foundation. Trinomial integer sequences, as representatives, need to be deeply explored by modern combinatorial & discrete mathematical societies. Further explorations are expected on detailed analysis and systematic construction on both and practical applications.
References
J.R. Chen, Combinatorial Mathematics (Harbin Institute of Technology Press, Harbin, 2012). (in Chinese)
Discrete geometry. http://en.wikipedia.org/wiki/Discrete_geometry
Generative. http://en.wikipedia.org/wiki/Generative
Generative science. http://en.wikipedia.org/wiki/Generative_science
H.W. Gould, Some generalizations of Vandermonde’s convolution. Am. Math. Mon. 63(2), 84–91 (1956)
H.W. Gould, Combinatorial Identities (Morganton, Morgantown, 1972)
L.K. Hua, Loo-Keng Hua Selected Papers (Springer, 1982)
L.K. Hua, Selected Work of Hua Loo-Keng on Popular Sciences (Shanghai Education Press, 1984) (in Chinese)
D.E. Knuth, The Art of Computer Programming, vol. 1, 3rd edn. (Addison-Wesley, Upper Saddle River, 1998)
G. Polya, R. Tarjan, D. Woods, Notes on Introductory Combinatorics (Birkhauser, Boston, 1983)
G.Z. Tu, Combinatorial Enumeration Methods and Applications (Science Press, Beijing, 1981). (in Chinese)
J.H. van Lint, R.M. Wilson, A Course in Combinatorics, 2nd edn. (Cambridge University Press, New York, 2001)
L.X. Wang, An Elementary Treatise on Combinations (Harbin Institute of Technology Press, Harbin, 2012) (in Chinese)
Z.J. Zheng, A. Maeder, The conjugate classification of the kernel form of the hexagonal grid, in Modern Geometric Computing for Visualization (Springer, 1992), pp. 73–89. https://doi.org/10.1007/978-4-431-68207-3
Z.J. Zheng, Conjugate transformation of regular plan lattices for binary images, Ph.D. thesis, Monash University, 1994
J.Z.J. Zheng, C.H.H. Zheng, A framework to express variant and invariant functional spaces for binary logic. Fron. Electr. Electron. Eng. China 5(2), 163–172 (2010). Higher Educational Press and Springer. https://doi.org/10.1007/s11460-010-0011-4
J.Z.J. Zheng, C.H.H. Zheng, T.L. Kunii, A framework of variant logic construction for cellular automata, In A. Salcido (Ed.), Cellular Automata—Innovative Modeling for Science and Engineering (InTech Press, 2011). https://doi.org/10.5772/15400
@zcaudate’s question. http://math.stackexchange.com/questions/155289/
Acknowledgements
Both authors would like to thank Mr. Zhonghao Yang for his contribution to work on sample sequences, sincerely to gratitude @Qiaochu Yuan for the suggestion of combinatorial description and @Zander to provide a set of combinatorial equations to answer @zcaudate’s question [18] in 2012.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2019 The Author(s)
About this chapter
Cite this chapter
Zheng, C., Zheng, J. (2019). Triangular Numbers and Their Inherent Properties. In: Zheng, J. (eds) Variant Construction from Theoretical Foundation to Applications. Springer, Singapore. https://doi.org/10.1007/978-981-13-2282-2_4
Download citation
DOI: https://doi.org/10.1007/978-981-13-2282-2_4
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-13-2281-5
Online ISBN: 978-981-13-2282-2
eBook Packages: EngineeringEngineering (R0)