3.14
 The number of communication patterns without contention in 4x4 cross-bar 
is 4! = 24. Patterns where the right side is the same for several left sides
(contention) are by construction impossible. 

  For 2-stage switch using 2x2 cross-bars the number of permutations
is the same (1:1 mapping), but some of them have contention.
  For example: 0-0, 1-2, 2-1, 3-3. 
  A communication pattern with contention appears when inputs from a
2x2 left switch are mapped to the outputs of the same 2x2 right switch.
There are 8 such possibilities, so the maximal number of 
communication patterns without contention is 24 - 8 = 16.

0-0, 1-1, 2-2, 3-3
          2-3, 3-2
     1-2, 2-1, 3-3 (contention)
          2-3, 3-1
     1-3, 2-1, 3-2 (contention)
          2-2, 3-1
0-1, ...

0-2, ...

0-3, ...

3.16
  Using different gray codings for each axe of the mesh, 
each node is getting a pair of coordinates.

   00 01 11 10
    |  |  |  |
0  -A--B--C--D-
    |  |  |  |
1  -E--F--G--H-
    |  |  |  |
A(0,00); B(0,01); C(0,11); D(0,10)

  So, two nodes connected by a line have one bit different -
mesh structure. (1)
  Also, for the hypercube, the gray code association is made such
that connected nodes have one bit difference in their coding. (2)
The number of nodes for the mesh is 2^i * 2^j = 2^d (3)
The number of verticex is 2^i * 2^j * 4 / 2 for the mesh and 2^d * d / 2 for
the hypercube. (4)

  From  (1) (2) (3) (optional-4) => a 2^i 2^j mesh can be imbedded in a 
d-dim cube with d >= i + j.

3.21
  The simplest network is a ring, so the number of switches is N / 4 =
2 ^ (d-2).