Important
- Mathematical Induction and Recursion for theorem.01.
- Direct deductive proof for theorem.02.
- Let
$$S$$ be a set of members; such that$$S = \{ m_n: n \in N \}$$ . - If a sequence
$$Q$$ is required to be built; prevailing the properties of the sequences (i.e., mainly sequential ordering, and no repetition). - Thus, one good example would be
$$Q = (m_0, m_1, m_2, m_3, ... m_n)$$ . -
One bad example would be
$$Q = (m_0, m_1, m_0, m_2, m_3, m_0 ... m_n)$$ ; this example typically violates the two crucial properties of ordinal sequence collections. - To calculate the total number of all possible sequences that can be formed over the Set
$$S$$ of cardinality$$n$$ elements;
-
Base step: Let the number of all possible sequences is
$$P_0$$ ; then$$P_0 = (n-0)$$ could be the number of all possible available selections of members from the Set$$S$$ for the first position in the sequence$$Q$$ ; where$$Q = ()$$ at this stage. -
Inductive step: Moving forward in position inside the sequence
$$Q$$ to member$$m_{i + 1}$$ towards$$m_n$$ , and based on the properties of the sequences; it's observed that the subtrahend increases by a factor of 1; thus$$P_1 = (n-1)$$ could be the number of all possible available selections of members from the Set$$S$$ for the second position in the sequence$$Q$$ ; where$$Q = (m_0)$$ at this stage. -
Continue inductive step: Based on the multiplicative principle of counting; one can deduce that the total number of all possible subsequences taken over a set
$$S = \{ m_n: n \in N \land n < 2 \}$$ composed of 2 members is:$$P_t = P_0 \cdot P_1 = (n-0) \cdot (n-1)$$ . - Conclusion Step: Repeating the steps illustrated above for the other positions in the resulted sub-sequence
$$Q$$ reveals that the total number of all possible subsequences with cardinality$$n$$ taken from the set$$S$$ is:$$P_t = \prod_{i = 0}^{(n-1)} P_i = \prod_{i = 0}^{(n-1)} (n - i) = n \cdot (n - 1) \cdot (n - 2) ... (n - (n - 2)) \cdot (n - (n - 1)) = n!$$ . -
Additional conditions:
- Recall that the subsequences of interest are of cardinality
$$r$$ such that$$r < n$$ ; then the total number of all possible subsequences with cardinality$$r < n$$ taken over the set$$S$$ is:$$P_t = \prod_{i = 0}^{(r-1)} (n - i) = \frac{n!}{x}$$ ; which in case of$$r = n$$ ; the variable$$x$$ evaluates to 1.- Then;
$$x = \frac{n!}{\prod_{i = 0}^{(r-1)} (n - i)} = (n-r)!$$ . - Therefore; the number of possible permutations over a Set
$$S$$ of cardinality$$n$$ taken r at a time; such that$$r < n$$ is:$$_rP_n = \prod_{i = 0}^{(r-1)} (n - i) = \frac{n!}{x} = \frac{n!}{(n-r)!}$$ .<<Theorem.04>>
- Then;
- Recall another set
$$M_s$$ ; is a multi-set variant of Set$$S$$ ; hence if members are allowed only to appear once in the original Set$$S$$ ; therefore the set$$R_m$$ denoting the number of repetitions of the set members is:$$R_m = \{k_{m}: m \in N \land m\ is\ the\ index\ of\ the\ member\}$$ ; in this case all$$k_m$$ are equal to one.- In case of the multi-set
$$M_s$$ ; let the cardinality of the set be$$n$$ denoting the total number of elements in that set. - Let the set
$$M_s = \{m_n: n \in N\}$$ be decomposed into proper subsets; in which each subset encloses identical members (e.g.,$$M_s = \{\{b_0, b_1, b_2\}, \{c\}, \{d_0, d_1\}\}$$ ). - Therefore, based on this decomposition, each proper subset will have sole number of permutations (e.g.,
$$_bP_b = b!$$ ,$$_cP_c = c!$$ , and$$_dP_d = d!$$ ). - Now, to permutate each of one them into
$$n$$ -lengthed sequences; the number of permutations is multiplied by$$(n - k_m)$$ ; where$$k_m$$ is the cardinality of the proper subset for this specific member$$m$$ ; hence the number of permutations of a member$$m$$ over a sequence of cardinality$$n$$ ; in which the member will appear$$k_m$$ number of times is:$$k_{m}! \cdot (n - k_m)$$ . - Eventually, to permutate all of the proper subsets together within
$$n$$ -lengthed sequences; based on the multiplicative principle of counting we can obtain:$$[k_{0}! \cdot (n - k_0)] \cdot [k_{1}! \cdot (n - k_1)] ... [k_{m}! \cdot (n - k_m)]$$ which can be represented as:$$\prod_{m = 0}^{M - 1} [k_{m}! \cdot (n - k_m)]$$ ; where$$M$$ is the cardinality of$$M_s$$ (i.e., the number of proper subsets enclosing identical members). - Then,
$$\prod_{i = 0}^{n - 1} (n - i) = \prod_{m = 0}^{M - 1} [k_{m}! \cdot (n - k_m)]$$ ; where$$n$$ is the number of elements in the original multi-set$$M_s$$ , and$$M$$ is the number of the possible proper subsets enclosing identical members in the decomposed version of$$M_s$$ . - More simply:
$$n! = [k_{0}! \cdot (n - k_0)] \cdot [k_{1}! \cdot (n - k_1)] ... [k_{m}! \cdot (n - k_m)]$$ . - Hence, dividing both sides by
$$k_{0}! \cdot k_{1}! \cdot k_{2}! ... k_{m}!$$ ; will yield the number of distinguishable permutations.<<Theorem.05>>
- In case of the multi-set
- Recall that the subsequences of interest are of cardinality