Draft for Information Only
ContentBasic Counting Techniques
Basic Counting TechniquesIn 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 PrincipleThe strategies used to count something involve two different approaches, the addition principle and the multiple principle. The Addition PrincipleThe 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 PrincipleThe 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. FactorialFactorial notation, '!' is a compact representation for the multiplication of consecutive integers. e.g 𝑛!=𝑛(𝑛−1)(𝑛−2)⋯(2)(1), where n is a positive integer.
Arrangement ProcessesThe ways to arrange of element can be classified to two cataloges, permutation and combination. PermutationFor 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 ExampleFor 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:
CombinationFor a given set of elements, a combination is a collection of elements of which the order of collected element does not matter. Combination ExampleFor 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: Circular PermutationFor 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:
Arrangement of Elements with RepetitionFor a given set of 𝑛 elements with 𝑛_{1} of type 1, 𝑛_{2} of type 2, 𝑛_{3} of type 3, ⋯ , 𝑛_{𝑘} of type 𝑘, where 𝑛=𝑛_{1}+𝑛_{2}+𝑛_{3}+⋯+𝑛_{𝑘}. 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. 𝑛_{1}, 𝑛_{2}, ⋯ , 𝑛_{𝑘}.
Therefore the ways, 𝑁, to arrange 𝑛 elements with 𝑛_{1} of type 1, 𝑛_{2} of type 2, 𝑛_{3} of type 3, ⋯ , 𝑛_{𝑘} of type 𝑘, where 𝑛=𝑛_{1}+𝑛_{2}+𝑛_{3}+⋯+𝑛_{𝑘} in 𝑛 ordered positions:
Arrangement of Elements with ReplacementFor a given set of 𝑛 elements with 𝑚_{1}, 𝑚_{2}, 𝑚_{3}, ⋯ , 𝑚_{𝑛}. 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_{1} of 𝑚_{1}, s_{2} of 𝑚_{2}, s_{3} of 𝑚_{3}, ⋯ , s_{𝑛} of 𝑚_{𝑛}, where 𝑆=s_{1}+s_{2}+s_{3}+⋯+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 𝑚_{2}, 1 𝑚_{3}, ⋯ , 1 𝑚_{𝑛}, plus additional (𝑟−1) 𝑚_{generic}
Therefore the ways to arrange 𝑛 elements in 𝑟 random positions with replacement:
©sideway ID: 190500010 Last Updated: 10/5/2019 Revision: 0 Ref: References
Latest Updated Links

Home_{ 5} Business Management HBR_{ 3} Information Recreation Hobbies_{ 8} Culture Chinese_{ 1097} English_{ 337} Reference_{ 67} Computer Hardware_{ 149} Software Application_{ 197} Digitization_{ 86} Numeric_{ 19} Programming Web_{ 738} HTML_{ 65} CSS_{ 58} ASP.NET_{ 62} OS_{ 389} DeskTop_{ 7} Python_{ 8} Knowledge Mathematics Formulas_{ 8} Algebra_{ 25} Number Theory_{ 206} Trigonometry_{ 18} Geometry_{ 18} Calculus_{ 67} Complex Analysis_{ 21} Engineering Tables_{ 8} Mechanical Mechanics_{ 1} Rigid Bodies Statics_{ 92} Dynamics_{ 37} Fluid_{ 5} Fluid Kinematics_{ 5} Control Process Control_{ 1} Acoustics_{ 19} FiniteElement_{ 2} Physics Electric_{ 27} Biology_{ 1} Geography_{ 1} 
Copyright © 20002020 Sideway . All rights reserved Disclaimers last modified on 06 September 2019