Tag

Sort by:

Pascal matrix

Three types of matrices can be obtained by writing Pascal's triangle as a lower triangular matrix and truncating appropriately: a symmetric matrix with , a lower triangular matrix with , and an upper triangular matrix with , where , 1, ..., . For example, for , these would be given by(1)(2)(3)The Pascal -matrix or order is implemented in the Wolfram Language as LinearAlgebra`PascalMatrix[n].These matrices have some amazing properties. In particular, their determinants are all equal to 1(4)and(5)(Edelman and Strang).Edelman and Strang give four proofs of the identity (5), themost straightforward of which is(6)(7)(8)(9)where Einstein summation has been used.

Erdős squarefree conjecture

The central binomial coefficient is never squarefree for . This was proved true for all sufficiently large by Sárkőzy's theorem. Goetgheluck (1988) proved the conjecture true for and Vardi (1991) for . The conjecture was proved true in its entirety by Granville and Ramare (1996).

Pascal's formula

Each subsequent row of Pascal's triangle is obtained by adding the two entries diagonally above. This follows immediately from the binomial coefficient identity(1)(2)(3)(4)(5)

Nexus number

A nexus number is a figurate number built up of the nexus of cells less than steps away from a given cell. The th -dimensional nexus number is given by(1)(2)where is a binomial coefficient. The symbolic representations and sequences for first few -dimensional nexus numbers are given in the table below.name01unit1odd number2hex number3rhombic dodecahedral number4nexus numberOEIS, , , ...01, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...1A0054081, 3, 5, 7, 9, 11, 13, 15, 17, 19, ...2A0032151, 7, 19, 37, 61, 91, 127, 169, 217, ...3A0059171, 15, 65, 175, 369, 671, 1105, 1695, 2465, ...4A0225211, 31, 211, 781, 2101, 4651, 9031, 15961, ...

Dilcher's formula

(1)where is a binomial coefficient (Dilcher 1995, Flajolet and Sedgewick 1995, Prodinger 2000). An inverted version is given by(2)where is a harmonic number of order (Hernández 1999, Prodinger 2000). A q-analog of (1) is given by(3)where is a q-binomial coefficient (Prodinger 2000).

Waring formula

where is the floor function and is a binomial coefficient.

Multinomial coefficient

The multinomial coefficients(1)are the terms in the multinomial series expansion. In other words, the number of distinct permutations in a multiset of distinct elements of multiplicity () is (Skiena 1990, p. 12).The multinomial coefficient is returned by the Wolfram Language function Multinomial[n1, n2, ...].The special case is given by(2)where is a binomial coefficient.The multinomial coefficients satisfy(3)(4)and so on (Gosper 1972).

Deficiency

Given binomial coefficient , writefor , where contains only those prime factors . Then the number of for which (i.e., for which all the factors of are is called the deficiency of (Erdős et al. 1993, Guy 1994). The following table gives the good binomial coefficients (i.e., those with ) having deficiency (Erdős et al. 1993), and Erdős et al. (1993) conjecture that there are no other with .good binomial coefficients1, , , , , , , ...2, , , , , ,, 3, , , , , 49

Trinomial triangle

The trinomial triangle is a number triangle of trinomial coefficients. It can be obtained by starting with a row containing a single "1" and the next row containing three 1s and then letting subsequent row elements be computed by summing the elements above to the left, directly above, and above to the right:(OEIS A027907).The plot above shows the binary representations for the first 255 (top figure) and 511 (bottom figure) terms of a flattened trinomial triangle.

Multichoose

The number of multisets of length on symbols is sometimes termed " multichoose ," denoted by analogy with the binomial coefficient . multichoose is given by the simple formulawhere is a multinomial coefficient. For example, 3 multichoose 2 is given by 6, since the possible multisets of length 2 on three elements are , , , , , and .The first few values of are given in the following table. 12345112345213610153141020354151535705162156126Multichoose problems are sometimes called "bars and stars" problems. For example, suppose a recipe called for 5 pinches of spice, out of 9 spices. Each possibility is an arrangement of 5 spices (stars) and dividers between categories (bars), where the notation indicates a choice of spices 1, 1, 5, 6, and 9 (Feller 1968, p. 36). The number of possibilities in this case is then ,..

Christmas stocking theorem

The Christmas stocking theorem, also known as the hockey stick theorem, states that the sum of a diagonal string of numbers in Pascal's triangle starting at the th entry from the top (where the apex has ) on left edge and continuing down rows is equal to the number to the left and below (the "toe") bottom of the diagonal (the "heel"; Butterworth 2002). This follows from the identitywhere is a binomial coefficient.

Trinomial coefficient

A trinomial coefficient is a coefficient of the trinomial triangle. Following the notation of Andrews (1990), the trinomial coefficient , with and , is given by the coefficient of in the expansion of . Therefore,(1)The trinomial coefficient can be given by the closed form(2)where is a Gegenbauer polynomial.Equivalently, the trinomial coefficients are defined by(3)The trinomial coefficients also have generatingfunction(4)(5)i.e.,(6)The trinomial triangle gives the triangle oftrinomial coefficients,(7)(OEIS A027907).The central column of the trinomial triangle gives the centraltrinomial coefficients.The trinomial coefficient is also given by the number of permutations of symbols, each , 0, or 1, which sum to . For example, there are seven permutations of three symbols which sum to 0, , , , , and , , , so .An alternative (but different) definition of the trinomial coefficients is as the coefficients in (Andrews 1990), which is therefore..

Mill curve

The -roll mill curve is given by the equationwhere is a binomial coefficient.

Central trinomial coefficient

The th central trinomial coefficient is defined as the coefficient of in the expansion of . It is therefore the middle column of the trinomial triangle, i.e., the trinomial coefficient . The first few central trinomial coefficients for , 2, ... are 1, 3, 7, 19, 51, 141, 393, ... (OEIS A002426).The central trinomial coefficient is also gives the number of permutations of symbols, each , 0, or 1, which sum to 0. For example, there are seven such permutations of three symbols: , , , , and , , .The generating function is given by(1)(2)The central trinomial coefficients are given by the recurrenceequation(3)with , but cannot be expressed as a fixed number of hypergeometric terms (Petkovšek et al. 1996, p. 160).The coefficients satisfy the congruence(4)(T. D. Noe, pers. comm., Mar. 15, 2005) and(5)for a prime, which is easy to show using Fermat's little theorem (T. D. Noe, pers. comm., Oct. 26, 2005).Sum..

Lucas correspondence theorem

Let be prime and(1)(2)then(3)This is proved in Fine (1947).This theorem is the underlying reason that the binomial coefficient mod 2 can be computed using bitwise operations AND(NOT(),), giving the Sierpiński sieve.

Central fibonomial coefficient

The th central fibonomial coefficient is defined as(1)(2)where is a fibonomial coefficient, is a Fibonacci number, is the golden ratio, and is a q-Pochhammer symbol (E. W. Weisstein, Dec. 8, 2009).For , 2, ..., the first few are 1, 6, 60, 1820, 136136, ... (OEIS A003267).

Logarithmic binomial theorem

For all integers and ,where is the harmonic logarithm and is a Roman coefficient. For , the logarithmic binomial theorem reduces to the classical binomial theorem for positive , since for , for , and when .Similarly, taking and gives the negative binomial series. Roman (1992) gives expressions obtained for the case and which are not obtainable from the binomial theorem.

Central binomial coefficient

The th central binomial coefficient is defined as(1)(2)where is a binomial coefficient, is a factorial, and is a double factorial.These numbers have the generating function(3)The first few values are 2, 6, 20, 70, 252, 924, 3432, 12870, 48620, 184756, ... (OEIS A000984). The numbers of decimal digits in for , 1, ... are 1, 6, 59, 601, 6019, 60204, 602057, 6020597, ... (OEIS A114501). These digits converge to the digits in the decimal expansion of (OEIS A114493).The central binomial coefficients are never prime except for .A scaled form of the central binomial coefficient is known as a Catalannumber(4)Erdős and Graham (1975) conjectured that the central binomial coefficient is never squarefree for , and this is sometimes known as the Erdős squarefree conjecture. Sárkőzy's theorem (Sárkőzy 1985) provides a partial solution which states that the binomial coefficient is never squarefree for all sufficiently..

Star of david theorem

As originally stated by Gould (1972),(1)where GCD is the greatest common divisor and is a binomial coefficient. This was subsequently extended by D. Singmaster to(2)(Sato 1975), and generalized by Sato (1975) to(3)An even larger generalization was obtained by Hitotumatu and Sato (1975), who defined(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15)with(16)and showed that each of the twelve binomial coefficients , , , , , , , , , , , and has equal greatest common divisor.A second star of David theorem states that if two triangles are drawn centered on a given element of Pascal's triangle as illustrated above, then the products of the three numbers in the associated points of each of the two stars are the same (Butterworth 2002). This follows from the fact that(17)(18)(19)The second star of David theorem holds true not only for the usual binomial coefficients, but also for q-binomial coefficients, where the common product is given by(20)In..

Klee's identity

Klee's identity is the binomial sumwhere is a binomial coefficient. For , 1, ... and , 1,..., the following array is obtained.10000000000000000000001000000000020000000001100000000040000000061000000004600000001151000000020800000015281(OEIS A092865)

Jonah formula

A formula for the generalized Catalan number . The general formula iswhere is a binomial coefficient, although Jonah's original formula corresponded to , (Hilton and Pederson 1991).

Staircase walk

The number of staircase walks on a grid with horizontal lines and vertical lines is given by(Vilenkin 1971, Mohanty 1979, Narayana 1979, Finch 2003). The first few values for , 2, ..., are 1, 2, 6, 20, 70, 252, ... (OEIS A000984), which are the central binomial coefficients. A Dyck path is a staircase walk from to which never crosses (but may touch) the diagonal .

Idempotent number

The idempotent numbers are given bywhere is a Bell polynomial and is a binomial coefficient. A table of the first few is given below.A000027A001788A036216A040075A050982A050988A050989112213361442412155809020166240540240301776722835224052542188179213608179207000100856994608612361290247875018144176410101152026244086016078750027216041160

Binomial coefficient

The binomial coefficient is the number of ways of picking unordered outcomes from possibilities, also known as a combination or combinatorial number. The symbols and are used to denote a binomial coefficient, and are sometimes read as " choose ." therefore gives the number of k-subsets possible out of a set of distinct items. For example, The 2-subsets of are the six pairs , , , , , and , so . The number of lattice paths from the origin to a point ) is the binomial coefficient (Hilton and Pedersen 1991).The value of the binomial coefficient for nonnegative and is given explicitly by(1)where denotes a factorial. Writing the factorial as a gamma function allows the binomial coefficient to be generalized to noninteger arguments (including complex and ) as(2)For nonnegative integer arguments, the gamma function reduces to factorials, leading to(3)which is Pascal's triangle. Using the symmetryformula(4)for integer , and complex , this..

Sárkőzy's theorem

A partial solution to the Erdős squarefree conjecture which states that the binomial coefficient is never squarefree for all sufficiently large . Sárkőzy (1985) showed that if is the square part of the binomial coefficient , thenwhere is the Riemann zeta function. An upper bound on of has been obtained.

Good binomial coefficient

A binomial coefficient with is called good if its least prime factor satisfies(Erdős et al. 1993). This is equivalent to the requirement thatThe first few good binomial coefficients are therefore , , , , , , , , .... Good binomial coefficients are closely related to the Erdős-selfridge function , which gives the least integer such that is good.

Bernoulli triangle

(1)The number triangle illustrated above (OEIS A008949) composed of the partial sums of binomial coefficients,(2)(3)where is a gamma function and is a hypergeometric function.The plot above shows the binary representations for the first 255 (top figure) and 511 (bottom figure) terms of a flattened Bernoulli triangle.

Franel number

The Franel numbers are the numbers(1)where is a binomial coefficient. The first few values for , 1, ... are 1, 2, 10, 56, 346, ... (OEIS A000172). They arise in the first Strehl identity(2)and can be written in closed form as(3)where is a generalized hypergeometric function.They are given by the integral(4)where is a Laguerre polynomial.They are also given by the recurrence equation(5)with and .

Fibonomial coefficient

The fibonomial coefficient (sometimes also called simply the Fibonacci coefficient) is defined by(1)where and is a Fibonacci number. This coefficient satisfies(2)for , where is a Lucas number.The triangle of fibonomial coefficients is given by(3)(OEIS A010048). may be called the central fibonomial coefficient by analogy with the central binomial coefficient.

Pascal's triangle

Pascal's triangle is a number triangle with numbersarranged in staggered rows such that(1)where is a binomial coefficient. The triangle was studied by B. Pascal, although it had been described centuries earlier by Chinese mathematician Yanghui (about 500 years earlier, in fact) and the Persian astronomer-poet Omar Khayyám. It is therefore known as the Yanghui triangle in China. Starting with , the triangle is(2)(OEIS A007318). Pascal's formula shows that each subsequent row is obtained by adding the two entries diagonally above,(3)The plot above shows the binary representations for the first 255 (top figure) and 511 (bottom figure) terms of a flattened Pascal's triangle.The first number after the 1 in each row divides all other numbers in that row iff it is a prime.The sums of the number of odd entries in the first rows of Pascal's triangle for , 1, ... are 0, 1, 3, 5, 9, 11, 15, 19, 27, 29, 33, 37, 45, 49, ... (OEIS A006046). It is then..

Exceptional binomial coefficient

A binomial coefficient is said to be exceptional if . The following table gives the exception binomial coefficients which are also good binomial coefficients, are not of the form , and have specified least prime factors .exceptional binomial coefficients1317, , , , ,, , 19, 2329

Dyson's conjecture

Based on a problem in particle physics, Dyson (1962abc) conjectured that the constantterm in the Laurent seriesis the multinomial coefficientThe theorem was proved by Wilson (1962) and independently by Gunson (1962). A definitive proof was subsequently published by Good (1970).

Binomial identity

Roman (1984, p. 26) defines "the" binomial identity as the equation(1)Iff the sequence satisfies this identity for all in a field of field characteristic 0, then is an associated sequence known as a binomial-type sequence.In general, a binomial identity is a formula expressing products of factors as a sum over terms, each including a binomial coefficient . The prototypical example is the binomial theorem(2)for . Abel (1826) gave a host of such identities (Riordan 1979, Roman 1984), some of which include(3)(4)(Abel 1826, Riordan 1979, p. 18; Roman 1984, pp. 30 and 73), and(5)(Saslaw 1989).

Balanced binomial coefficient

An integer is -balanced for a prime if, among all nonzero binomial coefficients for , ..., (mod ), there are equal numbers of quadratic residues and nonresidues (mod ). Let be the set of integers , , that are -balanced. Among all the primes , only those with , 3, and 11 have .The following table gives the -balanced integers for small primes (OEIS A093755).2357111317

Schmidt's problem

Schmidt (1993) proposed the problem of determining if for any integer , the sequence of numbers defined by the binomial sums(1)are all integers.The following table gives the first few values of for small .OEISvalues1A0018501, 3, 13, 63, 321, 1683, 8989, 48639, ...2A0052591, 5, 73, 1445, 33001, 819005, ...3A0928131, 9, 433, 36729, 3824001, 450954009, ...4A0928141, 17, 2593, 990737, 473940001, ...5A0928151, 33, 15553, 27748833, 61371200001, ...This was proved by Strehl (1993, 1994) and Schmidt (1995) for the case , corresponding to the Franel numbers. Strehl (1994) also found an explicit expression for the case . The resulting identities for are therefore known as the Strehl identities. The problem was restated in Graham et al. (1994, pp. 256 and 549), who indicated that H. S. Wilf had shown to be an integer for any for (Zudilin 2004).The problem was answered in the affirmative by Zudilin (2004), who found explicit expressions..

Worpitzky's identity

where is an Eulerian number and is a binomial coefficient (Worpitzky 1883; Comtet 1974, p. 242).

Strehl identities

The first Strehl identity is the binomial sum identity(Strehl 1993, 1994; Koepf 1998, p. 55), which are the so-called Franel numbers. For , 2, ..., the first few terms are 1, 2, 10, 56, 346, 2252, 15184, 104960, ... (OEIS A000172).The second Strehl identity is the binomial sum identity(Strehl 1993, 1994; Koepf 1998, p. 55) that is the case of Schmidt's problem. For , 1, 2, ..., these give the Apéry numbers 1, 5, 73, 1445, 33001, 819005, ... (OEIS A005259).

Binomial sums

The important binomial theorem states that(1)Consider sums of powers of binomial coefficients(2)(3)where is a generalized hypergeometric function. When they exist, the recurrence equations that give solutions to these equations can be generated quickly using Zeilberger's algorithm.For , the closed-form solution is given by(4)i.e., the powers of two. obeys the recurrence relation(5)For , the closed-form solution is given by(6)i.e., the central binomial coefficients. obeys the recurrence relation(7)Franel (1894, 1895) was the first to obtain recurrences for ,(8)(Riordan 1980, p. 193; Barrucand 1975; Cusick 1989; Jin and Dickinson 2000), so are sometimes called Franel numbers. The sequence for cannot be expressed as a fixed number of hypergeometric terms (Petkovšek et al. 1996, p. 160), and therefore has no closed-form hypergeometric expression.Franel (1894, 1895) was also the first to obtain the recurrence..

Binomial theorem

There are several closely related results that are variously known as the binomial theorem depending on the source. Even more confusingly a number of these (and other) related results are variously known as the binomial formula, binomial expansion, and binomial identity, and the identity itself is sometimes simply called the "binomial series" rather than "binomial theorem."The most general case of the binomial theorem is the binomialseries identity(1)where is a binomial coefficient and is a real number. This series converges for an integer, or . This general form is what Graham et al. (1994, p. 162). Arfken (1985, p. 307) calls the special case of this formula with the binomial theorem.When is a positive integer , the series terminates at and can be written in the form(2)This form of the identity is called the binomial theorem by Abramowitz and Stegun (1972, p. 10).The differing terminologies are..

Binomial series

There are several related series that are known as the binomial series.The most general is(1)where is a binomial coefficient and is a real number. This series converges for an integer, or (Graham et al. 1994, p. 162). When is a positive integer , the series terminates at and can be written in the form(2)The theorem that any one of these (or several other related forms) holds is knownas the binomial theorem.Special cases give the Taylor series(3)(4)where is a Pochhammer symbol and . Similarly,(5)(6)which is the so-called negative binomial series.In particular, the case gives(7)(8)(9)(OEIS A001790 and A046161), where is a double factorial and is a binomial coefficient.The binomial series has the continued fractionrepresentation(10)(Wall 1948, p. 343).

Roman coefficient

A generalization of the binomial coefficientwhose notation was suggested by Knuth,(1)where is a Roman factorial. The above expression is read "Roman choose ." Whenever the binomial coefficient is defined (i.e., or ), the Roman coefficient agrees with it. However, the Roman coefficients are defined for values for which the binomial coefficients are not, e.g.,(2)(3)where(4)The Roman coefficients also satisfy properties like those of the binomialcoefficient,(5)(6)an analog of Pascal's formula(7)and a curious rotation/reflection law due to Knuth(8)(Roman 1992).

Check the price
for your project
we accept
Money back
guarantee
100% quality