<< . .

. 7
( : 20)



. . >>


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

<< . .

. 7
( : 20)



. . >>