There are n input ports and n output ports in an optical network switch (called a n x n switch). Time evolves in discrete steps, where each step is called a 'time-slot' (each time-slot is 1 microsecond). At the beginning of each time-slot, the following occurs: Data-units arrive to each of the n input ports. Each data-unit has a destination as one of the n output ports, with the destination being (discrete) uniformly randomly chosen from among the outputs, and independently of any other event.

Example: In a (5 x 5) switch, (input, output) pairs could be:{(1, 3), (2, 4), (3, 4), (4, 1), (5, 5)}

This means that the data-unit on input port 1 is destined to output port 3, data-unit on input-port 2 is destined to output port 4, data-unit on input-port 3 is destined to output port 4, and so on.

Acollisionoccurs in a time-slot if two data-units are destined to the same output port. For example, (2, 4) and (3, 4) in the example above are both destined to output port 4, and thus is a collision.

The system starts at time-slot = 0.Determine the expected number of time-slots to see the first collision.

answer choices:

n

(n+n^2)/2

1/n!

n^2-1

(n^3-2)/3

n^n/n!