Intereting Posts

prove : if $G$ is a finite group of order $n$ and $p$ is the smallest prime dividing $|G|$ then any subgroup of index $p$ is normal
Need help with this geometry problem on proving three points are collinear
Discrete to Continuous Representations of Functions via Laplace Transforms?
Are there arbitrarily large sets $S$ of natural integers such that the difference of each pair is their GCD?
Computing $\int_{0}^{\pi}\ln\left(1-2a\cos x+a^2\right) \, dx$
Every open cover of the real numbers has a countable subcover (Lindelöf's lemma)
A formal name for “smallest” and “largest” partition
Let $f,g$ be two distinct functions from $$ to $(0, +\infty)$ such that $\int_{0}^{1} g = \int_{0}^{1} f $.
Prove that $\int_{0}^{\infty}{1\over x^4+x^2+1}dx=\int_{0}^{\infty}{1\over x^8+x^4+1}dx$
Symmetric difference of cycles
The meaning of $\lambda$ in Lagrange Multipliers
Find the breaking time in IVP for classical Burgers equation
If each eigenvalueof $A$ is either $+1$ or $-1$ $ \Rightarrow$ $A$ is similar to ${A^{ – 1}}$
Minimal prime ideals of $\mathcal O_{X,x}$ correspond to irreducible components of $X$ containing $x$
Commutators in a group

Consider a non-empty set A containing n objects. How many relations on A are both symmetric and reflexive?

The answer to this is $2^p$ where $p=$ $n \choose 2$. However, I dont understand why this is so. Can anyone explain this?

- In combinatorics, how can one verify that one has counted correctly?
- Number of solutions of equation
- Combinations of 5 integers from 1 to 100 such that differences between the sorted integers of each combination is at least 5 but not more than 10?
- $2^{k} \mid {2k \choose 0} \cdot 3^{0} + {2k \choose 2} \cdot 3^{1} + \cdots + {2k \choose 2i} \cdot 3^{i} + \cdots + {2k \choose 2k} \cdot 3^{k}$
- Bubble sorting question
- Euler numbers grow $2\left(\frac{2}{ \pi }\right)^{2 n+1}$-times slower than the factorial?

- Maximization with xor operator
- How to find a linear extension of a poset
- Number of $(0,1)$ $m\times n$ matrices with no empty rows or columns
- Number of triangles in a regular polygon
- Combinatorics: Number of subsets with cardinality k with 1 element.
- Show me some pigeonhole problems
- Anti symmetrical relation
- Proving $\sum_{k=0}^{n}k{n\choose k}^2 = n{2n-1 \choose n-1} $
- combinatorial geometry: covering a square
- Prove that $A \times (B -C) = (A \times B) - (A \times C)$

To be reflexive, it must include all pairs $(a,a)$ with $a\in A$. To be symmetric, whenever it includes a pair $(a,b)$, it must include the pair $(b,a)$. So it amounts to choosing which $2$-element subsets from $A$ will correspond to associated pairs. If you pick a subset $\{a,b\}$ with two elements, it corresponds to adding both $(a,b)$ and $(b,a)$ to your relation.

How many $2$-element subsets does $A$ have? Since $A$ has $n$ elements, it has exactly $\binom{n}{2}$ subsets of size $2$.

So now you want to pick a collection of subsets of $2$-elements. There are $\binom{n}{2}$ of them, and you can either pick or not pick each of them. So you have $2^{\binom{n}{2}}$ ways of picking the pairs of distinct elements that will be related.

Being reflexive means that $(x,x)\in R$ for all $x\in A$. Being symmetric means that $(x,y)\in R$ implies that $(y,x)\in R$ as well.

Begin by listing $A$ as $A=\{a_1,\dots,a_n\}$. Then let $B$ be the set $$\{(a_i,a_j)\mid 1\le i<j\le n\}.$$ Note that if $x\ne y$ are elements of $A$, then either $(x,y)\in B$ or $(y,x)\in B$ but not both.

Let $S$ be any subset of $B$. Let $$R_S=S\cup\{(y,x)\mid (x,y)\in S\}\cup\{(x,x)\mid x\in A\}.$$ Then $R_S$ is a symmetric and reflexive relation on $A$.

Note that there are $2^{|B|}$ subsets of $B$, and that if $S\ne S'$ are subsets of $B$, then $R_S\ne R_{S'}$. Also, note that $|B|=\binom{n}2$. (If the last equality is not clear, note that $$B=\{(a_1,a_j)\mid j>1\}\cup\{(a_2,a_j)\mid j>2\}\cup\dots$$ so $|B|=(n-1)+(n-2)+\dots+1$, and it is well-known that the last sum equals $n(n-1)/2=\binom n2$.

This shows that the number of symmetric, reflexive relations on $A$ is at least $2^p$ with $p=\binom n2$.

To see the equality, it is enough to check that any such relation $R$ is $R_S$ for some $S\subseteq B$. But, given $R$, let $S=\{(a_i,a_j)\in R\mid i<j\}$. This is a subset of $B$, and it is easy to check that $R=R_S$.

Maybe you can see it like this: a relation $R$ on $A$ is a subset of $A\times A$, and it is symmetric if and only if $(x,y)\in R \implies (y,x)\in R$, moreover, if the relation is reflexive, then $(x,x)\in R$ for all $x\in A$. Then you can determine uniquely such a relation by saying which subsets of two distinct elements of $A$ “belong” to $R$, in the sense that $\{x,y\}\in R \iff (x,y),(y,x)\in R$. Now, you know that the number of subsets with two distinct elements of $A$ is $\binom{n}{2}$, and the number of subset of a set with $p$ elements is $2^p$.

I’m sorry if i was too obscure.

You can also think of it as a matrix of $nxn$, with the elements of the matrix being $(a_i,a_j)$ with $ a_i,a_j \in A$. The elements of the main diagonal have to be included in R because R is reflexive. For the remaining $n^2-n$, picking a pair from the upper triangle say $(a_2,a_1)$ implies that you are also picking $(a_1,a_2)$. So in reality you only have $\frac{n^2-n}{2}$ elements to pick from. This can be done in $2^{\frac{n^2-n}{2}}$ ways.

There is only one way to make the relation reflexive — all ordered pairs $(x,x), x\in A$ must be in the relation. So the number of reflexive symmetric relations on $A$ is the same as the number of ways of adding symmetric pairs $(a,b),(b,a)$, where $a\neq b$ into the relation.

Let $S$ be a subset of $2^A$ consisting of subsets of 2 elements. Then $S$ gives rise to exactly one reflexive symmetric relation on $A$. For example, if $A=\lbrace 1,2,3,4\rbrace$, then an example of $S$ is $\lbrace \lbrace 1,2\rbrace, \lbrace 1,4\rbrace, \lbrace 3,2\rbrace\rbrace$. The relation induced by $S$ is $$\lbrace (1,2), (2,1), (1,4), (4,1), (2,3), (3,2)\rbrace$$ plus all $(x,x), x\in A$.

Conversely, every reflexive symmetric relation on $A$ arises in this way.

Since there are $p={n\choose 2}$ subsets of 2 elements, there are $2^p$ such $S$’s. The answer to your question is therefore $2^p$.

For reflexive and symmetric relations on an n-element set, consider the set to be in the form of an n x n matrix. This matrix consists of a total of n^2 entries.

Now the main diagonal consists of n entries, while the non-diagonal entries consist of ((n^2)-n) entries.

Definitions:

Reflexive relation => (a,a) in R

Symmetric relation => If (a, b) in R, then (b, a) in R, and a can be equal to b

- Now for reflexive relations, based on the definition, this means that the main diagonal must all be present within our answer, and thus their value is set. If it were just reflexive (and not also symmetric), then we would go on to say that the non-diagonal entries can be either present or not (and the answer would be 2^((n^2)-n) relations because the non-diagonal entries have 2 possible values).
- However, since it also includes symmetric relations, the last step need not be done yet.
- Now, for symmetric relations on the set, this means that the non-diagonal entries can be split into two triangles divided by the main diagonal. It is of importance to note that we only need to include non-diagonal entries/2 because the lower-triangular entries are dependent on the upper or vice versa. If an upper-triangular entry is included, then by the definition of symmetric relations, the equivalent lower entry will be included as well. Thus, the lower triangular entries, like the main diagonal entries, are set to a fixed value.
- Therefore, the only entries to consider are half of the non-diagonal entries, which corresponds to ((n^2)-n)/2 entries with 2 possible values each, and thus has a final value of 2^((n^2)-n)/2 relations

- Action of a matrix on the exterior algebra
- If $ \lim_{n \to \infty} (2 x_{n + 1} – x_{n}) = x $, then is it true that $ \lim_{n \to \infty} x_{n} = x $?
- Separable implies second countable
- Is a stably free module always free?
- proof of $\sum\nolimits_{i = 1}^{n } {\prod\nolimits_{\substack{j = 1\\j \ne i}}^{n } {\frac{{x_i }}{{x_i – x_j }}} } = 1$
- All the ternary n-words with an even sum of digits and a zero.
- Can we have a matrix whose elements are other matrices as well as other things similar to sets?
- Problem on Linear Diophantine Equation over 3 variables
- Is there a name for the operation $f^{-1}(f(x) \oplus f(y))$?
- Probability of getting k different coupons in a set of S coupons, from an infinite set of N different types of coupons.
- Representation theory of locally compact groups
- How to compute $\sum\limits_{k=0}^n (-1)^k{2n-k\choose k}$?
- Evaluate $\displaystyle\lim_{j\to0}\lim_{k\to\infty}\frac{k^j}{j!\,e^k}$
- How to prove tr AB = tr BA?
- Sines and cosines of angles in arithmetic progression