Cut The Knot!by Alex Bogomolny |
Generating Functions
July 2003
That was a proof by generating functions, another of the popular tools used by the species Homo sapiens for the proof of identities before the computer era. A = B, |
Generating functions have numerous applications in mathematics, especially, in combinatorics, probability theory, statistics, the theory of Markov chains and number theory.
By definition, an (ordinary) generating function of the sequence {a_{n}}, where, by convention, index n ranges from 0 to , is a formal series
f(x) = a_{0} + a_{1}x + a_{2}x^{2} + a_{3}x^{3} + ...
The generating function of a finite sequence is a polynomial in a single variable. The generating function of a double sequence is a series in two variables. Below we'll have examples of both kinds. [x^{n}]f(x) is the common notation for the coefficient a_{n} by the term x^{n}:
[x^{n}]f(x) = a_{n}.
Let [q: w_{1}, w_{2}, ..., w_{N}] be a weighted voting system with n players, quota q and weights w_{i} , I = 1, ..., N. The power of a player to affect the result of the voting process is not exactly determined by its weight (or the number of votes). For example, any system in which the quota equals the sum of all weights, requires a unanimous vote to pass a decision. Thus all players, regardless of their weights, have the same power. Power indices provide a mechanism to assess the latter. Following P. Tannenbaum, I am going to outline an application of generating functions for fast computations of two widely used power indices. (For historic remarks and evaluation of algorithmic complexity see J. M. Bilbao et al.)
The Banzhaf Power Index
Crucial to the definition of the Banzhaf power index is the concept of a coalition, which is just a nonempty set of players. A coalition of voters is called losing if the total weight of its members does not reach the quota. Otherwise, a coalition is called winning. A member is critical to a winning coalition if its removal renders the coalition losing. Let there be N vote holders (players, as they are usually called). Let B_{i} , I = 1, 2, ..., N, denote the number of times the I^{th} player is critical. Introduce B = B_{1} + ... + B_{N}. Then the Banzhaf power index of the I^{th} player is defined as
Consider the polynomial
B(x) = (1 + x^{w1})(1 + x^{w2})· ... ·(1 + x^{wN}).
Quite obviously, [x^{n}]B(x) is the number of ways to represent n as the sum of the elements of the sequence {w_{n}}, or as the number of coalitions with the total weight equal to n. B(x) is therefore the generating function for the sequence {c_{n}}, where c_{n} is the number of coalitions with weight n. An analogous product B^{<i>}(x) with
B^{<i>}(x) = B(x)/(1 + x^{wi})
"lists" all the coalitions that do not include the I^{th} player. The number of times the I^{th} player is critical is given by the sum
(1)
B_{i} = [x^{q-wi}]B^{<i>}(x) + ... + [x^{q-1}]B^{<i>}(x).
The Shapley-Shubik Power Index
Crucial to the definition of the Shapley-Shubik index is the concept of a sequential coalition, i.e., a permutation of players. The players are thought to be joining a sequential coalition one at a time, in the order defined by the permutation. Weights are accumulated with every player joining the coalition. The player, for whom the accumulation reaches or surpasses the quota for the first time, is called pivotal to the coalition. Let SS_{i} denote the number of times the I^{th} player is pivotal. Since a sequential coalition may have only one pivotal player, and each has at least one, provided the sum of all weights does not exceed the quota, we always have
SS_{1} + SS_{2} + ... + SS_{N} = N!.
The critical observation here is that if player P that occupies position k +1 in a permutation is pivotal to the corresponding sequential coalition, then it is in fact pivotal to k!(N-k-1)! sequential coalitions obtained from the latter by independently permuting the players preceding and those following P in the permutation.
Consider the function of two variables
SS(x, z) = (1 + zx^{w1})(1 + zx^{w2})· ... ·(1 + zx^{wN}).
[z^{k}x^{n}]SS(x, z) is the number of coalitions with weight n and length k. For each I, we shall also consider
SS^{<i>}(x, z) = SS(x, z)/(1 + zx^{wi})
with the I^{th} player omitted. We then have
(2)
SS_{i} = ∑_{k}([z^{k}x^{q-wi}]SS^{<i>}(x, z) + .. + [z^{k}x^{q-1}]SS^{< i >}(x, z))k!(N-k-1)!,
where k changes from 1 through N.
The applet below implements computations based on formulas (1) and (2). Several preset weighted system can be accessed via the dropdown box at the bottom of the applet. These can be modified and new ones can be created by adding new or deleting selected rows.
In how many ways can you change one dollar?
This was one of three questions answered by G. Pólya in a 1956 Monthly article. In absolutely the spirit of Pólya, the problem was also taken up in 1994 by Graham et al. Probably mindful of the soaring inflation, the authors put the question this way:
How many ways are there to pay 50 cents? We assume that the payment must be made with pennies (1), nickels (5), dimes (10), quarters (25), and half-dollars (50). George Pólya popularized this problem by showing that it can be solved with generating functions in an instructive way.
The problem has been also discussed by Kac and Ulam with an inspiring introduction:
Counting is such a primitive process, and we are first exposed to it at such an early age, that it may come as a surprise to learn that it is also a source of many problems of great interest, importance, and difficulty.
There is only one way to represent any amount as the sum of pennies which is expressed as the generating function:
P(x) = 1 + x + x^{2} + x^{3} + ... = 1/(1 - x),
where the first term stands for the only way to represent 0 pennies with no change at all.
If we are allowed to use only nickels, then the only amounts that can be changed are the multiples of 5, each of which can thus be changed in a single way. This is nicely represented by the generating function
N(x) = 1 + x^{5} + x^{10} + x^{15} + ... = 1/(1 - x^{5}),
The product
P(x)N(x) | = 1/[(1 - x)(1 - x^{5})] |
= 1 + x + x^{2} + x^{3} + x^{4} + 2x^{5} + 2x^{6} + 2x^{7} + 2x^{8} + 2x^{9} + 3x^{10} + 3x^{11} + ... , |
lists the number of ways in which various amounts could be changed with pennies and nickels. In general, the answer to Pólya's question (as well as to the deflated one) is determined as a coefficient of the generating function
C(x) = 1/[(1 - x)(1 - x^{5})(1 - x^{10})(1 - x^{25})(1 - x^{50})].
Making a clever use of the particular form of the function C, Graham et al (pp 344-346) express those coefficients in closed form, so that
[x^{100}]C(x) = C(6, 4) + 45C(5, 4) + 52C(4, 4) + C(3, 4) = 15 + 225 + 52 = 292
[x^{50}]C(x) = C(5, 4) + 45C(4, 4) + 52C(3, 4) + C(2, 4) = 5 + 45 = 50.
where C(n, m) is a poor man's notation for the binomial coefficient "n choose m".
The applet below allows one the choice of denominations from the standard set of 1, 5, 10, 25, 50, 100 augmented with the non-standard 2 and 20, to compound things somewhat. The applet also allows one to modify the maximum amount to be changed. You can check your solutions and test your patience by making this maximum sufficiently large.
(A very clear discussion of the dollar change problem can be also found in I. Niven's Mathematics of Choice, Ch. 7. A related problem has been posed by James Joseph Sylvester in 1884: for two coins, with coprime denominations p and q, what is the largest number that could not be expressed with p- and q-coins?)
References
- R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
- M. Kac and S. Ulam, Mathematics and Logic, Dover, 1992
- I. Niven, Mathematics of Choice: How to Count Without Counting, MAA 1965
- M. Petkovsek, H. S. Wilf, D. Zeilberger, A = B, A K Peters, 1996
- G. Pólya, On Picture-Writing, Am Math Monthly 63 (1956), 689-697
- P. Tannenbaum, Power in Weighted Voting Systems, The Mathematica Journal 7 issue 1 (1997), 58-63
- P. Tannenbaum & R. Arnold, Excursions In Modern Mathematics, 4^{th} edition, Prentice Hall, 2001
- H. S. Wilf, Generatingfunctionology, Academic Press, 2^{nd} edition, 1994 (Also available free online.)
Generating Functions
- Generating Functions
- A Property of the Powers of 2
- An USAMTS problem with light switches
- Examples with series of figurate numbers
- Euler's derivation of the binary representation
- Examples with finite sums with binomial coefficients
- Fast Power Indices and Coin Change
- Number of elements of various dimensions in a tesseract
- Straight Tromino on a Chessboard
- Ways To Count
- Probability Generating Functions
- Finite Sums of Terms 2^(n-i) i^2
- Sylvester's Problem, a Second Look
- Generating Functions from Recurrences
- Binet's Formula via Generating Functions
- Number of Trials to First Success
- Another Binomial Identity with Proofs
- Matching Socks in Dark Room
|Contact| |Front page| |Contents| |Algebra|
Copyright © 1966-2016 Alexander Bogomolny
68545722