Discrete Mathematics: Permutations With Repetition

Permutations With Repetition


  1. How many distinct strings with length \(L\) are there in a system with \(N\) digits \(0,\ldots,N-1\)?

    2. Example. $N=2, L=4$


    Example. $N=3, L=3$


    $$\boxed{N^L}$$
  2. How many distinct strings with length \(L\) are there in a system with \(N\) digits \(0,\ldots,N-1\) without leading zero?

    3. Example. $N=2, L=4$


    Example. $N=3, L=3$


    $$\boxed{(N-1)N^{L-1}}$$
  3. How many distinct strings with length \(L\) are there in a system with \(N\) digits \(0,\ldots,N-1\) where the digit \(1\) appears exactly \(K\) times?

    4. Example. $N=2, L=4, K=2$


    Example. $N=3, L=3, K=1$


    $$\boxed{\binom{L}{K}(N-1)^{L-K}}$$
  4. How many distinct strings with length \(L\) are there in a system with \(N\) digits \(0,\ldots,N-1\) where the digit \(1\) appears at least \(K\) times?

    5. Example. $N=2, L=4, K=2$


    Example. $N=3,L=3, K=1$


    $$ \boxed{ \sum_{t=K}^{L} \binom{L}{t}(N-1)^{L-t} = N^L - \sum_{t=0}^{K-1} \binom{L}{t}(N-1)^{L-t} } $$
  5. How many distinct strings of length \(L\) are there in a system with \(N\) digits \(0,\ldots,N-1\) with no two consecutive \(1\)s? Hint: Let \(S_L\) be the number of valid strings with length $L$. Consider cases when the last digit is not \(1\) and when the last digit is \(1\) and the previous digit is not \(1\).

    6. Example. $N=2,L=4$


    Example. $N=3,L=3$


    $$\boxed{ S_L = (N-1)S_{L-1} + (N-1)S_{L-2} }$$
  6. How many distinct strings with length \(L\) are there in a system with \(N\) digits \(0,\ldots,N-1\) that uses \(K\) distinct digits? Hint: Use the Inclusion-Exclusion Principle

    7. $$ \left| \bigcap_{i=0}^{K} A_i^c \right| = |T| - \sum_{i=0}^{K} |A_i| $$ $$ + \sum_{0 \le i_1 < i_2 \le K} |A_{i_1} \cap A_{i_2}| - \ldots $$ $$ + (-1)^{K+1} \sum_{0 \le i_1 < \ldots < i_{K} \le K} \left| A_{i_1} \cap \cdots \cap A_{i_{K}} \right| $$

    where \(T\) is the total set of strings of length \(L\) formed from a chosen set of \(K\) digits and \(A_i\) is the set of strings from \(T\) that completely exclude the \(i\)th chosen digit.


    Example. $N=2,L=4, K=1$


    Example. $N=3, L=3, K=2$


    $$\boxed{ \binom{N}{K} \sum_{i=0}^{K} (-1)^i \binom{K}{i}(K-i)^L }$$
  7. How many distinct strings of length \(L\) can be formed using digits \(0,1,\ldots,N-1\) where each digit \(i\) appears exactly \(n_i\) times (so \(n_0+n_1+\cdots+n_{N-1}=L\))?

    8. Example. $N=2, L=4, n_0=3, n_1=1$


    Example. $N=3, L=3, n_0=1, n_1=1, n_2=1$



    $$\boxed{ \frac{L!}{n_0!\,n_1!\cdots n_{N-1}!} }$$

Comments

Post a Comment