1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Discrete math problem: R.P. Grimaldi text

  1. Nov 19, 2009 #1
    1. The problem statement, all variables and given/known data

    Okay so I'm trying to teach myself the first three chapters if Grimaldi before I take a discrete math course in January. I'll probably be posting a few problems.

    The question is as follows:

    In how many ways can we select n objects from a collection of size 2n that consists of n distinct and n identical objects?

    I found an answer key on bit torrent but I still don't understand it. It says:

    "For each of the n distinct objects there are two choices. If an object is not selected, then one of the n identical objects is used in the selection. This results in 2^n possible selections of size n."

    Could someone please illustrate this a little better for me? It's driving me nuts that I can't understand what looks like an easy problem.

    2. Relevant equations

    Sigma(k=0,n)[ C(n,k) ] = 2^n

    Sigma(k=0,n)[ k ] = n(n+1)/2

    C(n,r)= n!/(r!*(n-r)!)

    3. The attempt at a solution

    Say we have n unique objects. We can change this selection by omitting
    one object and repeating a different one. eg. a--z, leave out 'a', but repeat 'z'.
    For one omission we get (n-1) different ways of doing this (b--z). For two omissions we get
    C(n-2,2) possibilities ... all the way up to n/2 when we run out of extra letters to double up on. This results in a sum of sorts, but not one that looks familiar.

    Thanks for reading!
  2. jcsd
  3. Nov 19, 2009 #2


    User Avatar
    Science Advisor
    Homework Helper

    Ok, here's n=3. {1,2,3,0,0,0}. 1, 2 and 3 are the 'unique' objects and the '0's are the 'identical'. How many ways to choose three? You can do it be choosing k unique objects and then filling out the choice with 3-k identical objects, and summing over k. That's C(3,3)+C(3,2)+C(3,1)+C(3,0). What they are saying is that each of those choices also corresponds to a specific subset of {1,2,3}, choose any subset and then full out the choice with the identical objects. There are 2^3 subsets. Therefore, C(3,3)+C(3,2)+C(3,1)+C(3,0)=2^3. That's what they are trying to prove.
  4. Nov 20, 2009 #3
    Makes sense now.
    Muchos Gracias, Richard!!
    Last edited: Nov 20, 2009
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook