Discrete Mathematics: Generating Functions

Generating Functions


  1. How many ways are there to make $N$ cents using pennies and nickels?

    2. $$ \boxed{\frac{1}{(1-x)(1-x^5)} = (1 + x + x^2 + x^3 + x^4 + x^5 + \ldots)(1 + x^5 + x^{10} + x^{15} + x^{20} + x^{25} + \ldots)} $$
    $$ \boxed{\Big\lfloor \frac{N}{5} \Big\rfloor + 1} $$
  2. How many ways are there to make $N$ cents using pennies, nickels, and dimes?

Comments

Post a Comment

Popular posts from this blog

Discrete Mathematics: Induction

Image
Induction Prove each of the following statements using mathematical induction. Triangular Numbers (Sum of First \(n\) Positive Integers): \[ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} \] Example. $N=10$ Sum of Odd Numbers: \[ 1 + 3 + 5 + \cdots + (2n-1) = n^2 \] Example. $N=10$ Sum of First \(n\) Square Numbers: \[ 1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6} \] Example. $N=5$ Tetrahedral Numbers (Sum of First $n$ Triangular Numbers): \[ 1 + 3 + 6 + 10 + \cdots + \frac{n(n+1)}{2} = \frac{n(n+1)(n+2)}{6} \] Example. $N=5$ Sum of First \(n\) Cubes: \[ 1^3 + 2^3 + 3^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2 \] Example. $N=5$ Geometric Series Partial Sum: \[ \sum_{k=0}^{n-1} r^k = \frac{r^n-1}{r-1}, \quad r \ne 1 \] Example. $r=2$ Example. $r=4$ Pascal's Identity: \[ \binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}, \quad n \ge 0,\...
Read more

Discrete Mathematics: Permutations With Repetition

Image
Permutations With Repetition How many distinct strings with length \(L\) are there in a system with \(N\) digits \(0,\ldots,N-1\)? Example. $N=2, L=4$ Example. $N=3, L=3$ $$\boxed{N^L}$$ How many distinct strings with length \(L\) are there in a system with \(N\) digits \(0,\ldots,N-1\) without leading zero? Example. $N=2, L=4$ Example. $N=3, L=3$ $$\boxed{(N-1)N^{L-1}}$$ 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? Example. $N=2, L=4, K=2$ Example. $N=3, L=3, K=1$ $$\boxed{\binom{L}{K}(N-1)^{L-K}}$$ 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? Example. $N=2, L=4, K=2$ Example. $N=3,L=3, K=1$ $$ \boxed{ \sum_{t=K}^{L} \bi...
Read more