# Total no. of reflexive relations on a set of n elements

• December 27th 2011, 10:01 PM
nikhilbhr
Total no. of reflexive relations on a set of n elements
The number of reflexive relations on an n-element set is 2n2−n
Can anybody tell me why so?

• December 27th 2011, 10:52 PM
FernandoRevilla
Re: Total no. of reflexive relations on a set of n elements
Quote:

Originally Posted by nikhilbhr
The number of reflexive relations on an n-element set is 2n2−n Can anybody tell me why so?

Hint Every relation $R$ on $A=\{a_1,\ldots,a_n\}$ is an element of $\mathcal{P}( A\times A)$ . So, we have $\textrm{card}\;\mathcal{P}( A\times A)=2^{\;\textrm{card }\mathcal{P}( A\times A)}}=2^{n^2}$ relations on $A$ . Could you continue?
• December 28th 2011, 04:19 AM
Plato
Re: Total no. of reflexive relations on a set of n elements
Quote:

Originally Posted by nikhilbhr
The number of reflexive relations on an n-element set is $2^{n^2-n}$ Can anybody tell me why so?[/I]

Here is a different approach.
Any reflexive relation on a set of n elements must contain the diagonal. The diagonal has n elements.
So how many off-diagonal elements are there?
Now look at your answer, $2^{n^2-n}$.
How are they related?
• December 28th 2011, 04:27 AM
nikhilbhr
Re: Total no. of reflexive relations on a set of n elements
Quote:

Originally Posted by Plato
Here is a different approach.
Any reflexive relation on a set of n elements must contain the diagonal. The diagonal has n elements.
So how many off-diagonal elements are there?
Now look at your answer, $2^{n^2-n}$.
How are they related?

I understood your approach but can u tell me how you are correlating off-diagonal elements with reflexive relation.
• December 28th 2011, 04:43 AM
Plato
Re: Total no. of reflexive relations on a set of n elements
Quote:

Originally Posted by nikhilbhr
I understood your approach but can u tell me how you are correlating off-diagonal elements with reflexive relation.

How many subsets of off-diagonal elements are there?
• December 28th 2011, 06:35 PM
nikhilbhr
Re: Total no. of reflexive relations on a set of n elements
total elements in that matrix=nXn
total diagonal element=n
so obviously power set off-diagonal elements=2^(n^2-1).
But i have problem with the approach u are using .Can please how off-diagonal elements are correlated with reflexive relation..
Thanx for help.
• December 29th 2011, 01:03 AM
FernandoRevilla
Re: Total no. of reflexive relations on a set of n elements
Denote $\Delta$ the diagonal of $A\times A$ with $A=\{a_1,\ldots,a_n\}$ . Every reflexive relation $R$ on $A$ has the form $R=\Delta\cup B$ with $B\subset A\times A-\Delta$ . But $A\times A-\Delta$ has $n^2-n$ elements, so there are $2^{n^2-n}$ reflexive relations on $A$ .
• December 29th 2011, 02:24 AM
nikhilbhr
Re: Total no. of reflexive relations on a set of n elements
Thank u very much for your valuable help..Now i got where was the problem.Actually R= (set of diagonal element) U B ,i havent thought of this expression
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 19, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.7077123522758484, "perplexity": 700.2676678399097}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-48/segments/1448398456975.30/warc/CC-MAIN-20151124205416-00165-ip-10-71-132-137.ec2.internal.warc.gz"}