# Cut The Knot!

An interactive column using Java applets
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, M. Petkovsek, H. S. Wilf, D. Zeilberger A K Peters, 1996, p. 24

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 {an}, where, by convention, index n ranges from 0 to , is a formal series

 f(x) = a0 + a1x + a2x2 + a3x3 + ...

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. [xn]f(x) is the common notation for the coefficient an by the term xn:

 [xn]f(x) = an.

Let [q: w1, w2, ..., wN] be a weighted voting system with n players, quota q and weights wi , i = 1, ..., N. The ith player's vote is weighted by the weight wi; 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 Bi , i = 1, 2, ..., N, denote the number of times the ith player is critical. Introduce B = B1 + ... + BN. Then the Banzhaf power index of the ith player is defined as BPIi = Bi/B.

Consider the polynomial

 B(x) = (1 + xw1)(1 + xw2)· ... ·(1 + xwN).

Quite obviously, [xn]B(x) is the number of ways to represent n as the sum of the elements of the sequence {wn}, or as the number of coalitions with the total weight equal to n. B(x) is therefore the generating function for the sequence {cn}, where cn is the number of coalitions with weight n. An analogous product B<i>(x) with (1 + xwi) omitted

 B(x) = B(x)/(1 + xwi)

"lists" all the coalitions that do not include the ith player. The number of times the ith player is critical is given by the sum

 (1) Bi = [xq-wi]B(x) + ... + [xq-1]B(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 SSi denote the number of times the ith 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

 SS1 + SS2 + ... + SSN = 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 + zxw1)(1 + zxw2)· ... ·(1 + zxwN).

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

 SS(x, z) = SS(x, z)/(1 + zxwi)

with the ith player omitted. We then have

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

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 + x2 + x3 + ... = 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 + x5 + x10 + x15 + ... = 1/(1 - x5),

The product

 P(x)N(x) = 1/[(1 - x)(1 - x5)] = 1 + x + x2 + x3 + x4 + 2x5 + 2x6 + 2x7 + 2x8 + 2x9 + 3x10 + 3x11 + ... ,

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 - x5)(1 - x10)(1 - x25)(1 - x50)].

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

 [x100]C(x) = C(6,4) + 45C(5,4) + 52C(4,4) + C(3,4) = 15 + 225 + 52 = 292  [x50]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". 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, 4th edition, Prentice Hall, 2001
6. H. S. Wilf, Generatingfunctionology, Academic Press, 2nd 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,000th visitor.

Copyright ® 1996-2003 Alexander Bogomolny