Construct a deterministic finite automation The question asks to:
construct a DFA which accepts exactly $\frac{n(n-1)(n-2)}{6} + \frac{n(n-1)}{2}+1$ many members of $\{0, 1\}^n$ for every n.
I have no idea where to start to constructing the DFA, could you give some directions?
By the way, how many states should this DFA have?
 A: HINT: Every $w\in\{0,1\}^n$ has $n$ symbols. There are $$\binom{n}3=\frac{n(n-1)(n-2)}6=\binom{n}3$$ ways to choose $3$ of those places to be $1$, leaving the rest $0$. $\dfrac{n(n-1)}2$ is also a binomial coefficient and can be interpreted similarly. Use these ideas to identify which $n$-symbol words to include in the language; once you have that, the DFA will be easy, and you won’t need very many states. I won’t say yet exactly how many, but it’s fewer than half a dozen.
A: First you might want to ask yourself how many members there are in $\{0, 1\}^n$. Since there are 2 elements in $\{0, 1\}$, clearly there are $2^n$ in total for each $n$. Turns out this doesn't get us anywhere in the problem, but when you have to do combinatorial reasoning it's always useful to think about how big the whole set is.
Now, you should consider the significance of $\frac{n(n - 1)(n - 2)}{6} + \frac{n(n - 1)}{2} + 1$. It might help to know some identities that are everywhere in computer science (typically learned along with analysis of algorithms). You should just internalize these:
$$ \dfrac{n(n - 1)}{2} = \sum_{i = 1}^n i = \binom{n}{2}$$
$$ \dfrac{n(n - 1)(n - 2)}{6} = \sum_{i = 1}^n i^2 = \binom{n}{3}$$
To construct your DFA, you should think about what those sums mean relative to elements of $\{0, 1\}^n$, what 1 means in this problem, and how you could accept the correct number of elements.
