Results 1 to 3 of 3

Math Help - Combinatorial Proof

  1. #1
    Junior Member
    Joined
    Feb 2008
    Posts
    51

    Combinatorial Proof

    Thanks in advance!
    Attached Thumbnails Attached Thumbnails Combinatorial Proof-1.jpg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Let A be a balanced subset of \{1,2,...,2n\}. Then the number of elements of A must be even. Furthermore, |A| can be either 2,4,6,...,2n. Assume we wish to find all balanced subsets with 2k elements, 1\leq k\leq n. To do this we need to choose k even integers, and and k odd integers. There are {n\choose k} ways to choose an even integer and {n\choose k} to choose odd integers. In total there are {n\choose k}^2 ways to create a balanced subset with 2k integers. This sum is taken over k=1,...,n. And thus, there are a total of \sum_{k=1}^n {n\choose k}^2 balanced subsets.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2008
    Posts
    51
    Thank you,
    Now a continuation of this question, I have came up with the formula
    bn = {2n\choose n}
    Prove combinatorially that this is true for all integers n>=1.

    I have this so far:
    1. Choose n integers from the 2n
    2. Choose all the even integers in that set
    3. Choose the odd that are not in that set

    How can I turn this into a more formal proof?

    Thanks again.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 10th 2011, 01:42 PM
  2. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 21st 2010, 02:47 AM
  3. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: June 4th 2010, 04:12 PM
  4. Combinatorial proof help
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 30th 2009, 05:43 PM
  5. Combinatorial proof?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 24th 2008, 06:20 PM

Search Tags


/mathhelpforum @mathhelpforum