Question

the number of different nxn symmetric matrices with each element being either 0 or 1 is ______
a. 2^n
b. 2^(n^2)
c.2^((n^2+n)/2)
d.2^((n^2-n)/2)

Answer 1

We're only counting the lower (or upper) triangular part of the matrix, as shown on the drawing.

Thus, there are 1 + 2 + ... + n positions. Each position has two possible states, 0 or 1. If we have m positions, where each position can be in k states, then there are k^m permutations.

So, putting it all together, we get...?

Hint: Let S = 1 + 2 + ... + n.
S + (reverse S) = (1 + n) + (2 + [n - 1]) + ... + (n + 1) = (n + 1) + (n + 1) + ... + (n + 1) = n(n + 1). Therefore, 2 * S = n(n+1).