Mathematics for Computer Science

15.6. Sequences with Repetitions 461

But we know there arenŠpermutations of ann-element set, so by the Division
Rule, we conclude that

nŠDkŠ.nk/Š

n

k

!

which proves:

Rule 15.5.1(Subset Rule).The number ofk-element subsets of ann-element set is

n

k

!

D

nŠ

kŠ .nk/Š

:

Notice that this works even for 0-element subsets:nŠ=0ŠnŠD 1. Here we use the
fact that0Šis aproductof 0 terms, which by convention^2 equals 1.

15.5.2 Bit Sequences

How manyn-bit sequences contain exactlykones? We’ve already seen the straight-
forward bijection between subsets of ann-element set andn-bit sequences. For
example, here is a 3-element subset offx 1 ;x 2 ;:::;x 8 gand the associated 8-bit
sequence:
f x 1 ; x 4 ; x 5 g

. 1; 0; 0; 1; 1; 0; 0; 0 /

Notice that this sequence has exactly 3 ones, each corresponding to an element
of the 3-element subset. More generally, then-bit sequences corresponding to a
k-element subset will have exactlykones. So by the Bijection Rule,

Corollary.The number ofn-bit sequences with exactlykones is

n

k

!

15.6 Sequences with Repetitions

15.6.1 Sequences of Subsets

Choosing ak-element subset of ann-element set is the same as splitting the set
into a pair of subsets: the first subset of sizekand the second subset consisting of
the remainingnkelements. So the Subset Rule can be understood as a rule for
counting the number of such splits into pairs of subsets.

(^2) We don’t use it here, but asumof zero terms equals 0.