# Number of combinations w/o repetition that include a certain element

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?

-

## migrated from stackoverflow.comMar 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

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

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

-

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.

-