計算具有特定結構的條目的函式
考慮函式 $ f: {0,1}^n\rightarrow {0,1}^{2n} $
我想計算所有具有一個條目的函式，其中它的前 n 位與最後 n 位相等。
假設我們以條目號 10 為目標，並且 g 是具有上述屬性的函式之一： $ m={0,1}^n;g(10)=m||m $
假設的函式總數 $ 2^n $ 每行都有的行 $ 2n $ 位是 $ 2^{{2^n}2n} $
我想說，如果我們希望函式的特定條目具有該結構，我們可以首先計算函式的其餘行具有： $ (2^{n}-1)*2n $ 位，然後因為我們希望前 n 位與最後一個與我們沒有考慮的條目相等，所以我們再添加 n 位，因此每個函式的總計： $ (2^{n}-1)*2n+n $ .
總功能： $ 2^{(2^{n}-1)*2n+n} $
所以機率： $ \frac{2^{(2^{n}-1)2n+n}}{2^{2^n2n}}=\frac{1}{2^n} $
我做對了嗎？有沒有更簡單的思考方式？結果是微不足道的需要這麼多的努力。
編輯（添加了更多細節）：
一個例子（對於 $ n=2 $ ):
$ F: {0,1}^2 \rightarrow {0,1}^{4} $ 我想計算所有具有特定條目的函式，例如 00，具有特定結構（前 n 位等於最後 n 位）。 $ F(00)={0000, 1010, 0101, 1111} $ 在這種情況下
條目 00| 0000
條目 01| 0100
條目 10| 0001
條目 11| 0100
例如這裡 $ F(00)=0000 $ 並且因為 $ 00=00 $ , 這個函式應該算
條目 00| 0001
條目 01| 0000
條目 10| 0000
條目 11| 0000
在這個函式中 $ F(00)=0001 $ 和 $ 00\neq 01 $ , 不應計入
如果您希望該函式具有一個輸入的屬性，請說 $ x $ ，這是提前固定的，你只需關注那個輸出向量
$$ f(x)=f(x_1,\ldots,x_n)=(z_1,\ldots,z_{2n}) $$ 和條件 $ z_i=z_{i+n} $ 有機率成立 $$ P(given ~row ~is ~good)=\frac{2^{n}}{2^{2n}}=2^{-n}, $$ 因為在這種情況下，您不在乎其他行發生了什麼。 如果您希望此屬性僅適用於您選擇的輸入，這很有可能發生
$$ P(given~ row ~is ~good) (1-P(given ~row ~is ~good))^{2^n-1}=2^{-n}[1-2^{-n}]^{2^{n}-1} $$ 這可以估計為大 $ n $ 從上面和下面使用 $$ 1-k\varepsilon+\frac{k(k-1)}{2}<[1-\varepsilon]^k<1-k\varepsilon $$ 在哪裡 $ \varepsilon $ 是小而積極的。