Discrete math problem: R.P. Grimaldi text

[hallwayantics]

Homework Statement

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.

Homework 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)!)

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!

 

[Dick]

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.

 

[hallwayantics]

Makes sense now.
Muchos Gracias, Richard!