Abstract
Four variant measures are used to represent combinatorial functions including binomial coefficients. These variant measures are based on two types of m-bit vectors. Type A corresponds to non-periodic boundary conditions, while Type B corresponds to periodic boundary conditions. For each type, groups containing the four variant measures are formed, which are invariant against permutative and associative operations. By mapping two group elements of Type B on coefficients of binomial decompositions, patterns similar to Pascal’s triangle are observed.
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
- Variant measurement
- m variable vector
- Multinomial coefficient
- Permutative and associative operations
- Global invariant
1 Introduction
For any n 0–1 variables, variant logic provides a \(2^n!\times 2^{2^n}\)-dimensional configuration space [16, 17] to support measurement and analysis [14, 15], which is a real difficulty for any practical activities [1, 9,10,11]. From a measuring analysis viewpoint [6,7,8, 13], it is essential to manipulate static states and their measuring clustering as effective measures to be a core content of any 0–1 measuring framework. In this chapter, starting from m variables of a 0–1 vector, binomial expressions are applied to support the four meta measures of variant partitions and associated multinomial expressions.
Using permutative and associative operations, various variation and invariant properties are investigated. From a global invariant viewpoint, various combinatorial clustering properties are systematically explored.
2 Elementary Equation
Let x be an m-bit vector, \(x=x_0x_1 \ldots x_i \cdots x_{m-1}, x_i\in \{0,1\}, 0\le i < m, x\in B_2^m\). Each x is an m bit state. From a variation viewpoint, there are two types \(\{A,B\}\) distinguished. Let \(\{m_{\bot },m_+, m_-, m_{\top }\}\) be four measuring operators.
2.1 Type A Measures
For a pair of \((i,i+1)\) elements, \((x_i,x_{i+1}), 0\le i < (m-1)\) form partitions. (Non-periodic boundary conditions)
Four measures can be calculated from the following equations.
From a clustering viewpoint, the last bit of x, \(x_{m-1}\) can be used to distinguish relevant combinatorial numbers. While \(x_{m-1}==1\), there are \({m-1 \atopwithdelims ()m_{+}+m_{\top }+1}\) and for \(x_{m-1}==0\), there are \({m-1 \atopwithdelims ()m_{+}+m_{\top }}\), possible x vectors, where \(m_{+}+m_{\top }\) is the number of 1 elements in a vector. By adding both binomial coefficients, Pascal’s rule [4] is obtained.
2.2 Type B Measures
A pair of \((i,i+1)\) elements is linked as a ring, \((x_i,x_{i+1 (mod \; m)}), 0\le i < m\) (Periodic boundary conditions).
Let p be the number of 1 elements, \(p(x) = m_{+}(x)+m_{\top }(x)\), then the number of possible x vectors is
3 Partition
Either Type A or B, internal parameters are associated with the four meta measures. For a brief analysis, Type B will be selected as initial part, multinomial coefficients are applied to partition relevant binomial coefficients. Using m variable, p number and q branches, the following equations are formulated. Under the partition condition, vector x can be ignored.
Based on equivalent quantitative numbers, there are one-to-one corresponding on the four meta measures and relevant quantitative measures:
from a global restriction to establish an equivalent expressional framework.
From an expressional viewpoint, different partitions are investigated from a single binomial coefficient to a set of multinomial coefficients with equivalent properties among different expressions. Their partitions undertaken on various levels are illustrated in the following sections. From a binomial coefficient, there are multiple levels of representations involved, the first level and the nth level can be connected as
The core content of this chapter is to establish a global invariant framework using n levels of representations by deriving the functions \(f_l\) and \(g_l\).
4 Variation Space
Let {a,b,c,d} be a set of four distinct measures. Two operations, permutative and associative, can be determined. For an ordered tuple with four measures (a, b, c, d), Permutative operator \(\pi \): \((a,b,c,d) \rightarrow (\pi (a), \pi (b), \pi (c),\pi (d))\) to map one measure to another measure.
Associative operator \(\alpha \): \(\{a,b,c,d\} \rightarrow \alpha \{a,b,c,d\}\) to group one to multiple measures keeping the initial ordering.
e.g. \((a,b,c,d) \rightarrow (b,d,a,c)\) is a permutative operation and
\(\{a,b,c,d\} \rightarrow \{a,b\}\{c\}\{d\}\) is an associative operation.
A permutative operation changes the order of four tuple variables and an associative operation changes sequential relationship on its neighbourhood elements. In a normal arithmetical condition, two operations have conservative under add operations with global invariant properties. From an algebraic viewpoint, two operations are independent.
Lemma 1
For an ordering structure with four measures under two operations: permutative and associative, there are 192 configurations identified.
Proof
For a vector with 4 members, there are a total of 24 distinct permutations \(4!=24\). For an ordered set of 4 elements, 8 associated patterns are identified as follows: {{a,b,c,d}; {a}{b,c,d}; {a,b}{c,d}; {a,b,c}{d}; {a}{b}{c,d}; {a}{b,c}{d}; {a, b}{c}{d}; {a}{b}{c}{d}}. Two operations are independent, so the whole system contains \(24\times 8 = 192\) configurations.
5 Invariant Combination
Using both permutative and associative operations, various combinatorial invariants can be identified.
5.1 Type A Invariants
Five invariant groups can be distinguished.
Proposition 1
For a measuring structure with four members, Type A has 16 combinatorial invariants distinguished (0 item: 1 cluster; 1 item: 1 cluster; 2a item: 4Â clusters; 2b item: 3 clusters; 3 item: 6 clusters; 4 item: 1 cluster).
Proof
Checking Type A conditions listed, all combinatorial conditions are exhaustive included.
5.2 Type B Invariants
For Type B, let \(b=c\), following simplification can be performed.
Proposition 2
For a measuring structure with four members, Type B has 12 combinatorial invariants distinguished (0 item: 1 cluster; 1 item: 1 cluster; 2a item: 3 clusters; 2b item: 2 clusters; 3 item: 4 clusters; 4 item: 1 cluster).
Proof
Checking Type B conditions listed, all combinatorial conditions are exhaustive included.
6 Combinatorial Expressions of Type B Invariants
Applying \(m_{\bot }=m-p-q, m_{+}=m_{-}, m_{\top }=p-q\) to replace \(\{a,b,c,d\}\), there are 11 effective formula:
Corollary 1
Type B invariants include 11 nontrivial expressions.
Proof
Only 0 item is a trivial one.
7 Two Combinatorial Formula and Quantitative Distributions
From a combinatorial viewpoint, 1. item formula is a binomial coefficient \({m \atopwithdelims ()p}, 0\le p \le m\), to show various partition properties with relevant parameters. For convenient illustration, two expressions are selected: \(\{m-p\}\{p\}\) and \(\{2q\}\{m-2q\}\) from 2 clusters of 2b item of Type B.
7.1 Case I. \(\{m-p\}\{p\}\)
In combinatorics, the following identity for binomial coefficients:
is Vandermonde’s identity (or Vandermonde’s convolution), for any nonnegative integers r, m, n. The identity is named after Alexandre-Théophile Vandermonde (1772), although it was already known in 1303 by the Chinese mathematician Zhu Shijie (Chu Shi-Chieh) [2, 3, 5, 12].
Applying Chu-Vandermonde’s identity to identify \(\{m-p\}\{p\}\) as \(f_1\) and \(f_2\) in Eq. (18), the binomial coefficient in level \(n=2\) can be written as
In this way, each binomial coefficient \({m \atopwithdelims ()p}\) is composed of \(p+1\) pairs of binomial coefficient multiplications and a total of sums on relevant groups.
Theorem 1
For all coefficients of Type B, sum of all coefficients in \(\{m-p\}\{p\}, 0\le p \le m\) is equal to \(2^m\).
Proof
Since
so
According to Theorem 1, all parameters of \(\{{m-p \atopwithdelims ()k}{p \atopwithdelims ()k}\}\) are distributed in \((m+1)^2\) 2D array.
For e.g., while \(m=10\), all coefficients are in \(11\times 11\) region and nontrivial values are composed of a triangle shape with reflect symmetric properties on p values.
7.2 Case II. \(\{2q\}\{m-2q\}\)
Applying Chu-Vandermonde’s identity to identify \(\{2q\}\{m-2q\}\) as \(f_1\) and \(f_2\) in Eq. (18), the binomial coefficient in level \(n=2\) can be written as
By using this formula, it is possible to select a special q value in \(\{{2q \atopwithdelims ()k}{m-2q \atopwithdelims ()p-k}\}\) to form \(\lfloor m/2 \rfloor +1\) 2D coefficient distributions.
Theorem 2
For Type B \(\{2q\}\{m-2q\}, 0\le p \le m, 0\le q \le \lfloor m/2 \rfloor \) equation, selecting a proper value of q, all coefficients are distributed in \(\lfloor m/2 \rfloor +1\) 2D arrays and the sum of total coefficients in a 2D array is equal to \(2^m\).
Proof
Since
so
According to Theorem 2, \(\{{2q \atopwithdelims ()k}{m-2q \atopwithdelims ()p-k}\}\) coefficients are distributed in \(\lfloor m/2 \rfloor +1\) levels of \((m+1)\times (m+1)\) 2D planes.
For e.g., while \(m=10\), all coefficients are arranged on 6 levels of \(11\times 11\) regions with multiple symmetric properties.
\(m=10,q=0\):
\(\cdots \)
\(m=10,q=3\):
\(\cdots \)
\(m=10,q=5\):
7.3 Result Analysis
Two formulas selected from 2b item of Type B show completely different properties. In Case I, for a given m, all coefficients are distributed in one triangle area with reflection properties on p direction.
However, Case II provides multiple levels of 2D distributions and each one is corresponding to a selected q value. From three listed conditions, \(q=0\) and \(q=5\) are linear structures, the first one is located on diagonal positions of the plane and the second one is located on \(k=0,p=\{0, 1, \ldots , 10\}\) a horizontal region. While \(0<q<5\), all distributions are shown in as parallelograms. Each line is shown in special symmetries. We can observe associated with variations of q values, horizontal projection keeps the same, however, the vertical projection will be changed from \(q=0\) binomial distribution, to be a pulse on \(q=\lfloor m/2 \rfloor \) condition. This type of controllable properties could be useful to explore future advanced applications.
8 Conclusion
A new approach to decompose binomial coefficients under permutative and associative operations is proposed. Using this approach, it is feasible to investigate four meta measures in global invariant spaces. The resulting set of 192 configurations is categorized into standard group theory mechanism. From a statistic viewpoint, Type A (Five levels in 16 clusters) and Type B (Five levels in 12 clusters) provide global identifications on complicated partitions on wider restrictions, further theoretical explorations and practical applications are deeply expected in the coming period.
References
J.R. Chen, Combinatorial Mathematics (Harbin Institute of Technology Press, Harbin, 2012). (in Chinese)
H.W. Gould, Some generalizations of Vandermonde’s convolution. Am. Math. Mon. 63(2), 84–91 (1956)
H.W. Gould, Combinatorial Identities (Morgantown Printing and Binding Company, Morganton, 1972)
M. Hall, Combinatorial Theory, 2nd edn. (Blaisdell, New York, 1986)
L.K. Hua, Loo-Keng Hua Selected Papers (Springer, New York, 1982)
D.E. Knuth, The Art of Computer Programming, vol. 1, 3rd edn. (Addison-Wesley, Reading, Massachusett, 1998)
D.E. Knuth, The Art of Computer Programming, Volume 4: Combinatorial Algorithms, Part 1, (Addison-Wesley, Boston, 2011)
F. Morgan, Geometric Measure Theory, 4th edn. (Elsevier, Amsterdam, 2009)
R.P. Stanley, Enumerative Combinatorics, vol. 1, 2nd edn. (Cambridge University Press, Boston, 1997)
D. Stanton, R. Stanton, D. White, Constructive Combinatorics (Springer, New York, 1986)
G.Z. Tu, Combinatorial Enumeration Methods and Applications (Science Press, 1981) (in Chinese)
Vandermonde’s identity. https://en.wikipedia.org/wiki/Vandermonde’s_identity
L.Z. Xu, M.S. Jiang, Z.Q. Zhu, Combinatorial Mathematics of Computation (Shanghai Science and Technology Press, 1983) (in Chinese)
Z.J. Zheng, A. Maeder, The The conjugate classification of the kernel form of the hexagonal grid, in Modern Geometric Computing for Visualization (Springer, 1992), pp. 73–89
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. Front. Electr. Electron. Eng. China 5(2), 163–172 (2010). Higher Educational Press and Springer
J.Z.J. Zheng, C.H.H. Zheng, T.L. Kunii, A framework of variant logic construction for cellular automata, in Cellular Automata—Innovative Modeling for Science and Engineering, ed. by A. Salcido (InTech Press, 2011)
Acknowledgements
The author would like to thank Chris Zheng for refined clustering analysis on random sequences to open a new way in binomial expressions, Yifeng Zheng and Kaiyu Yang for generating binomial coefficients in different conditions and Dr. Dennis Heim for correction of the chapter.
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, J. (2019). Elementary Equations of Variant Measurement. In: Zheng, J. (eds) Variant Construction from Theoretical Foundation to Applications. Springer, Singapore. https://doi.org/10.1007/978-981-13-2282-2_3
Download citation
DOI: https://doi.org/10.1007/978-981-13-2282-2_3
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-13-2281-5
Online ISBN: 978-981-13-2282-2
eBook Packages: EngineeringEngineering (R0)