# Count the functions that have an entry with a specific structure

Consider the function $f: \{0,1\}^n\rightarrow \{0,1\}^{2n}$

I want to count all the functions that have one entry where its first n bits are equal with the last n bits.

Assume we target entry number 10 and g is one of those functions that have the aforementioned property: $m=\{0,1\}^n;g(10)=m||m$

The total number of functions assuming $2^n$ rows where each row has $2n$ bits is $2^{{2^n}2n}$

I would say, if we want a specific entry of the function to have that structure we can first count the rest of the rows of the function which have: $(2^{n}-1)*2n$ bits and then since we want the first n bits to be equal with the last to the entry that we didn't take into account, we add another n bits, so total for each function: $(2^{n}-1)*2n+n$.

Total functions: $2^{(2^{n}-1)*2n+n}$

So the probability: $\frac{2^{(2^{n}-1)*2n+n}}{2^{2^n*2n}}=\frac{1}{2^n}$

Do i have it right? Is there an easier way to think about it? The result is to trivial to require that amount of effort.

One example (for $n=2$):

$F: \{0,1\}^2 \rightarrow \{0,1\}^{4}$ and I want to count all functions that have a specific entry, e.g 00, with a specific structure(first n bits equal with the last n bits). $F(00)=\{0000, 1010, 0101, 1111\}$ in this case

Entry 00| 0000

Entry 01| 0100

Entry 10| 0001

Entry 11| 0100

For example here $F(00)=0000$ and since $00=00$, this function should be counted

Entry 00| 0001

Entry 01| 0000

Entry 10| 0000

Entry 11| 0000

In this function since $F(00)=0001$ and $00\neq 01$, it should not be counted

• What do you mean by a row? A row in the value table of the function? Shouldn't you have $2^{2n}$ for $\{0,1\}^n \times \{0,1\}^n$ inputs? – Elias Apr 26 '17 at 15:30
• Visualizing the function as a table with $2^n$ rows where each row has $2n$ bits since the output of the function is $2n$ – Antonis Paragas Apr 26 '17 at 16:34
• But don't you need as many rows as you have possible inputs which is $2^{2n}$? – Elias Apr 26 '17 at 19:25
• Other issues, what on earth does "entry" mean? Input? Input coordinate? This is with respect to your example. – kodlu Apr 26 '17 at 21:39
• @Elias: Does the fact that has key change the total number of possible functions? I am not sure, I would say if we line up the functions, the key would just change their order. kodlu: with entry i mean the row inside the function, for example: f(10) is the 10th entry/row – Antonis Paragas Apr 27 '17 at 9:18

If you want the function to have the property for one input, say $x$, which is fixed ahead of time, you just focus on that output vector $$f(x)=f(x_1,\ldots,x_n)=(z_1,\ldots,z_{2n})$$ and the condition $z_i=z_{i+n}$ holds with probability
$$P(given ~row ~is ~good)=\frac{2^{n}}{2^{2n}}=2^{-n},$$ since in this case you don't care what is happening in the other rows.
$$P(given~ row ~is ~good) (1-P(given ~row ~is ~good))^{2^n-1}=2^{-n}[1-2^{-n}]^{2^{n}-1}$$ which can be estimated for large $n$ from above and below by using $$1-k\varepsilon+\frac{k(k-1)}{2}<[1-\varepsilon]^k<1-k\varepsilon$$ where $\varepsilon$ is small and positive.
• I have probably messed up the function definition, i am creating a new question about that. What i want is, assuming we have all the functions: $f(x)=(x_1,x_2,....,x_{2\cdot n})$. How many functions have $f(10)=(x_1,x_2,...,x_n, x_1, x_2, ..., x_n)$ – Antonis Paragas Apr 29 '17 at 9:10
• You need to improve your notation. You are mixing the general with the specific. Do you mean all functions $f:\{0,1\}^{2}\rightarrow \{0,1\}^{2n}$? If not why the $f(10)$ above is confusing since it would have $n=2.$ – kodlu Apr 29 '17 at 23:21
• @Antonis Paragas, Please show an example with $n=2$ in the question. Your $n=1$ example is consistent with my answer. – kodlu Apr 30 '17 at 21:48