How many symmetric functions are possible?

Question

what should be the approach followed to solve this question ?

Answer 1

Let's begin with the input. Every input is an $n$-tuple of bits. If there is a permutation of the entries sending one $n$-tuple to another, then they clearly must have the same number of 1s, since the 1s just get moved around. But if two $n$-tuples have the same number of 1s, then we can obviously rearrange the entries from one to get the other (formally, let order the positions with 0s and the positions with 1s in each tuple and then use this to pair them up and find a permutation that works).

Thus since the function has the same value at all tuples with a permutation between them, it has the same value at all tuples with the same number of 1s. Additionally since all tuples with permutations between them have the same number of 1s, any choice of values for each number of 1s determines a valid function.

Then we can have between $0$ and $n$ 1s in a tuple, and for each number of 1s, we have 2 possibilities for the value of the function.

This gives $2^{n+1}$ possible such functions.