# Arrangements

Arrangements of n different elements are all possible orderings of these n elements. Arrangements differ only by order of elements.

Arrangement is particular case of permutation when k=n.

There are two forms of arrangements:

1. without repetitions - every element in the arrangement can occur only once (for example, arrangements without repetitions of n=3 elements a,b,c are following: abc,acb,bac,bca,cab,cba).
2. with repetitions - every element in the arrangement can occur more than once (for example, arrangements with repetitions of n=2 elements a,b where a occurs three times and b occurs two times are following: aaabb,aabab,aabba,abaab,ababa,abbaa,baaab,baaba,babaa,bbaaa).

Number of arrangements without repetitions is P_n=P_n^n=(n!)/((n-n)!) =n!.

Number of arrangements of n elements where k_1 elements are of first type, k_2 elments are of second type, ..., k_n elements are of n-th type is P(k_1,k_2,...,k_n)=((k_1+k_2+k_3+...+k_n)!)/(k_1!k_2!...k_n!), where k_1+k_2+...+k_n=n.

Example 1. Find number of different 4-digits numbers that can be formed from digits 0,1,2,3 if every digit can occur only once.

Note, that order is important here, because 1234 and 3214 are different numbers. Also, every digit can occur only once, i.e. number 2342 is not allowed. Therefore we use formula for arrangement without repetition: P_4=4! =4*3*2*1=24.

However, it is not correct answer, because there can occur numbers like 0231, which are not 4-digit numbers. Therefore we need to subtract number of arrangements where 0 is on first place. If we fix 0 on the first place then number of arrangements of other three digits is P_3=3! =6. Thus, there are 6 numbers that begin from 0: 0123,0132,0213,0231,0312,0321.

Therefore, number of 4-digit numbers is P_4-P_3=24-6=18.

Example 2. How many words can you make from 2 letters a and 1 letter b?

Let's first see what will be if we just arrange 2 letters a and 1 b:

1. aab (first letter a is on first place)
2. aab (second letter a is on first place)
3. aba (first letter a is on first place)
4. aba (second letter a is on first place)
5. baa (first letter a is on second place)
6. baa (second letter a is on second place)

See? We can't distinguish between 1 and 2; 3 and 4; 5 and 6. Though we use different a's but they are indistinguishable.

Therefore, we use formula for number of arrangements with repetitions: P(2,1)=((2+1)!)/(2!1!)=(3!)/(2!1!)=3 .

Example 3. How many ways are there to thread on string 4 green, 5 blue and 6 red beads?

Here we need to find arrangements with repetitions that can be formed from k_1=4 elements of first type (green beads; they are indistinguishable between each other), k_2=5 elements of second type (blue beads; they are also indistinguishable) and k_3=6 elements of the third type (red beads; they are indistinguishable as well): P(4;5;6)=((4+5+6)!)/(4!5!6!)=(15!)(4!5!6!)=630630.