In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, Pascal's rule is a combinatorial

Combinatorics

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...

 identity

Identity (mathematics)

In mathematics, the term identity has several different important meanings:*An identity is a relation which is tautologically true. This means that whatever the number or value may be, the answer stays the same. For example, algebraically, this occurs if an equation is satisfied for all values of...

 about binomial coefficient

Binomial coefficient

In mathematics, binomial coefficients are a family of positive integers that occur as coefficients in the binomial theorem. They are indexed by two nonnegative integers; the binomial coefficient indexed by n and k is usually written \tbinom nk , and it is the coefficient of the x k term in...

s. It states that for any natural number

Natural number

In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

 n we have $\{n-1\backslash choose\; k\}\; +\; \{n-1\backslash choose\; k-1\}\; =\; \{n\backslash choose\; k\}\backslash quad\backslash text\{for\; \}1\; \backslash le\; k\; \backslash le\; n$ where $\{n\backslash choose\; k\}$ is a binomial coefficient. This is also commonly written $\{n\; \backslash choose\; k\}\; +\; \{n\; \backslash choose\; k-1\}\; =\; \{n\; +\; 1\; \backslash choose\; k\}\; \backslash quad\backslash text\{for\; \}\; 1\; \backslash le\; k\; \backslash le\; n\; +\; 1$

Combinatorial proof

Pascal's rule has an intuitive combinatorial meaning. Recall that $\{a\backslash choose\; b\}$ counts in how many ways can we pick a subset

Subset

In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

 with b elements out from a set with a elements. Therefore, the right side of the identity $\{n\backslash choose\; k\}$ is counting how many ways can we get a k-subset out from a set with n elements. Now, suppose you distinguish a particular element 'X' from the set with n elements. Thus, every time you choose k elements to form a subset there are two possibilities: X belongs to the chosen subset or not. If X is in the subset, you only really need to choose k − 1 more objects (since it is known that X will be in the subset) out from the remaining n − 1 objects. This can be accomplished in $n-1\backslash choose\; k-1$ ways. When X is not in the subset, you need to choose all the k elements in the subset from the n − 1 objects that are not X. This can be done in $n-1\backslash choose\; k$ ways. We conclude that the numbers of ways to get a k-subset from the n-set, which we know is $\{n\backslash choose\; k\}$, is also the number $\{n-1\backslash choose\; k-1\}\; +\; \{n-1\backslash choose\; k\}.$ See also Bijective proof

Bijective proof

In combinatorics, bijective proof is a proof technique that finds a bijective function f : A → B between two sets A and B, thus proving that they have the same number of elements, |A| = |B|. One place the technique is useful is where we wish to know the size of A, but can find no direct way of...

.

Algebraic proof

We need to show$\{\; n\; \backslash choose\; k\; \}\; +\; \{\; n\; \backslash choose\; k-1\; \}\; =\; \{\; n+1\; \backslash choose\; k\; \}.$ Let us begin by writing the left-hand side as $\backslash frac\{n!\}\{k!(n-k)!\}\; +\; \backslash frac\{n!\}\{(k-1)!(n-(k-1))!\}.$ Getting a common denominator and simplifying, we have

Generalization

Let $n,\; k\_1,\; k\_2,\; k\_3,\backslash dots\; ,k\_p,\; p\; \backslash in\; \backslash mathbb\{N\}^*\; \backslash ,\backslash !$ and $n=k\_1+k\_2+k\_3+\; \backslash cdots\; +k\_p\; \backslash ,\backslash !$. Then NEWLINE

NEWLINE

$$

NEWLINE \begin{align} & {} \quad {n-1\choose k_1-1,k_2,k_3, \dots, k_p}+{n-1\choose k_1,k_2-1,k_3,\dots, k_p}+\cdots+{n-1\choose k_1,k_2,k_3,\dots,k_p-1} \\ & = \frac{(n-1)!}{(k_1-1)!k_2!k_3! \cdots k_p!} + \frac{(n-1)!}{k_1!(k_2-1)!k_3!\cdots k_p!} + \cdots + \frac{(n-1)!}{k_1!k_2!k_3! \cdots (k_p-1)!} \\ & = \frac{k_1(n-1)!}{k_1!k_2!k_3! \cdots k_p!} + \frac{k_2(n-1)!}{k_1!k_2!k_3! \cdots k_p!} + \cdots + \frac{k_p(n-1)!}{k_1!k_2!k_3! \cdots k_p!} = \frac{(k_1+k_2+\cdots+k_p) (n-1)!}{k_1!k_2!k_3!\cdots k_p!} \\ & = \frac{n(n-1)!}{k_1!k_2!k_3! \cdots k_p!} = \frac{n!}{k_1!k_2!k_3! \cdots k_p!}

Sources

NEWLINE

NEWLINE
• Merris, Russell. http://media.wiley.com/product_data/excerpt/6X/04712629/047126296X.pdfCombinatorics. John Wiley & Sons. 2003 ISBN 978-0-471-26296-1

NEWLINE