Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

migrated from stackoverflow.com Mar 12 '11 at 23:04

This question came from our site for professional and enthusiast programmers.

    
This question is for Math at StackExchange. –  darioo Mar 12 '11 at 8:13

3 Answers 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))!
share|improve this answer
    
This is what I had figured 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! –  episcopus Mar 12 '11 at 17:12

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)!
share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.