Mathematics for Computer Science

15.13. A Magic Trick 491

1

3 7

5 4

2 6 65622

tree code

1 2 3 4 5 432

Figure 15.7

Problem 15.5.
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 ofY with 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,P.X/, and the setŒX! f0;1gçof
0-1-valued total functions onX.

(e)LetXWWDf1;2;:::;ng. In this problem we count how many bijections there
are fromXto itself. Consider the setBX;Xof allbijectionsfrom setXto setX.
Show a bijection fromBX;Xto the set of all permuations ofX(as defined in the
notes). Using that, countBX;X.