2
$\begingroup$

Given the number of combinations w/o repetition for a set of size n from which you choose k is given by:

n! / k! * (n - k)!

How does one calculate the number of these combinations that include a given element. That amount should be the same for all elements of the original set.

For example, given the set {A, B, C, D}, there are 6 different ways to pick 2 elements: AB, AC, AD, BC, BD, CD. However there are only 3 of these subsets with 'A' in it (AB, AC, AD). I am stumped on getting to this 3 beyond brute forcing it.

I assume I am missing some formula?

  • 0
    This question is for [Math at StackExchange](http://math.stackexchange.com/).2011-03-12

3 Answers 3

3

You must choose 1 element, then you can choose any k-1 elements from the remaining n-1. It's the same formula but with n and k replaced with n-1 and k-1 respectively.

(n-1)! / (k-1)! * ((n-1) - (k-1))! 
  • 0
    This is what I had $f$igured ahead of posting this - however I committed an algebraic brain fade when translating into code so the answer I was getting was not making sense. Thanks to all that responded!2011-03-12
0

Since you already have 1 element picked for you, you need to pick k-1 element from n-1 remaining, that gives the following formula:

(n-1)!/(k-1)!(n-k)! 
0

In the {A, B, C, D} example, picking A is already decided, to it reduces to picking the other one out of the three {B, C, D}, which is 3!/1!*(3-1)! = 3.