Basic Counting Techniques

In general, counting is the process of determining the number of elements of a finite set of objects. In mathematics, the set of integer numbers {1, 2, 3, ⋯, 𝑛} is used to keep track of the progress of counting.

Counting Principle

The strategies used to count something involve two different approaches, the addition principle and the multiple principle.

The Addition Principle

The addition principle is used to accumulate all possible choices to select a element from all available sets of elements. For example, given two disjoint, or mutually exclusive groups with m elements in group I and n elements in group II, then the possible number of choices to select one element from group I or group II is m+n.

The Multiplication Principle

The multiplication principle, also called fundamental counting principle, is used to compute the possible ways to complete a task involving a number of steps of which the ways to complete are independent of each other. For example, a task involves two steps with m independent ways to complete the first step and n independent ways to completer the second step, then the most possible ways to complete the task is m*n.

Factorial

Factorial notation, '!' is a compact representation for the multiplication of consecutive integers. e.g 𝑛!=𝑛(𝑛−1)(𝑛−2)⋯(2)(1), where n is a positive integer. Definiton (Factorial notation) 0!=1a special case 1!=(1)=1 2!=(2)(1)=2 3!=(3)(2)(1)=6 ⋮ (𝑛−2)!=(𝑛−2)(𝑛−3)⋯(2)(1)=(𝑛−2)(𝑛−3)! (𝑛−1)!=(𝑛−1)(𝑛−2)⋯(2)(1)=(𝑛−1)(𝑛−2)! 𝑛!=𝑛(𝑛−1)(𝑛−2)⋯(2)(1)=𝑛(𝑛−1)!

Arrangement Processes

The ways to arrange of element can be classified to two cataloges, permutation and combination.

Permutation

For a given set of elements, a permutation is a linear arrangement of elements of which the order of arranged elements must be taken into account

Permutation Example

For example, The ways to arrange 𝑛 elements in 𝑛 ordered positions: Elements are arranged one after one in the 𝑛 ordered positions All steps to complete the task are independent of each other.The number of available elements will be reduced by one after every step. Therefore the ways to arrange 𝑛 elements in 𝑛 ordered positions are: 𝑛𝑃𝑛=𝑃(𝑛,𝑛)=𝑛(𝑛−1)(𝑛−2)⋯(2)(1) 𝑛 ordered positions =𝑛! The ways to arrange 𝑛 elements in 𝑟 ordered positions: Elements are arranged one after one in the 𝑟 ordered positions All steps to complete the task are independent of each other.The number of available elements will be reduced by one after every step. Therefore the ways to arrange 𝑛 elements in 𝑛 ordered positions are: 𝑛𝑃𝑟=𝑃(𝑛,𝑟)=𝑛(𝑛−1)(𝑛−2)⋯(𝑛−𝑟+1) 𝑟 ordered positions  =𝑛(𝑛−1)(𝑛−2)⋯(𝑛−𝑟+1)⋅(𝑛−𝑟)(𝑛−𝑟−1)⋯(2)(1)(𝑛−𝑟)(𝑛−𝑟−1)⋯(2)(1)  =𝑛(𝑛−1)(𝑛−2)⋯(𝑛−𝑟+1)(𝑛−𝑟)(𝑛−𝑟−1)⋯(2)(1)(𝑛−𝑟)(𝑛−𝑟−1)⋯(2)(1)  =𝑛!(𝑛−𝑟)!

Combination

For a given set of elements, a combination is a collection of elements of which the order of collected element does not matter.

Combination Example

For example, The ways to arrange 𝑛 elements in 𝑛 random positions: Elements are arranged one after one in the 𝑛 random positions All steps to complete the task are independent of each other.The number of available elements will be reduced by one after every step. But when the order of collected element does not matter, then all arrangements of the same selected elements can only be considered as one arrangement. The number of arrangements that can be grouped together is equal to all possible ways to rearrange elements in the 𝑛 random positions. The last step is to group all idential collections of each random collection pattern together as one single collection.Therefore the ways to arrange 𝑛 elements in 𝑛 random positions: 𝑛𝐶𝑛=𝐶(𝑛,𝑛)=𝑃(𝑛,𝑛)⋅1𝑃(𝑛,𝑛)  =𝑛(𝑛−1)(𝑛−2)⋯(2)(1) 𝑛 random positions ⋅1𝑛(𝑛−1)(𝑛−2)⋯(2)(1) each 𝑛 position duplicates  =𝑃(𝑛,𝑛)𝑃(𝑛,𝑛)=𝑛(𝑛−1)(𝑛−2)⋯(2)(1)𝑛(𝑛−1)(𝑛−2)⋯(2)(1)=1 The ways to arrange 𝑛 elements in 𝑟 random positions are: Elements are arranged one after one in the 𝑟 random positions All steps to complete the task are independent of each other.The number of available elements will be reduced by one after every step. But when the order of collected element does not matter, then all arrangements of the same selected elements can only be considered as one arrangement. The number of arrangements that can be grouped together is equal to all possible ways to rearrange elements in the 𝑟 random positions.The last step is to group all idential collections of each random collection pattern together as one single collection. Therefore the ways to arrange 𝑛 elements in 𝑟 random positions: 𝑛𝐶𝑟=𝐶(𝑛,𝑟)=𝑃(𝑛,𝑟)⋅1𝑃(𝑟,𝑟)  =𝑛(𝑛−1)(𝑛−2)⋯(𝑛−𝑟+1) 𝑟 random positions ⋅1𝑟(𝑟−1)(𝑟−2)⋯(2)(1) each 𝑟 position duplicates  =𝑃(𝑛,𝑟)𝑃(𝑟,𝑟)=𝑛!(𝑛−𝑟)!𝑟!(𝑟−𝑟)!=𝑛!(𝑛−𝑟)!𝑟!  =𝑛!(𝑛−𝑟)!𝑟!=𝑃(𝑛,𝑟)𝑟!  =𝑛!𝑟!(𝑛−𝑟)!=𝑛!(𝑛−(𝑛−𝑟))!(𝑛−𝑟)!=𝑃(𝑛,𝑛−𝑟)(𝑛−𝑟)!=𝑛𝐶𝑛−𝑟=𝐶(𝑛,𝑛−𝑟)

Circular Permutation

For a given set of elements, a circular permutation is a circular arrangement of elements for which the order of arranged elements must be taken into account.

For example, The ways to arrange 𝑛 elements in 𝑛 circular ordered positions: Elements are arranged one after one in the 𝑛 circular ordered positions All steps to complete the task are independent of each other.The number of available elements will be reduced by one after every step.Unlike linear permutation arrangement, the head and tail of a circular permutation arrangement in 𝑛 circular ordered positions are always connected together. Similar to combination arrangement, the same selected elements of the same order in a connected circular permutation arrangement can only be considered as one arrangement. The number of arrangements that can be grouped together is equal to all possible orientations for each unique linear arrangements moving around the fixed 𝑛 circular ordered positions. The last step is to group all idential circular ordered arrangements of each circular ordered pattern together as one single collection. Therefore the ways to arrange 𝑛 elements in 𝑛 circular ordered positions: 𝐶𝑃(𝑛,𝑛)=𝑃(𝑛,𝑛)⋅1𝑛  =𝑛(𝑛−1)(𝑛−2)⋯(2)(1) 𝑛 circular ordered positions ⋅1𝑛 each 𝑛 orientation duplicates  =𝑃(𝑛,𝑛)𝑛=𝑛!𝑛=(𝑛−1)! The ways to arrange 𝑛 elements in 𝑟 circular ordered positions: The permutation approach Elements are arranged one after one in the 𝑟 circular ordered positions All steps to complete the task are independent of each other.The number of available elements will be reduced by one after every step.Unlike linear permutation arrangement, the head and tail of a circular permutation arrangement in 𝑟 circular ordered positions are always connected together. Similar to combination arrangement, the same selected elements of the same order in a connected circular permutation arrangement can only be considered as one arrangement. The number of arrangements that can be grouped together is equal to all possible orientations for each unique linear arrangements moving around the fixed 𝑟 circular ordered positions. The last step is to group all idential circular ordered arrangements of each circular ordered pattern together as one single collection. Therefore the ways to arrange 𝑛 elements in 𝑟 circular ordered positions: 𝐶𝑃(𝑛,𝑟)=𝑃(𝑛,𝑟)⋅1𝑟  =𝑛(𝑛−1)(𝑛−2)⋯(𝑛−𝑟+1) 𝑟 circular ordered positions ⋅1𝑟 each 𝑟 orientation duplicates  =𝑃(𝑛,𝑟)𝑟=𝑛!(𝑛−𝑟)!𝑟
 =𝑛!(𝑛−𝑟)!𝑟 The combination approach All steps to complete the task are independent of each other.The first step is using combination arrangement to prepare the 𝑟 elements from 𝑛 elements with the order of collected element does not matter for the next circular ordered arrangement. The next step is always be an ordinary circular permutation of arranging 𝑟 elements in 𝑟 circular ordered positions Therefore the ways to arrange 𝑛 elements in 𝑟 circular ordered positions: 𝐶𝑃(𝑛,𝑟)=𝐶(𝑛,𝑟)𝐶𝑃(𝑟,𝑟)  =𝑛!(𝑛−𝑟)!𝑟! 𝑟 random elements from 𝑛 elements ⋅𝑟!𝑟 𝑟 elements in 𝑟 circular ordered positions  =𝐶(𝑛,𝑟)𝐶𝑃(𝑟,𝑟)=𝑛!(𝑛−𝑟)!𝑟!⋅𝑟!𝑟=𝑛!(𝑛−𝑟)!𝑟=𝑃(𝑛,𝑟)𝑟

Arrangement of Elements with Repetition

For a given set of 𝑛 elements with 𝑛₁ of type 1, 𝑛₂ of type 2, 𝑛₃ of type 3, ⋯ , 𝑛_𝑘 of type 𝑘, where 𝑛=𝑛₁+𝑛₂+𝑛₃+⋯+𝑛_𝑘. The arrangement of 𝑛 elements with repetition in 𝑛 ordered positions is also called permutation with repetition. However, the arrangement of 𝑛 elements with repetition in 𝑛 ordered positions can be determined by both Permutation and combination approaches. The permutation approach: The first step is to arrange all 𝑛 elements in 𝑛 ordered positions as an ordinary permutation arrangement. Since all arrangements are arranged together with all elements with repetition, the arrangements of elements with repetition of the same pattern on the same positions can only be considered as one arrangement because these arrangements are all identical. For each type of elements with repetition, the number of arrangements that can be grouped together for every possible arrangement of elements with repetition on all possible position patterns is equal to the permutation arrangement of the type of elements with repetition. The next steps are to group all idential ordered arrangements of each ordered pattern together as one single collection for each type of elements with repetitions one by one, i.e. 𝑛₁, 𝑛₂, ⋯ , 𝑛_𝑘. Therefore the ways, 𝑁, to arrange 𝑛 elements with 𝑛₁ of type 1, 𝑛₂ of type 2, 𝑛₃ of type 3, ⋯ , 𝑛_𝑘 of type 𝑘, where 𝑛=𝑛₁+𝑛₂+𝑛₃+⋯+𝑛_𝑘 in 𝑛 ordered positions: 𝑁=𝑃(𝑛,𝑛)⋅1𝑃(𝑛1,𝑛1)⋅1𝑃(𝑛2,𝑛2)⋅1𝑃(𝑛3,𝑛3)⋅⋯⋅1𝑃(𝑛𝑘,𝑛𝑘)  =𝑛! 𝑛 elements 𝑛 ordered positions ⋅1𝑛1! each 𝑛1 duplicates ⋅1𝑛2!⋅1𝑛3!⋅⋯ each ⋯ ⋅1𝑛𝑘! each 𝑛𝑘 duplicates  =𝑃(𝑛,𝑛)𝑃(𝑛1,𝑛1)𝑃(𝑛2,𝑛2)𝑃(𝑛3,𝑛3)⋯𝑃(𝑛𝑘,𝑛𝑘)=𝑛!𝑛1!𝑛2!𝑛3!⋯𝑛𝑘! The combination approach: The technique used is similar to the combination approach used in arranging 𝑛 elements in 𝑟 circular ordered positions But the arrangement process focus on the arrangement of the 𝑛 ordered position instead of the elements itself. All steps to complete the task are independent of each other. The arrangement steps use combination arrangement to select the collection of ordered positions for the corresponding elements with repetition that the order of collected element does not matter from 𝑛 ordered positions. The number of available ordered positions will be reduced by the amount of selected ordered positions after every step. Therefore the ways, 𝑁, to arrange 𝑛 elements with 𝑛₁ of type 1, 𝑛₂ of type 2, 𝑛₃ of type 3, ⋯ , 𝑛_𝑘 of type 𝑘, where 𝑛=𝑛₁+𝑛₂+𝑛₃+⋯+𝑛_𝑘 in 𝑛 ordered positions: 𝑁=𝐶(𝑛,𝑛1)⋅𝐶(𝑛−𝑛1,𝑛2)⋅𝐶(𝑛−𝑛1−𝑛2,𝑛3)⋅⋯⋅𝐶(𝑛−𝑛1−𝑛2−⋯−𝑛𝑘−1,𝑛𝑘)  =𝑛!(𝑛−𝑛1)𝑛1! 𝑛1 positions ⋅(𝑛−𝑛1)!(𝑛−𝑛1−𝑛2)𝑛2! 𝑛2 positions ⋅𝐶(𝑛−𝑛1−𝑛2,𝑛3)⋅⋯ 𝑛3⋯𝑛𝑘−1 positions ⋅(𝑛−𝑛1−𝑛2−𝑛3−⋯−𝑛𝑘−1)!(𝑛−𝑛1−𝑛2−𝑛3−⋯−𝑛𝑘)𝑛𝑘! 𝑛𝑘 positions  =𝑛!𝑛1!𝑛2!𝑛3!⋯𝑛𝑘!

Arrangement of Elements with Replacement

For a given set of 𝑛 elements with 𝑚₁, 𝑚₂, 𝑚₃, ⋯ , 𝑚_𝑛. The arrangement of 𝑛 elements in 𝑟 randoms positions with no restriction replacement, i.e. each element is allowed to choose more than once, also called combination with repetition.

The combination approach: The given set of elements, in some sense, can be considered as a given set of 𝑆 with s₁ of 𝑚₁, s₂ of 𝑚₂, s₃ of 𝑚₃, ⋯ , s_𝑛 of 𝑚_𝑛, where 𝑆=s₁+s₂+s₃+⋯+s_𝑛. There are many ways to determine the set 𝑆, one way is the generic element method. A generic element is a special element that will be changed accordingly to the selected element. Therefore a generic element can be used as a generic replacement element for the selected element automatically. For 𝑟 randoms positions, only 𝑟−1 generic replacement elements are needed, because at least one of the 𝑛 elements must be choosen before one or more, but least than 𝑟, replacement elements are needed and no 𝑟 generic replacement elements are allowed to be arranged in all 𝑟 randoms positions. Because of the generic property of generic replacement elements and the order of collected element does not matter, all generic replacement elements can be considered as an special type element of 𝑆 in addition to the given set of 𝑛 elements. Therefore, the elements of set 𝑆 are 𝑛 elements with 1 𝑚₁, 1 𝑚₂, 1 𝑚₃, ⋯ , 1 𝑚_𝑛, plus additional (𝑟−1) 𝑚_generic Therefore the ways to arrange 𝑛 elements in 𝑟 random positions with replacement: 𝑛𝑟=𝐶(𝑛+(𝑟−1),𝑟)=𝐶(𝑛+𝑟−1),𝑟)=(𝑛+(𝑟−1))!((𝑛+(𝑟−1))−𝑟)!𝑟!=𝑛+𝑟−1(𝑛−1)!𝑟!  =𝑛+𝑟−1((𝑛+𝑟−1)−(𝑛−1))!(𝑛−1)!=𝐶(𝑛+(𝑟−1),(𝑛−1))=𝐶(𝑛+𝑟−1,(𝑛−1))