# Permutations & Combinations

As you may have already noticed, finding patterns in the possible ways events can occur is very useful in helping us count the number of desirable events in our sample space. Two of the easiest methods for doing this are with *permutations* (when order matters) and *combinations* (when order doesn't matter). 

### Permutations

An ordered arrangement of $$r$$ objects from a set, $$A$$, of $$n$$ objects (where $$0\<r\leq n$$) is called an $$r$$*-element permutation* of $$A$$. You can also think of this as a permutation of $$A$$'s elements taken $$r$$ at a time. The number of $$r$$*-element permutations* of an $$n$$-object set is denoted by the following formula:\
\
$$\_nP\_r =\frac{n!}{(n-r)!}$$

**Note:** We define $$0!$$ to be $$1$$; otherwise, $$\_nP\_n$$ would be $$\frac{n!}{0}$$ (when $$r=n$$).&#x20;

permutations = 3 \* 2 \* 1 = 3! = 6

-> written as n! $$numpy.math.factorial(n)$$

**- of a subset**

k-permutations = 8 \* 7 \* 6 = 3366

> select *k* elements out of a pool of *n* objects

​$$n \* (n-1) \* ... \* (n - k + 1)\newline P\_k^n=\frac{n!}{(n-k)!}$$

```python
from numpy.math import factorial as fact

def permutation(n, k):
    return fact(n) / fact(n-k)
```

**- with replacement**

Now the number of possible outcomes is 3 \* 3 \* 3.

Generalizing this to *n*, this means that the number of permutations with replacenent when having *n* distinct objects is equal to *n^j* where *j* is the number of “draws”.

### Combinations

An unordered arrangement of $$r$$ objects from a set, $$A$$, of $$n$$ objects (where $$r \leq n$$) is called an $$r$$*-element combination* of $$A$$. You can also think of this as a combination of $$A$$'s elements taken $$r$$ at a time.&#x20;

Because the only difference between permutations and combinations is that combinations are unordered, we can easily find the number of $$r$$-element combinations by dividing out the permutations ($$r!$$):\
\
$$\_nC\_r=\frac{\_nP\_r}{r!}=\frac{n!}{r! \* (n-r)!}$$

When we talk about combinations, we're talking about the number of subsets of size $$r$$ that can be made from a set of size $$n$$. In fact, $$\_nC\_r$$ is often referred to as "$$n$$ choose $$r$$", because it's counting the number of $$r$$-element combinations that can be chosen from a set of $$n$$ elements. In notation, $$\_nC\_R$$ is typically written as $$\binom{n}{r}$$.&#x20;

In general, combinations answer the question: "How many ways can we create a subset *k* out of *n* objects?". The subset is not ordered.

$$\binom{n}{k}=\frac{P\_k^n}{k!} = \frac{\frac{n!}{(n-k)!}}{k!} = \frac{n!}{(n-k)!k!}$$

```python
def combination(n, k):
  return fact(n) / (fact(n-k)*fact(k))
```

### [Bernoulli Distribution](https://www.hackerrank.com/challenges/s10-binomial-distribution-1/tutorial)

We define a binomial process to be a binomial experiment meeting the following conditions:

* The number of successes is *k*.
* The total number of trials is *n*.
* The probability of success of 1 trial is *p*.
* The probability of failure of 1 trial *q*, where *q = 1 - p*.
* *b(n, k, p)* is the binomial probability, meaning the probability of having exactly successes out of *n* trials.

The binomial random variable is the number of successes, *k*, out of *n* trials.

The binomial distribution is the probability distribution for the binomial random variable, given by the following probability mass function:

$$b(n, k, p) = \binom nk \* p^k \* q^{(n-k)}$$

```python
def bernoulli(n, k, p):
    return combination(n, k) * p**k * (1-p)**(n-k)
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://stephanosterburg.gitbook.io/scrapbook/math/hackerrank/permutations-and-combinations.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.