Mathematics for Computer Science

Chapter 14 Cardinality Rules594

1

3 7

5 4

2 6 65622

tree code

1 2 3 4 5 432

Figure 14.7

(a)Describe a procedure for reconstructing a numbered tree from its code.

(b)Conclude there is a bijection between then-vertex numbered trees andf1;:::;ngn^2 ,
and state how manyn-vertex numbered trees there are.

Problem 14.9.
LetXandYbe finite sets.

(a)How many binary relations fromXtoYare there?

(b)Define a bijection between the setŒX!Yçof all total functions fromXto
Y and the setYjXj. (RecallYnis the Cartesian product ofYwith itselfntimes.)
Based on that, what isjŒX!Yçj?

(c)Using the previous part, how manyfunctions, not necessarily total, are there
fromXtoY? How does the fraction of functions vs. total functions grow as the
size ofXgrows? Is itO.1/,O.jXj/,O.2jXj/,...?

(d)Show a bijection between the powerset, pow.X/, and the setŒX! f0;1gçof
0-1-valued total functions onX.

(e)LetXbe a set of sizenandBXbe the set of all bijections fromX toX.