# What is the expected number of of $k$-tuples of vertices such that all edges between the vertices have the same colour?

Consider the complete graph $K_n$ and suppose we colour each edge of $K_n$ red or blue with equal probability.

For every $k$, $1\leq k \leq n$, give a formula for the expected number of $k$-tuples $X$ of vertices such that all edges between the vertices of $X$ have the same colour.

I have some ideas so far. For $k=1$ we have $E(X)=n$ (the number of vertices) and for $k=2$ we have $E(X)=\begin{pmatrix}n\\2\end{pmatrix}$ (the number of edges). I also think that for $n=k$ we have $E(X)=2\times2^{-\begin{pmatrix}n\\2\end{pmatrix}}$.

However I'm unsure how to make a unified formula for a general $k$. Does such a formula exist?

We use the method of indicator random variables. I will assume, perhaps unreasonably, that a $k$-tuple of vertices is a set of $k$ vertices. The answer does not change if by $k$-tuple we mean a sequence of $k$ distinct vertices. But the answer below does not deal with ordered $k$-tuples of not necessarily distinct vertices.
There are $B=\binom{n}{k}$ such sets. List them as $S_1,S_2,\dots,S_B$. For $i=1$ to $B$, define random variable $X_i$ by $X_i=1$ if all the edges between vertices of $S_i$ have the same colour, and by $X_i=0$ otherwise.
Then the number $Y$ of monochromatic $k$-sets of vertices is given by $Y=X_1+\cdots +X_B$, and by the linearity of expectation we have $E(Y)=E(X_1)+\cdots +E(X_B)$.
For $k\ge 2$, the probability that a $k$-set is monochromatic is $\dfrac{2}{2^{\binom{k}{2}}}$. It follows that $E(Y)=\dfrac{2\binom{n}{k}}{2^{\binom{k}{2}}}$.