Results 1 to 4 of 4

Math Help - Equivalence Relations

  1. #1
    Newbie Chief65's Avatar
    Joined
    Sep 2008
    From
    Denver
    Posts
    18

    Equivalence Relations

    Let B(n) be the n-th Bell number (the number of equivalence relations on an n-element set). Show that the Bell numbers satisfy:
    B(0) = 1;
    B(n+1) = Sum_{k=0 }^n C(n,k)B(k).
    (Hint: count equivalence relations on {0,1,...,n} by first choosing which elements are NOT related to n.) I am not quite sure how to start. i was thinking induction, but got lost? any help would be great
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Here is a pdf file that I did sometime ago.
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie Chief65's Avatar
    Joined
    Sep 2008
    From
    Denver
    Posts
    18
    the pdf does not show that B(0)=1, it just says "for convenient notation."
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by Chief65 View Post
    the pdf does not show that B(0)=1, it just says "for convenient notation."
    Well of course not! By definition the empty set cannot be partitioned.
    But for convenience of notation we use it in the sums.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 19th 2011, 01:09 PM
  2. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: April 29th 2010, 04:30 PM
  3. Replies: 10
    Last Post: January 14th 2010, 12:28 PM
  4. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 14
    Last Post: October 1st 2009, 03:03 PM
  5. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 16th 2008, 01:08 PM

Search Tags


/mathhelpforum @mathhelpforum