Mathematics for Computer Science

Chapter 14 Cardinality Rules624

Problem 14.68.
According to the Multinomial Theorem 14.6.5,.x 1 Cx 2 C


Cxk/ncan be
expressed as a sum of terms of the form

n

r 1 ;r 2 ;:::;rk

!

x 1 r^1 x 2 r^2 :::xkrk:

(a)How many terms are there in the sum?

(b)The sum of these multinomial coefficients has an easily expressed value:

X

r 1 Cr 2 C


CrkDn;

ri 2 N

n

r 1 ; r 2 ; :::; rk

!

Dkn (14.28)

Give a combinatorial proof of this identity.

Hint:How many terms are there when.x 1 Cx 2 C


Cxk/nis expressed as a sum
of monomials inxibeforeterms with like powers of these variables are collected
together under a single coefficient?

Problem 14.69.
You want to choose a team ofmpeople for your startup company from a pool ofn
applicants, and from thesempeople you want to choosekto be the team managers.
You took a Math for Computer Science subject, so you know you can do this in

n

m

!

m

k

!

ways. But your CFO, who went to Harvard Business School, comes up with the
formula
n
k

!

nk

mk

!

:

Before doing the reasonable thing—dump on your CFO or Harvard Business School—
you decide to check his answer against yours.

(a)Give acombinatorial proofthat your CFO’s formula agrees with yours.

(b)Verify this combinatorial proof by giving analgebraicproof of this same fact.