# Number of n-variable symmetric boolean functions that are linear

How many symmetric boolean functions exist that are linear?
Let $$f$$ be a $$n$$-variable boolean function. $$f$$ is said to be symmetric if it is unchanged by any permutation of its variables, i.e. for 2-variable boolean functions $$f$$ is symmetric if $$f(a,b) = f(b,a)$$. In addition $$f$$ is called a linear function if it does not include second- or higher degree product terms in the ring sum normal form (RSNF). For example, a 2-variable function $$g(x_1, x_2)$$ is linear if the RSNF is of the form $$f(x_1, x_2) = c_0 \oplus c_1 x_1 \oplus c_2 x_2$$
I found the number of symmetric functions as $$2^{n+1}$$ and the number of linear functions as $$2^n$$ but I'm not sure if the number of linear functions is correct.
How do I get the number of symmetric functions that are also linear?

• @D.W. I am currently preparing for entrance examinations and encountered this question in a past exam. Commented Jan 8 at 6:35
• Thank you for the improved post!
– D.W.
Commented Jan 8 at 6:46

There are only 4 symmetric linear functions. You can easily show that you must have $$c_1=c_2$$ (otherwise $$f(1,0,0,\dots,0)$$ will be different from $$f(0,1,0,\dots,0)$$), and similarly, you must have $$c_1=c_2=\cdots=c_n$$. $$c_0$$ can be anything. Therefore, once you choose $$c_0$$ and $$c_1$$, the function is wholly determined.

There are $$2^{n+1}$$ linear functions, when your definition of linear functions allows a constant term $$c_0$$.

• What is the number of symmetric functions? I argued that because $f$ is symmetric it is only dependent on the number of its input variables. Because they can only take $n+1$ different values the number of symmetric boolean functions is therefore $2^{n+1}$. Commented Jan 8 at 7:05
• @M3n4p, that is best asked separately, using the 'Ask Question' button. I suggest counting the number of such functions with $n=4$ by hand, and comparing to your formula, to gain some partial insight. Hint: if you have such an $f$, and I tell you that I have an input in mind with two 1's and two 0's, but I don't tell you the particular input I have in mind, is the output fully determined?
– D.W.
Commented Jan 8 at 7:16
• I counted all the $n = 4$ functions and it fulfills $2^{n+1}$. I don't know how you would get more? Commented Jan 8 at 14:17
• @M3n4p, the comments here aren't intended for interactive discussion or for follow-up questions. I would suggesting using the 'Ask Question' button to ask how many symmetric functions there are. When you do that, show your work for how you got $2^{n+1}$ as the general formula, and how you got that number for $n=4$.
– D.W.
Commented Jan 8 at 17:19
• There are $2^{n+1}$ symmetric $n$-ary Boolean functions, this is stated in the Wikipedia entry "symmetric boolean function". Commented May 24 at 12:49