Trinomial triangle

Last updated October 30, 2024

The trinomial triangle is a variation of Pascal's triangle. The difference between the two is that an entry in the trinomial triangle is the sum of the three (rather than the two in Pascal's triangle) entries above it:

Properties

The $n$ -th row corresponds to the coefficients in the polynomial expansion of the expansion of the trinomial $(1+x+x^{2})$ raised to the $n$ -th power:^[1]

\left(1+x+x^{2}\right)^{n}=\sum _{j=0}^{2n}{n \choose j-n}_{2}x^{j}=\sum _{k=-n}^{n}{n \choose k}_{2}x^{n+k}

or, symmetrically,

\left(1+x+1/x\right)^{n}=\sum _{k=-n}^{n}{n \choose k}_{2}x^{k}

,

hence the alternative name trinomial coefficients because of their relationship to the multinomial coefficients:

{\displaystyle {n \choose k}_{2}=\sum _{\textstyle {0\leq \mu ,\nu \leq n \atop \mu +2\nu =n+k}}{\frac {n!}{\mu

Furthermore, the diagonals have interesting properties, such as their relationship to the triangular numbers.

The sum of the elements of $n$ -th row is $3^{n}$ .

Recurrence formula

The trinomial coefficients can be generated using the following recurrence formula:^[1]

{0 \choose 0}_{2}=1

,

{n+1 \choose k}_{2}={n \choose k-1}_{2}+{n \choose k}_{2}+{n \choose k+1}_{2}

for

n\geq 0

,

where ${n \choose k}_{2}=0$ for $\ k<-n$ and $\ k>n$ .

Central trinomial coefficients

The middle entries of the trinomial triangle

1, 1, 3, 7, 19, 51, 141, 393, 1107, 3139, … (sequence A002426 in the OEIS )

were studied by Euler and are known as central trinomial coefficients.

The only known prime central trinomial coefficients are 3, 7 and 19 at n = 2, 3 and 4.

The $n$ -th central trinomial coefficient is given by

{n \choose 0}_{2}=\sum _{k=0}^{n}{\frac {n(n-1)\cdots (n-2k+1)}{(k!)^{2}}}=\sum _{k=0}^{n}{n \choose 2k}{2k \choose k}.

Their generating function is^[2]

1+x+3x^{2}+7x^{3}+19x^{4}+\ldots ={\frac {1}{\sqrt {(1+x)(1-3x)}}}.

Euler noted the following exemplum memorabile inductionis fallacis ("notable example of fallacious induction"):

3{n+1 \choose 0}_{2}-{n+2 \choose 0}_{2}=F_{n}(F_{n}+1)

for

0\leq n\leq 7

,

where $F_{n}$ is the n-th Fibonacci number. For larger $n$ , however, this relationship is incorrect. George Andrews explained this fallacy using the general identity^[3]

2\sum _{k\in \mathbb {Z} }\left[{n+1 \choose 10k}_{2}-{n+1 \choose 10k+1}_{2}\right]=F_{n}(F_{n}+1).

Applications

In chess

Number of ways to reach a cell with the minimum number of moves

The triangle corresponds to the number of possible paths that can be taken by the king in a game of chess. The entry in a cell represents the number of different paths (using a minimum number of moves) the king can take to reach the cell.

In combinatorics

The coefficient of $x^{k}$ in the expansion of $\left(1+x+x^{2}\right)^{n}$ gives the number of different ways to draw $k$ cards from two identical sets of $n$ playing cards each.^[4] For example, from two sets of the three cards A, B, C, the different drawings are:

Number of selected cards	Number of options	Options
0	1
1	3	A, B, C
2	6	AA, AB, AC, BB, BC, CC
3	7	AAB, AAC, ABB, ABC, ACC, BBC, BCC
4	6	AABB, AABC, AACC, ABBC, ABCC, BBCC
5	3	AABBC, AABCC, ABBCC
6	1	AABBCC

For example,

6={3 \choose 2-3}_{2}={3 \choose 0}{3 \choose 2}+{3 \choose 1}{2 \choose 0}=1\cdot 3+3\cdot 1

.

In particular, this provides the formula ${24 \choose 12-24}_{2}={24 \choose -12}_{2}={24 \choose 12}_{2}$ for the number of different hands in the card game Doppelkopf .

Alternatively, it is also possible to arrive at this expression by considering the number of ways of choosing $p$ pairs of identical cards from the two sets, which is the binomial coefficient ${n \choose p}$ . The remaining $k-2p$ cards can then be chosen in ${n-p \choose k-2p}$ ways,^[4] which can be written in terms of the binomial coefficients as

{n \choose k-n}_{2}=\sum _{p=\max(0,k-n)}^{\min(n,[k/2])}{n \choose p}{n-p \choose k-2p}

.

The example above corresponds to the three ways of selecting two cards without pairs of identical cards (AB, AC, BC) and the three ways of selecting a pair of identical cards (AA, BB, CC).

Related Research Articles

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers $n \geq k \geq 0$ and is written $It is the coefficient of the x k term in the polynomial expansion of the binomial power (1 + x) n; this coefficient can be computed by the multiplicative formula$

The Möbius function is a multiplicative function in number theory introduced by the German mathematician August Ferdinand Möbius in 1832. It is ubiquitous in elementary and analytic number theory and most often appears as part of its namesake the Möbius inversion formula. Following work of Gian-Carlo Rota in the 1960s, generalizations of the Möbius function were introduced into combinatorics, and are similarly denoted $.$

In mathematics, the $L p$ spaces are function spaces defined using a natural generalization of the $p$ -norm for finite-dimensional vector spaces. They are sometimes called Lebesgue spaces, named after Henri Lebesgue, although according to the Bourbaki group they were first introduced by Frigyes Riesz.

In mathematics, Pascal's triangle is an infinite triangular array of the binomial coefficients which play a crucial role in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although other mathematicians studied it centuries before him in Persia, India, China, Germany, and Italy.

In the mathematical field of real analysis, the monotone convergence theorem is any of a number of related theorems proving the good convergence behaviour of monotonic sequences, i.e. sequences that are non-increasing, or non-decreasing. In its simplest form, it says that a non-decreasing bounded-above sequence of real numbers $converges to its smallest upper bound, its supremum. Likewise, a non-increasing bounded-below sequence converges to its largest lower bound, its infimum. In particular, infinite sums of non-negative numbers converge to the supremum of the partial sums if and only if the partial sums are bounded.$

In mathematical analysis, Hölder's inequality, named after Otto Hölder, is a fundamental inequality between integrals and an indispensable tool for the study of $L p$ spaces.

In mathematics, Pascal's pyramid is a three-dimensional arrangement of the trinomial numbers, which are the coefficients of the trinomial expansion and the trinomial distribution. Pascal's pyramid is the three-dimensional analog of the two-dimensional Pascal's triangle, which contains the binomial numbers and relates to the binomial expansion and the binomial distribution. The binomial and trinomial numbers, coefficients, expansions, and distributions are subsets of the multinomial constructs with the same names.

In mathematics, the representation theory of the symmetric group is a particular case of the representation theory of finite groups, for which a concrete and detailed theory can be obtained. This has a large area of potential applications, from symmetric function theory to quantum chemistry studies of atoms, molecules and solids.

In mathematics, the Bernoulli scheme or Bernoulli shift is a generalization of the Bernoulli process to more than two possible outcomes. Bernoulli schemes appear naturally in symbolic dynamics, and are thus important in the study of dynamical systems. Many important dynamical systems exhibit a repellor that is the product of the Cantor set and a smooth manifold, and the dynamics on the Cantor set are isomorphic to that of the Bernoulli shift. This is essentially the Markov partition. The term shift is in reference to the shift operator, which may be used to study Bernoulli schemes. The Ornstein isomorphism theorem shows that Bernoulli shifts are isomorphic when their entropy is equal.

In mathematics, Schur polynomials, named after Issai Schur, are certain symmetric polynomials in n variables, indexed by partitions, that generalize the elementary symmetric polynomials and the complete homogeneous symmetric polynomials. In representation theory they are the characters of polynomial irreducible representations of the general linear groups. The Schur polynomials form a linear basis for the space of all symmetric polynomials. Any product of Schur polynomials can be written as a linear combination of Schur polynomials with non-negative integral coefficients; the values of these coefficients is given combinatorially by the Littlewood–Richardson rule. More generally, skew Schur polynomials are associated with pairs of partitions and have similar properties to Schur polynomials.

In mathematics, the Wasserstein distance or Kantorovich–Rubinstein metric is a distance function defined between probability distributions on a given metric space $. It is named after Leonid Vaseršteĭn.$

The tetrad formalism is an approach to general relativity that generalizes the choice of basis for the tangent bundle from a coordinate basis to the less restrictive choice of a local basis, i.e. a locally defined set of four linearly independent vector fields called a tetrad or vierbein. It is a special case of the more general idea of a vielbein formalism, which is set in (pseudo-)Riemannian geometry. This article as currently written makes frequent mention of general relativity; however, almost everything it says is equally applicable to (pseudo-)Riemannian manifolds in general, and even to spin manifolds. Most statements hold simply by substituting arbitrary $for . In German, " vier " translates to "four", and " viel " to "many".$

In mathematics, the Littlewood–Richardson rule is a combinatorial description of the coefficients that arise when decomposing a product of two Schur functions as a linear combination of other Schur functions. These coefficients are natural numbers, which the Littlewood–Richardson rule describes as counting certain skew tableaux. They occur in many other mathematical contexts, for instance as multiplicity in the decomposition of tensor products of finite-dimensional representations of general linear groups, or in the decomposition of certain induced representations in the representation theory of the symmetric group, or in the area of algebraic combinatorics dealing with Young tableaux and symmetric polynomials.

In mathematics, the Robinson–Schensted–Knuth correspondence, also referred to as the RSK correspondence or RSK algorithm, is a combinatorial bijection between matrices $A$ with non-negative integer entries and pairs $(P, Q)$ of semistandard Young tableaux of equal shape, whose size equals the sum of the entries of $A$ . More precisely the weight of $P$ is given by the column sums of $A$ , and the weight of $Q$ by its row sums. It is a generalization of the Robinson–Schensted correspondence, in the sense that taking $A$ to be a permutation matrix, the pair $(P, Q)$ will be the pair of standard tableaux associated to the permutation under the Robinson–Schensted correspondence.

In probability theory, a McKean–Vlasov process is a stochastic process described by a stochastic differential equation where the coefficients of the diffusion depend on the distribution of the solution itself. The equations are a model for Vlasov equation and were first studied by Henry McKean in 1966. It is an example of propagation of chaos, in that it can be obtained as a limit of a mean-field system of interacting particles: as the number of particles tends to infinity, the interactions between any single particle and the rest of the pool will only depend on the particle itself.

Stochastic portfolio theory (SPT) is a mathematical theory for analyzing stock market structure and portfolio behavior introduced by E. Robert Fernholz in 2002. It is descriptive as opposed to normative, and is consistent with the observed behavior of actual markets. Normative assumptions, which serve as a basis for earlier theories like modern portfolio theory (MPT) and the capital asset pricing model (CAPM), are absent from SPT.

In combinatorial mathematics, the hook length formula is a formula for the number of standard Young tableaux whose shape is a given Young diagram. It has applications in diverse areas such as representation theory, probability, and algorithm analysis; for example, the problem of longest increasing subsequences. A related formula gives the number of semi-standard Young tableaux, which is a specialization of a Schur polynomial.

In mathematical physics, Clebsch–Gordan coefficients are the expansion coefficients of total angular momentum eigenstates in an uncoupled tensor product basis. Mathematically, they specify the decomposition of the tensor product of two irreducible representations into a direct sum of irreducible representations, where the type and the multiplicities of these irreducible representations are known abstractly. The name derives from the German mathematicians Alfred Clebsch (1833–1872) and Paul Gordan (1837–1912), who encountered an equivalent problem in invariant theory.

In mathematics, Wiener's lemma is a well-known identity which relates the asymptotic behaviour of the Fourier coefficients of a Borel measure on the circle to its atomic part. This result admits an analogous statement for measures on the real line. It was first discovered by Norbert Wiener.

<span class="mw-page-title-main">Representations of classical Lie groups</span>

In mathematics, the finite-dimensional representations of the complex classical Lie groups $,,,,, can be constructed using the general representation theory of semisimple Lie algebras. The groups,, are indeed simple Lie groups, and their finite-dimensional representations coincide with those of their maximal compact subgroups, respectively,, . In the classification of simple Lie algebras, the corresponding algebras are$

References

1 2 Weisstein, Eric W. "Trinomial Coefficient". MathWorld .
↑ Weisstein, Eric W. "Central Trinomial Coefficient". MathWorld .
↑ George Andrews, Three Aspects for Partitions. Séminaire Lotharingien de Combinatoire, B25f (1990) Online copy
1 2 Andreas Stiller: Pärchenmathematik. Trinomiale und Doppelkopf. ("Pair mathematics. Trinomials and the game of Doppelkopf"). c't Issue 10/2005, p. 181ff