What is the expected number of different sequences of bits in the collection that contains $2^{800}$ elements? Let $F$ denote a function that returns the first $800$ bits of the input.  

Let $G(N)$ denote a function that returns the last $800$ bits of the binary encoding of the given number $N$. For example,  

$$\begin{array}{l}
G(0) = 00\underbrace  \ldots _{{\rm{796\;zeroes}}}00,\\
G(1) = 00\underbrace  \ldots _{{\rm{796\;zeroes}}}01,\\
G({2^{800}} - 2) = 11\underbrace  \ldots _{{\rm{796\;ones}}}10,\\
G({2^{800}} - 1) = 11\underbrace  \ldots _{{\rm{796\;ones}}}11
\end{array}$$

etc (we are only interested in the interval $0 \le N \lt {2^{800}}$ ).  

Let $P$ denote Keccak permutation function that operates on $1600$-bit blocks.  

Choose (arbitrarily or randomly) any 800-bit sequence. Denote it by $S$. 

Consider the following collection (set) of bitsequences:  

$$\begin{array}{l}
{C} = \{ &amp;F(P(G(0)|| S)),\\&amp;F (P(G(1) || S)),\\&amp;F(P(G(2) || S)),\\&amp;\ldots ,\\&amp;F(P(G({2^{800}} - 2) || S)),\\&amp;F(P(G({2^{800}} - 1) || S))\;\;\} 
\end{array}$$

(it contains $2^{800}$ elements, and each element is a $800$-bit sequence).  

Let $Y$ denote the number of different (unique) elements in $C$.   

Question: what is the expected value of $Y$? And why?

Edit: I have read Expected number of different birthdays, and found the following formula:  

$$\begin{array}{l}\\&amp;
D = 2^{1600},\\&amp;
n = 2^{800},\\&amp;
\varphi = (D-1)/D,\\&amp;
Y = D\times (1-\varphi^n)
\end{array}$$  

Is this the correct formula for $Y$?
Every input $G(i) \mathbin\| S$ to $P$ is distinct.  If $P$ were a uniform random permutation, the random function $x \mapsto F(P(x))$ would have almost uniform distribution.  So the answer can't be much different from the number of distinct 800-bit strings in an independent uniform random sampling of $2^{800}$ of them, which is a fraction of $$1 - (1 - 1/2^{800})^{2^{800}} \approx 1 - e^{-1}$$ of them by the usual reason.  The fact that $S$ is chosen independently at random is not relevant to this analysis; the same analysis would apply if $S = 0$.