The same method can be carried out in general for ¬nding the ex-

pansion of (x1 + x2 + . . . + xr )n . From each factor we choose either an

x1 , or x2 , . . . , or xr , form the product and add these products for all

possible choices. We will have r n products, but many will be equal. A

particular choice of one term from each factor determines an r-cell par-

tition of the numbers from 1 to n. In the ¬rst cell we put the numbers

of the factors from which we choose an x1 , in the second cell those from

which we choose x2 , etc. A particular choice gives us a term of the form

xn1 xn2 . . . xnr with n1 + n2 + . . . + nr = n. The corresponding partition

1 2 r

has n1 elements in the ¬rst cell, n2 in the second, etc. For each such

partition we obtain one such term. Hence the number of these terms

which we obtain is the number of such partitions, which is

n n!

= .

n1 , n2 , . . . , n r n1 !n2 ! . . . nr !

64 CHAPTER 3. PARTITIONS AND COUNTING

Thus we have the multinomial theorem.

Multinomial theorem. The expansion of (x1 + x2 + . . . + xr )n is

found by adding all terms of the form

n

xn 1 xn 2 . . . x n r

n1 , n2 , . . . , n r 1 2 r

where n1 + n2 + . . . + nr = n.

Exercises

1. Expand by the binomial theorem

(a) (x + y)4 .

(b) (1 + x)5 .

(c) (x ’ y)3 .

(d) (2x + a)4 .

(e) (2x ’ 3y)3 .

(f) (100 ’ 1)5 .

2. Expand

(a) (x + y + x)4 .

(b) (2x + y ’ z)3 .

(c) (2 + 2 + 1)3 . (Evaluate two ways.)

3. (a) Find the coe¬cient of the term x2 y 3 z 2 in the expansion of

(x + y + z)7 .

[Ans. 210.]

(b) Find the coe¬cient of the term x6 y 3 z 2 in the expression (x’

2y + 5z)11

[Ans. -924,000.]

4. Using the binomial theorem prove that

(a)

n n n n

= 2n .

+ + +...+

0 1 2 n

65

3.6. BINOMIAL AND MULTINOMIAL THEOREMS

(b)

n n n n n

’ ’ +...±

+ =0

0 1 2 3 n

for n > 0.

5. Using an argument similar to the one in Section 3.6, prove that

n+1 n n n

= + + .

i ’ 1, j, k i, j ’ 1, k i, j, k ’ 1

i, j, k

6. Let f (n, r) be the number of terms in the multinomial expansion

of

(x1 + x2 + . . . + xr )n

and show that

n+r’1

f (n, r) = .

n

[Hint: Show that the conditions of Exercise 10 are satis¬ed by

showing that f (n, r ’ 1) is the number of terms which do not

have xr and f (n ’ 1, r) is the number which do.]

7. How many terms are there in each of the expansions:

(a) (x + y + z)6 ?

[Ans. 28.]

(b) (a + 2b + 5c + d)4 ?

[Ans. 35.]

(c) (r + s + t + u + v)6 ?

[Ans. 210.]

n

8. Prove that k n is the sum of the numbers for all choices

r1 ,r2 ,...,rk

of r1 , r2 , . . . , rk such that

r1 + r2 + . . . + rk = n.

Supplementary exercises.

66 CHAPTER 3. PARTITIONS AND COUNTING

9. Show that the problem given in Exercise 15b can also be solved

by a multinomial coe¬cient, and hence show that

n’k

n n r n

= = .

n ’ r, r ’ k, k r’k

r k k

10. Show that the problem given in Exercise 16 can also be solved by

a multinomial coe¬cient, and hence show that

n’s n’k

n n r k n

= = .

n ’ r, r ’ k, k ’ s, s k’s r’k

r k s s

11. If a + b + c = n, show that

n’a

n n

= .

a, b, c a b

12. If a + b + c + d = n, show that

n’a n’a’b

n n

= .

a, b, c, d a b c

13. If n1 + n2 + . . . + nr = n, guess a formula that relates the multino-

mial coe¬cient to a product of binomial coe¬cients. [Hint: Use

the formulas in Exercises 11 and 12 to guide you.]

14. Use Exercises 11, 12, and 13 to show that the multinomial co-

e¬cients can always be obtained by taking products of suitable

numbers in the ¬rst n rows of the Pascal triangle.

3.7 Voting power

We return to the problem raised in Section 2.6. Now we are interested

not only in coalitions, but also in the power of individual members. We

will develop a numerical measure of voting power that was suggested

by L. S. Shapley and M. Shubik. While the measure will be explained

in detail below, for the reasons for choosing this particular measure the

reader is referred to the original paper.

First of all we must realize that the number of votes a member

controls is not in itself a good measure of his or her power. If x has

three votes and y has one vote, it does not necessarily follow that x has

67

3.7. VOTING POWER

three times the power that y has. Thus if the committee has just three

members {x, y, z} and z also has only one vote, then x is a dictator and

y is powerless.

The basic idea of the power index is found in considering various

alignments of the committee members on a number of issues. The n

members are ordered x1 , x2 , . . . , xn according to how likely they are to

vote for the measure. If the measure is to carry, we must persuade x1

and x2 up to xi to vote for it until we have a winning coalition. If

{x1 , x2 , . . . , xi } is a winning coalition but {x1 , x2 , . . . , xi’1 } is not win-

ning, then xi is the crucial member of the coalition. We must persuade

him or her to vote for the measure, and he or she is the one hardest to

persuade of the i necessary members. We call xi the pivot.

For a purely mathematical measure of the power of a member we

do not consider the views of the members. Rather we consider all

possible ways that the members could be aligned on an issue, and see

how often a given member would be the pivot. That means considering

all permutations, and there will be n! of them. In each permutation

one member will be the pivot. The frequency with which a member is

the pivot of an alignment is a good measure of his or her voting power.

De¬nition. The voting power of a member of a committee is the

number of alignments in which he or she is pivotal divided by the total

number of alignments. (The total number of alignments, of course, is

n! for a committee of n members.)

Example 3.17 If all n members have one vote each, and it takes a

majority vote to carry a measure, it is easy to see (by symmetry) that

each member is pivot in 1/n of the alignments. Hence each member has

power equal to 1/n. Let us illustrate this for n = 3. There are 3! = 6

alignments. It takes two votes to carry a measure; hence the second

member is always the pivot. The alignments are: 123, 132, 213, 231,

312, 321. The pivots are emphasized. Each member is pivot twice,

hence has power 2 = 3 .

1

™¦

6

Example 3.18 Reconsider Example 2.9 of Section 2.6 from this point

of view. There are 24 permutations of the four members. We will list

them, with the pivot emphasized:

wxyz wxzy wyxz wyzx wzxy wzyx

xwyz xwzy xywz xyzw xzwy xzyw

yxwz yxzw ywxz ywzx yzxw yzwx

zxyw zxwy zyxw zywx zwxy zwyx

68 CHAPTER 3. PARTITIONS AND COUNTING

14 6 2

We see that z has power of 24 , w has 24 , x and y have 24 each. (Or,

7 3 1 1

simpli¬ed, they have 12 , 12 , 12 , 12 power, respectively.) We note that

these ratios are much further apart than the ratio of votes which is

3 : 2 : 1 : 1. Here three votes are worth seven times as much as the

™¦

single vote and more than twice as much as two votes.

Example 3.19 Reconsider Example 2.10 of Section 2.6. By an analy-

sis similar to the ones used so far it can be shown that in the Security

Council of the United Nations before 1966, each of the Big Five had

76

or approximately .197 power, while each of the small nations had

385

approximately .002 power. (See Exercise 12.) This reproduces our in-

tuitive feeling that, while the small nations in the Security Council are

not powerless, nearly all the power is in the hands of the Big Five.

The voting powers according to the 1966 revision will be worked

™¦

out in Exercise 13.

Example 3.20 In a committee of ¬ve each member has one vote, but

the chair has veto power. Hence the minimal winning coalitions are

three-member coalitions including the chair. There are 5! = 120 per-

mutations. The pivot cannot come before the chair, since without the

chair we do not have a winning coalition. Hence, when the chair is in

3

place number 3, 4, or 5, he or she is the pivot. This happens in 5 of the

permutations. When he or she is in position 1 or 2, then the number 3

member is pivot. The number of permutations in which the chair is in

one of the ¬rst two posltions and a given member is third is 2 · 3! = 12.

3 1

Hence the chair has power 5 , and each of the others has power 10 . ™¦

Exercises

1. A committee of three makes decisions by majority vote. Write

out all permutations, and calculate the voting powers if the three

members have

(a) One vote each.

111

[Ans. , , .]

333

(b) One vote for two of them, two votes for the third.

112

[Ans. , , .]

663

(c) One vote for two of them, three votes for the third.

69

3.7. VOTING POWER

[Ans. 0, 0, 1.]

(d) One, two, and three votes, respectively.

112

[Ans. , , .]

663

(e) Two votes each for two of them, and three votes for the

third.

111

[Ans. , , .]

333

2. Prove that in any decision-making body the sum of the powers of

the members is 1.

3. What is the power of a dictator? What is the power of a “pow-

erless” member? Prove that your answers are correct.

4. A large company issued 100,000 shares. These are held by three

stockholders, who have 50,000, 49,999, and one share, respec-

tively. Calculate the powers of the three members.

211

[Ans. , , .]

366

5. A committee consists of 100 members having one vote each, plus

a chairman who can break ties. Calculate the power distribution.

(Do not try to write out all permutations!)

6. In Exercise 5, give the chairman a veto instead of the power to

break ties. How does this change the power distribution?

50

[Ans. The chairman has power .]

101

7. How are the powers in Exercise 1 changed if the committee re-

3

quires a 4 vote to carry a measure?

8. If in a committee of ¬ve, requiring majority decisions, each mem-

1

ber has one vote, then each has power 5 . Now let us suppose that

two members team up, and always vote the same way. Does this

increase their power? (The best way to represent this situation is

by allowing only those permutations in which these two members

are next to each other.)

[Ans. Yes, the pair™s power increases from .4 to .5.]

70 CHAPTER 3. PARTITIONS AND COUNTING

9. If the minimal winning coalitions are known, show that the power

of each member can be determined without knowing anything

about the number of votes that each member controls.

10. Answer the following questions for a three-man committee.

(a) Find all possible sets of minimal winning coalitions.

(b) For each set of minimal winning coalitions ¬nd the distribu-

tion of voting power.

(c) Verify that the various distributions of power found in Ex-

ercises 1 and 7 are the only ones possible.

11. In Exercise 1 parts 1a and 1e have the same answer, and parts 1b

and 1d and Exercise 4 also have the same answer. Use the results

of Exercise 9 to ¬nd a reason for these coincidences.

12. Compute the voting power of one of the Big Five in the Security

Council of the United Nations as follows:

(a) Show that for the nation to be pivotal it must be in the

number 7 spot or later.

(b) Show that there are 6 6!4! permutations in which the nation

2

is pivotal in the number 7 spot.

(c) Find similar formulas for the number of permutations in

which it is pivotal in the number 8, 9, 10, or 11 spot.

(d) Use this information to ¬nd the total number of permuta-

tions in which it is pivotal, and from this compute the power

of the nation.

13. Apply the method of Exercise 12 to the revised voting scheme

in the Security Council (10 small-nation members, and 9 votes

required to carry a measure). What is the power of a large nation?

Has the power of one of the small nations increased or decreased?

421

[Ans. (nearly the same as before); decreased.]

2145

3.8 Techniques for counting

We know that there is no single method or formula for solving all count-

ing problems. There are, however, some useful techniques that can be

71

3.8. TECHNIQUES FOR COUNTING

learned. In this section we shall discuss two problems that illustrate

important techniques.

The ¬rst problem illustrates the importance of looking for a general

pattern in the examination of special cases. We have seen in Section

3.2 and Exercise 6 of that section, that the following formulas hold for

the number of elements in the union of two and three sets, respectively.

n(A1 ∪ A2 ) = n(A1 ) + n(A2 ) ’ n(A1 © A2 ),

n(A1 ∪ A2 ∪ A3 ) = n(A1 ) + n(A2 ) + n(A3 )

’n(A1 © A2 ) ’ n(A1 © A3 ) ’ n(A2 © A3 )

+n(A1 © A2 © A3 ).

On the basis of these formulas we might conjecture that the number of

elements in the union of any ¬nite number of sets could be obtained by

adding the numbers in each of the sets, then subtracting the numbers in

each possible intersection of two sets, then adding the numbers in each

possible intersection of three sets, etc. If this is correct, the formula for

the intersection of four sets should be

n(A1 ∪ A2 ∪ A3 ∪ A4 ) = n(A1 ) + n(A2 ) + n(A3 ) + n(A4 ) (3.1)

’ n(A1 © A2 ) ’ n(A1 © A3 ) ’ n(A1 © A4 )

’ n(A2 © A3 ) ’ n(A2 © A4 ) ’ n(A3 © A4 )

+ n(A1 © A2 © A3 ) + n(A1 © A2 © A4 )

+ n(A1 © A3 © A4 ) + n(A2 © A3 © A4 )

’ n(A1 © A2 © A3 © A4 )

Let us try to establish this formula. We must show that if u is an

element of at least one of the four sets, then it is counted exactly once

on the right-hand side of 3.1. We consider separately the cases where

u is in exactly 1 of the sets, exactly 2 of the sets, etc.

For instance, if u is in exactly two of the sets it will be counted twice

in the terms of the right-hand side of 3.1 that involve single sets, once

in the terms that involve the intersection of two sets, and not at all in

the terms that involve the intersections of three or four sets. Again, if

u is in exactly three of the sets it will be counted three times in the

terms involving single sets, twice in the terms involving intersections

of two sets, once in the terms involving the intersections of three sets,

and not at all in the last term involving the intersection of all four sets.

Considering each possibility we have the following table.

72 CHAPTER 3. PARTITIONS AND COUNTING

Number of sets that contain u Number of times it is counted

1 1

2’1

2