Pascal's rule

In mathematics, Pascal's rule (or Pascal's formula) is a combinatorial identity about binomial coefficients. It states that for positive natural numbers n and k, where is a binomial coefficient; one interpretation of the coefficient of the xk term in the expansion of (1 + x)n. There is no restriction on the relative sizes of n and k, since, if n < k the value of the binomial coefficient is zero and the identity remains valid. Pascal's rule can also be viewed as a statement that the formula solves the linear two-dimensional difference equation over the natural numbers. Thus, Pascal's rule is also a statement about a formula for the numbers appearing in Pascal's triangle. Pascal's rule can also be generalized to apply to multinomial coefficients. Pascal's rule has an intuitive combinatorial meaning, that is clearly expressed in this counting proof. Proof. Recall that equals the number of subsets with k elements from a set with n elements. Suppose one particular element is uniquely labeled X in a set with n elements. To construct a subset of k elements containing X, include X and choose k − 1 elements from the remaining n − 1 elements in the set. There are such subsets. To construct a subset of k elements not containing X, choose k elements from the remaining n − 1 elements in the set. There are such subsets. Every subset of k elements either contains X or not. The total number of subsets with k elements in a set of n elements is the sum of the number of subsets containing X and the number of subsets that do not contain X, . This equals ; therefore, . Alternatively, the algebraic derivation of the binomial case follows. Pascal's rule can be generalized to multinomial coefficients. For any integer p such that , and , where is the coefficient of the term in the expansion of . The algebraic derivation for this general case is as follows. Let p be an integer such that , and . Then Merris, Russell. Combinatorics. John Wiley & Sons.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (1)

Related concepts (3)

Related courses (1)

Related lectures (17)

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

A positive combinatorial formula for symplectic Kostka-Foulkes polynomials I: Rows

Thomas Gerber

We prove a conjecture of Lecouvey, which proposes a closed, positive combinatorial formula for symplectic Kostka-Foulkes polynomials, in the case of rows of arbitrary weight. To show this, we construct a new algorithm for computing cocyclage in terms of wh ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2020

Explores advanced counting techniques such as the pigeonhole principle and combinatorial proofs.

Delves into advanced counting methods, combinatorial proofs, recurrence relations, and the Generalized Pigeonhole Principle.

Explores the complexity of calculating binomial coefficients using dynamic programming.

In mathematics, Pascal's triangle is a triangular array of the binomial coefficients arising 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. The rows of Pascal's triangle are conventionally enumerated starting with row at the top (the 0th row). The entries in each row are numbered from the left beginning with and are usually staggered relative to the numbers in the adjacent rows.

In elementary algebra, the binomial theorem (or binomial expansion) describes the algebraic expansion of powers of a binomial. According to the theorem, it is possible to expand the polynomial (x + y)n into a sum involving terms of the form axbyc, where the exponents b and c are nonnegative integers with b + c = n, and the coefficient a of each term is a specific positive integer depending on n and b. For example, for n = 4, The coefficient a in the term of axbyc is known as the binomial coefficient or (the two have the same value).

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 ≥ k ≥ 0 and is written It is the coefficient of the xk term in the polynomial expansion of the binomial power (1 + x)n; this coefficient can be computed by the multiplicative formula which using factorial notation can be compactly expressed as For example, the fourth power of 1 + x is and the binomial coefficient is the coefficient of the x2 term.