Generating functions have numerous applications in mathematics, especially in combinatorics, probability theory, statistics, the theory of Markov chains, and number theory.

Let [q: w₁, w₂, ..., w_N] be a weighted voting system with n players, quota q and weights w_i , i = 1, ..., N. The i^th player's vote is weighted by the weight w_i; the quota q is the number of points required to pass a decision. 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₁ + ... + B_N. Then the Banzhaf power index of the i^th player is defined as BPI_i = B_i/B.

Consider the polynomial

Quite obviously, [xⁿ]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 (1 + x^w_i) omitted

"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

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

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

[z^kxⁿ]SS(x, z) is the number of coalitions with weight n and length k. For each i, we shall also consider

with the i^th player omitted. We then have

(2)	SSi = k([zkxq-wi]SS<i>(x, z) + .. + [zkxq-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:

There is only one way to represent any amount as the sum of pennies which is expressed as the generating function:

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

The product

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

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

where C(n,m) is a poor man's notation for the binomial coefficient "n choose m". C(n,m) = 0, for n < 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.

References

1. R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
2. M. Petkovsek, H. S. Wilf, D. Zeilberger, A = B, A K Peters, 1996
3. G. Pólya, On Picture-Writing, Am Math Monthly 63 (1956), 689-697
4. P. Tannenbaum, Power in Weighted Voting Systems, The Mathematica Journal 7 issue 1 (1997), 58-63
5. P. Tannenbaum & R. Arnold, Excursions In Modern Mathematics, 4^th edition, Prentice Hall, 2001
6. H. S. Wilf, Generatingfunctionology, Academic Press, 2^nd edition, 1994

Alex Bogomolny has started and still maintains a popular Web site Interactive Mathematics Miscellany and Puzzles to which he brought more than 10 years of college instruction and, at least as much, programming experience. He holds M.S. degree in Mathematics from the Moscow State University and Ph.D. in Applied Mathematics from the Hebrew University of Jerusalem. In June 2003, his site has welcomed its 7,000,000^th visitor.

Copyright ® 1996-2003 Alexander Bogomolny