Results 1 to 3 of 3

Math Help - Combinatorial argument

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    33

    Combinatorial argument

    I can prove these algebraically with no problems but I'm having trouble explaining with words why they are true i.e. with a combinatorial argument. Can someone give me a hint?

    C(n, k) = C(n-2, k-2) + 2C(n-2, k-1) + C(n-2, k)

    P(n, k) = P(n-1, k) + kP(n-1, k-1)

    Thank you.
    Last edited by VENI; March 14th 2009 at 09:15 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Feb 2009
    Posts
    33
    No one knows?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by VENI View Post
    I can prove these algebraically with no problems but I'm having trouble explaining with words why they are true i.e. with a combinatorial argument. Can someone give me a hint?

    C(n, k) = C(n-2, k-2) + 2C(n-2, k-1) + C(n-2, k)

    P(n, k) = P(n-1, k) + kP(n-1, k-1)

    Thank you.
    For C(n,k), consider breaking the k-subsets of 1, 2, ..., n into 4 sets:

    1. Those which include n-1 and n;
    2. those which include n-1 but not n;
    3. those which include n but not n-1; and
    4. those which include neither n-1 nor n.

    For P(n,k), consider breaking the k-permutations of 1, 2, ..., n into 2 sets:

    1. Those which do not include n; and
    2. those which do. In this case, consider the possible positions of n among the other k-1 integers.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorial proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 10th 2009, 12:20 PM
  2. Combinatorial argument and how many intersections?
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: December 4th 2009, 04:50 PM
  3. Combinatorial Argument
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 25th 2009, 02:49 PM
  4. combinatorial sum
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 12th 2009, 10:46 AM
  5. combinatorial argument
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 30th 2009, 01:03 PM

Search Tags


/mathhelpforum @mathhelpforum