Results 1 to 8 of 8

Math Help - Total no. of reflexive relations on a set of n elements

  1. #1
    Newbie
    Joined
    Dec 2011
    Posts
    20

    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?

    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45

    Re: Total no. of reflexive relations on a set of n elements

    Quote Originally Posted by nikhilbhr View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1

    Re: Total no. of reflexive relations on a set of n elements

    Quote Originally Posted by nikhilbhr View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Dec 2011
    Posts
    20

    Re: Total no. of reflexive relations on a set of n elements

    Quote Originally Posted by Plato View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1

    Re: Total no. of reflexive relations on a set of n elements

    Quote Originally Posted by nikhilbhr View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Dec 2011
    Posts
    20

    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45

    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 .
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Dec 2011
    Posts
    20

    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Total relations between sets proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 15th 2011, 02:39 AM
  2. Relations, reflexive and transitive
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: October 5th 2010, 02:36 AM
  3. Total Differentiation; total mess.
    Posted in the Calculus Forum
    Replies: 4
    Last Post: May 13th 2010, 12:14 PM
  4. reflexive in relations
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 27th 2008, 03:41 PM
  5. Reflexive relations proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 14th 2007, 03:46 AM

/mathhelpforum @mathhelpforum