maths.free › Combinatorics & Graph Theory › 8. Generating Functions › An Application of the Binomial Theorem

An Application of the Binomial Theorem

In this section, we see how can be used to derive another useful identity. We begin by establishing a different recursive formula for P(p,k) than was used in our definition of it.

An Application of the Binomial Theorem

In this section, we see how can be used to derive another useful identity. We begin by establishing a different recursive formula for \(P(p,k)\) than was used in our definition of it.

Our goal in this section will be to invoke with the exponent \(p=-1/2\). To do so in a meaningful manner, we need a simplified expression for \(C(-1/2,k)\), which the next lemma provides.

We will return to this generating function in , where it will play a role in a seemingly new counting problem that actually is a problem we've already studied in disguise.

Now recalling about the coefficients in the product of two generating functions, we are able to deduce the following corollary of by squaring the function \(f(x) = (1-4x)^{-1/2}\).

Symbols used here

\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
\infty
infinity
Not a number: "grows without bound" in limits and intervals.
P(A),\ P(A \mid B)
probability, conditional probability
Chance of A; chance of A given that B happened.
\leq,\ \geq
less/greater than or equal
Inequalities that allow equality; < and > exclude it.
\sup,\ \inf
supremum, infimum
Least upper bound, greatest lower bound.
n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\prod_{k=1}^{n} a_k
product
Multiply a_k for k = 1 up to n.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Өзүңүздүн аракетиңизди көрүңүз

Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Кээ бирлери Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion–exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs