The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
222 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 in Set Theory & Algebra by Loyal (6.8k points)
edited by | 222 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 by
0
how does number of inputs are n + 1  here

Related questions

+1 vote
1 answer
1
asked Dec 16, 2016 in Set Theory & Algebra by vaishali jhalani Loyal (5.8k points) | 245 views
+1 vote
2 answers
2


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,774 questions
41,739 answers
118,909 comments
41,386 users