+4 votes
272 views

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!$ asked
edited | 272 views
0
ANYBODY CLEAR ME THE 3RD LINE OF THE QUESTION....THE EQUALITY PART
0
@ arjun sir i m unable to cache the third line of the question...the equality part ..give an example
0

I think that means f(Xsigma1) can take either 0 or 1 value

Similarly others too

## 1 Answer

+5 votes
Best answer
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}.$
answered by Active (2.5k points)
selected
0
how does number of inputs are n + 1  here

+1 vote
2 answers
2
0 votes
1 answer
3
+2 votes
2 answers
4
0 votes
2 answers
5
+2 votes
2 answers
6