Figuring out the correct number of permutations for a problem at work

[vaanwadilion]

I'm trying to figure out a problem at work.

Last year my company sent out 6 pieces of direct mail. A person could have received any combination of 1-6 (received only #1, received #2,5,6, #1-6, etc.). They also could have responded to only one of them, but obviously had to receive the one they responded to. For instance, they couldn't respond to #5 if they never received it. They can also receive each piece only once, so couldn't have received #1 more than once. They also could have received any number of direct mail pieces and not responded to any of them.

I'm now trying to figure out what I believe is the number of possible permutations considering this scenario. I believe the problem would involve this formula:

P(n,k)=n!/(n−k)!

To be honest, I'm not great at math, so I have no idea if that's the formula I need or not. Any help would be much appreciated. Thanks.

 

[micromass]

Hi vaanwadilion!

Admittedly, combinatorics is not my strong side. But let's see what we can do.

There are 7 possibilities, either a person receives no package, 1 package,..., 6 packages. The number of ways a person can receive k packages is $\binom{6}{k}$.

Now, if a person received k packages, then there are 2^k possibilities. Indeed every possibility corresponds to a subset of the k packages that he sends back. And there are 2_k such subsets.

So, the total number of combinations is

$$\sum_{k=0}^6{2^k\binom{6}{k}}=1+2*6+4*15+8*20+16*15+32*6+64$$

I hope that others will check this, as I easily make mistakes in these kinds of things...

 

[awkward]

Here's another way to approach the problem which yields the same result as micromass's solution and thereby establishes a combinatorial identity.

For each of the 6 packages, there are 3 possibilities:
(1) the person never receives it
(2) the person receives it but does not reply
(3) the person receives it and replies.

Therefore there are 3^6 = 729 possibilities.