in Set Theory & Algebra edited by
472 views
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!$

in Set Theory & Algebra edited by
472 views

3 Comments

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

0

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}.$
selected by

1 comment

how does number of inputs are n + 1  here
0

Related questions

Ask
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