Results 1 to 3 of 3

Math Help - Sequence proof help

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    8

    Sequence proof help

    Hi,

    I'm having trouble with a math problem which involves proving that a particular recurrence is true for a function S(n,k). Having trouble getting started with this one - I think maybe I can use induction, but I'm not sure exactly how it would be applied to this problem.



    Thanks in advance for any help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2009
    Posts
    125
    Hi,

    let's look at S_{n,r}=S_{n-1,r-1}+rS_{n-1,r} (the other two are obvious).

    Let a set A have n elements. Pick one of them and denote it a. Then the following certainly holds:

    "number of ways to partition A into r nonempty subsets" = "number of ways to partition A into r nonempty subsets such that for each such partition the subset containing a contains only a" + "number of ways to partition A into r nonempty subsets such that for each such partition the subset containing a contains also another element distinct from a"

    First of these summands equals S_{n-1,r-1} because each partition occuring in the first summand is obtained by partitioning A\smallsetminus \{a\} into r-1 nonempty subsets and adding the singleton \{a\} to this partition.

    Each partition occuring in the second summand can be described like this: Partition the set A\smallsetminus \{a\} into r nonempty subsets and adjoin the element a to one of those subsets - there are r possibilities how to do so for each such partition of A\smallsetminus \{a\}. So the second summand equals rS_{n-1,r}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2009
    Posts
    8
    Thanks for your help Taluivren
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Sequence proof
    Posted in the Calculus Forum
    Replies: 2
    Last Post: May 10th 2010, 03:31 PM
  2. Sequence proof
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: October 6th 2009, 01:20 PM
  3. Sequence Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 28th 2009, 07:14 PM
  4. Sequence proof
    Posted in the Calculus Forum
    Replies: 3
    Last Post: February 5th 2008, 02:18 PM
  5. Sequence Proof
    Posted in the Calculus Forum
    Replies: 6
    Last Post: December 11th 2007, 02:19 PM

Search Tags


/mathhelpforum @mathhelpforum