edited by
981 views
4 votes
4 votes

A function $f:\left\{0, 1\right\}^{n}\rightarrow \left\{0, 1\right\}$ is called symmetric if for every $x_{1}, x_{2},....,x_{n} \in \left\{0, 1\right\}$ and every permutation $\sigma$ of $\left\{1, 2,...,n\right\}$, we have

$f\left(x_{1}, x_{2},...,x_{n}\right) = f \left(x_{\sigma(1)}, x_{\sigma(2)},....x_{\sigma(n)}\right)$.

The number of such symmetric function is:

  1. $2^{n+1}$
  2. $2^{n}$
  3. $2^{2n}/n!$
  4. $2^{2n}$
  5. $n!$

edited by

1 Answer

Best answer
5 votes
5 votes
First we need to find different number of inputs for $f$ given that permutations are equivalent.
 
Now given two binary string $x,y$: $x$ is a permutation of $y$ iff $x$ has same number of ones and zeros as $y$.
 
So the total number of different inputs is n+1 ( namely input with zero 0's, one 0's ... n 0's)
 
For each of these inputs we can have either 1 or 0 as output, so two choices.
 
Therefore, number of choices is $ \underbrace{2 \times 2 \times 2 \times \dots\times 2}_{n+1 \text{ times}} $.
 
So the total number of such symmetric functions is $2^{n + 1}.$
selected by

Related questions

1 votes
1 votes
2 answers
2
pC asked Jun 19, 2016
727 views
QuestionWhich of the following is NOT True ?Statement 1 : A-( B-C )=(A-B) - (A-C)Statement 2 : A$\bigtriangleup$(B$\cup$C)= (A $\bigtriangleup$B)$\cup$(A$\bigtriangleup$...