Number of finite-state machines with $n$ states, output alphabet size $a$, and binary input How many FSMs are there where the machine has $n$ states, reads a binary symbol at each time-step, and may or may not output a symbol from an alphabet of size $a$ after each transition?
 A: Without output
The state space has $n$ elements and the input space has $2$ elements. The state transition function maps the possible input-state pairs into the states. There are $2n$ such pairs. That is, we are talking about functions that map sets of $2n$ elements onto sets of $n$ elements. There are $$n^{2n}$$ such functions since any pair of input-state can be associated with any state.
With output
Assume that there is always an output. Then every state-input pair generates an output. Now, we have functions mapping sets of $2n$ elements onto sets of $a$ elements. There are $$a^{2n}$$ such functions. Together with the state transition functions we have $$n^{2n}a^{2n}$$ possibilities.
May or may not
I can interpret the "may or may not" clause in the following way. There are $a+1$ outputs, one of them is the "no output".
Appendix
Why do we have $2n$ possible pairs of inputs and states when we have $n$ states and $2$ inputs?
For $n=1$ we have $(0,1)$ and $(1,1)$, that is $2\times 1=2n$ possible pairs of inputs and states. Assume, that for all $k \le n$ we have $2k$ such elements of the range of the state transition function. Let's see how many pairs we have if the number of states is $n+1$. For the elements of the form $(i,k), k\le n, i=0,1$ we will have to add $(i,n+1), i=0,1$, that is two more pairs. $2n+2=2(n+1)$. By the principle of mathematical induction, it has been proved that for all $n$ the number of pairs is $2n$.
I hope that it it does not need any further argumentation that the number of possible state transition functions is $n^{2n}$.
Example
Let the set of states be $\{\spadesuit, \heartsuit,\diamondsuit, \clubsuit\}$ and let the set of inputs be $\{0,1\}$. The set of possible pairs of inputs and states is $$\{(0,\spadesuit),(0,\heartsuit),(0,\diamondsuit),(0,\clubsuit),(1,\spadesuit),(1,\heartsuit),(1,\diamondsuit),(1,\clubsuit)\}.$$
Every such pair may trigger $4$ new states. For example
$$(0,\spadesuit)\rightarrow\spadesuit, (0,\spadesuit)\rightarrow\heartsuit, (0,\spadesuit)\rightarrow\diamondsuit,(0,\spadesuit)\rightarrow\clubsuit.$$
As a total, we have $4^8=n^{2n}$ distinct state transition functions.
A: Imagine a transition table with $n$ rows, and columns with pairs (new-state, write) given read 0, (new-state, write) given read 1. 
There are $n^2a^2$ ways to make each row.  There are $n$ rows.  The total number of machines is thus $n^{n^{2}a^{2}}$. Add 1 to $a$ to account for an empty "no-write" character.
When I get enough reputation points I'll post an image of the transition table.
