Answer to Question #98204 in Statistics and Probability for C

Question

Hi,I’m struggling with counting principle in probability.Please explain it to me.All the rules of counting principles,why do we sometimes divide and sometimes multiply together and what does factorial mean?please help me understand each rule please?

Answer 1

Multiplication Rule

If one event can occur in $m$ ways, a second event in $n$ ways and a third event in $r,$ then the three events can occur in $m\times n\times r$ ways.

Repetition of an Event

If one event with $n$ outcomes occurs $r$ times with repetition allowed, then the number of ordered arrangements is $n^r.$

Arrangements or Permutations

Distinctly ordered sets are called arrangements or permutations (order matters, no repetition). 

The factorial is computed by the formula $n!=1\cdot 2 \cdot \dots \cdot n.$

The number of permutations of size $k$ that can be formed from the $n$ individuals or objects in a group will be denoted by $P_{n,k}.$

The number of permutations of $n$ objects taken $k$ at a time is given by:

$$P_{n,k}={n! \over (n-k)!}$$

Permutations with indistinguishable objects

If the $n$ objects are all distinguishable there are $n!$ permutations.

Dividing $n!$ by $n_1!$ gives the number of permutations of $n$ objects with $n_1$ of them being identical.

Repeating, to identify $n_2$ objects of type 2, …, $n_k$ objects of type $k,$ gives

$${n! \over n_1!n_2!...n_k!}$$

as the result.

Example

If we have $n$ elements of which $x$ are alike of one kind, $y$ are alike of another kind, $z$ are alike of another kind, then the number of ordered selections or permutations is given by:

$${n! \over x!y!z!}$$

An unordered subset is called a combination. One way to denote the number of combinations is

$C_{n,k}.$

Definition of combination without repetition

Let $a_1,a_2,...,a_n$ be $n$ objects. A simple combination (or combination without repetition) of $k$ objects from the $n$ objects is one of the possible ways to form a set containing $k$ of the $n$ objects.

To form a valid set, any object can be chosen only once. Furthermore, the order in which the objects are chosen does not matter.

$$C_{n,k}={P_{n,k} \over k!}={n! \over k!(n-k)!}=\binom{n}{k}$$

Definition of combination with repetition

The difference between a multiset and a set is the following: the same object is allowed to appear more than once in the list of members of a multiset, while the same object is allowed to appear only once in the list of members of an ordinary set.

Let $a_1,a_2,...,a_n$ be $n$ objects. A  combination with repetition of $k$ objects from the $n$ objects is one of the possible ways to form a multiset containing $k$ of the $n$ objects.

$$C'_{n,k}=C_{n+k-1,k}=\binom{n+k-1}{k}={(n+k-1)! \over k!(n+k-1-k)!}=$$ $$={(n+k-1)! \over k!(n-1)!}$$

Permutation with repetition (Use permutation formulas when order matters in the problem.

$$n^r$$

Where $n$ is the number of things to choose from, and you choose $r$ of them. 

Permutation without repetition

(Use permutation formulas when order matters in the problem.)

$$P_{n,k}={n! \over (n-k)!}$$

Where $n$ is the number of things to choose from, and you choose $k$ of them. 

Combination with repetition

(Use combination formulas when order doesn’t matter in the problem.)

$$C_{n+k-1,k}=\binom{n+k-1}{k}={(n+k-1)! \over k!(n-1)!}$$

Where $n$ is the number of things to choose from, and you choose $k$ of them. 

Combination without repetition

(Use combination formulas when order doesn’t matter in the problem.)

$$C_{n,k}={P_{n,k} \over k!}={n! \over k!(n-k)!}=\binom{n}{k}$$

Where $n$ is the number of things to choose from, and you choose $k$ of them.

Putting objects into boxes

There are

$${n! \over n_1!n_2!...n_k!}$$

ways to put $n$ distinguishable objects into $k$ boxes, so that the $i$th box contains $n_i$ objects.