Solveeit Logo
Login

Question

Question: The number of integers, between 100 and 1000 having the sum of their digits equals use coefficient ...

The number of integers, between 100 and 1000 having the sum of their digits equals use coefficient method

Answer

70

Explanation

Solution

To find the number of integers between 100 and 1000 having the sum of their digits equal to 14, we are looking for 3-digit numbers N=abcN = abc, where aa is the hundreds digit, bb is the tens digit, and cc is the units digit.

The constraints on the digits are:

  1. a∈{1,2,…,9}a \in \{1, 2, \ldots, 9\} (since it's a 3-digit number, aa cannot be 0)
  2. b∈{0,1,…,9}b \in \{0, 1, \ldots, 9\}
  3. c∈{0,1,…,9}c \in \{0, 1, \ldots, 9\}

The condition is a+b+c=14a + b + c = 14.

We will use the coefficient method (generating functions) to solve this problem.

The generating function for each digit represents the possible values it can take:

  • For digit aa: Ga(x)=x1+x2+…+x9=x(1+x+…+x8)=x1−x91−xG_a(x) = x^1 + x^2 + \ldots + x^9 = x(1 + x + \ldots + x^8) = x \frac{1-x^9}{1-x}
  • For digit bb: Gb(x)=x0+x1+…+x9=1−x101−xG_b(x) = x^0 + x^1 + \ldots + x^9 = \frac{1-x^{10}}{1-x}
  • For digit cc: Gc(x)=x0+x1+…+x9=1−x101−xG_c(x) = x^0 + x^1 + \ldots + x^9 = \frac{1-x^{10}}{1-x}

The generating function for the sum a+b+ca+b+c is the product of these individual generating functions:

G(x)=Ga(x)⋅Gb(x)⋅Gc(x)G(x) = G_a(x) \cdot G_b(x) \cdot G_c(x)

G(x)=(x1−x91−x)(1−x101−x)(1−x101−x)G(x) = \left(x \frac{1-x^9}{1-x}\right) \left(\frac{1-x^{10}}{1-x}\right) \left(\frac{1-x^{10}}{1-x}\right)

G(x)=x(1−x9)(1−x10)2(1−x)3G(x) = x \frac{(1-x^9)(1-x^{10})^2}{(1-x)^3}

We need to find the coefficient of x14x^{14} in the expansion of G(x)G(x). This is equivalent to finding the coefficient of x13x^{13} in the expression (1−x9)(1−x10)2(1−x)3\frac{(1-x^9)(1-x^{10})^2}{(1-x)^3}.

First, expand the numerator:

(1−x9)(1−x10)2=(1−x9)(1−2x10+x20)(1-x^9)(1-x^{10})^2 = (1-x^9)(1 - 2x^{10} + x^{20})

=1−2x10+x20−x9+2x19−x29= 1 - 2x^{10} + x^{20} - x^9 + 2x^{19} - x^{29}

Rearranging by powers:

=1−x9−2x10+2x19+x20−x29= 1 - x^9 - 2x^{10} + 2x^{19} + x^{20} - x^{29}

Now, we need the coefficient of x13x^{13} in:

(1−x9−2x10+2x19+x20−x29)(1−x)−3(1 - x^9 - 2x^{10} + 2x^{19} + x^{20} - x^{29}) (1-x)^{-3}

Recall the generalized binomial theorem for negative exponents:

(1−z)−n=∑k=0∞(n+k−1k)zk=∑k=0∞(n+k−1n−1)zk(1-z)^{-n} = \sum_{k=0}^{\infty} \binom{n+k-1}{k} z^k = \sum_{k=0}^{\infty} \binom{n+k-1}{n-1} z^k

For (1−x)−3(1-x)^{-3}, we have n=3n=3, so the coefficient of xkx^k is (3+k−13−1)=(k+22)\binom{3+k-1}{3-1} = \binom{k+2}{2}.

We look for terms in the product that contribute to x13x^{13}:

  1. From 1⋅(1−x)−31 \cdot (1-x)^{-3}: We need the coefficient of x13x^{13} from (1−x)−3(1-x)^{-3}.

    This is (13+22)=(152)=15×142=105\binom{13+2}{2} = \binom{15}{2} = \frac{15 \times 14}{2} = 105.

  2. From −x9⋅(1−x)−3-x^9 \cdot (1-x)^{-3}: We need the coefficient of x13−9=x4x^{13-9} = x^4 from (1−x)−3(1-x)^{-3}.

    This is −1×(4+22)=−(62)=−6×52=−15-1 \times \binom{4+2}{2} = -\binom{6}{2} = -\frac{6 \times 5}{2} = -15.

  3. From −2x10⋅(1−x)−3-2x^{10} \cdot (1-x)^{-3}: We need the coefficient of x13−10=x3x^{13-10} = x^3 from (1−x)−3(1-x)^{-3}.

    This is −2×(3+22)=−2×(52)=−2×5×42=−2×10=−20-2 \times \binom{3+2}{2} = -2 \times \binom{5}{2} = -2 \times \frac{5 \times 4}{2} = -2 \times 10 = -20.

  4. The terms 2x192x^{19}, x20x^{20}, and −x29-x^{29} have powers greater than 13, so they will not contribute to the coefficient of x13x^{13}.

Summing the contributions:

Total coefficient = 105−15−20=70105 - 15 - 20 = 70.

Thus, there are 70 integers between 100 and 1000 whose digits sum to 14.