Chủ đề này có 3 trả lời

[Nobodyv3]

1/ Có bao nhiêu số tự nhiên từ 0 đến 99999 có tổng các chữ số là s.
2/ Số các số tự nhiên từ 1 đến $10^k$ có tổng các chữ số nhỏ hơn hoặc bằng s.

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 22-05-2023 - 19:42

[chanhquocnghiem]

1/ Có bao nhiêu số tự nhiên từ 0 đến 99999 có tổng các chữ số là s.
2/ Số các số tự nhiên từ 1 đến $10^k$ có tổng các chữ số nhỏ hơn hoặc bằng s.

1) Hàm sinh $f(x)=\left ( \frac{1-x^{10}}{1-x} \right )^5=\left ( 1-5x^{10}+10x^{20}-10x^{30}+5x^{40}-x^{50} \right )\sum_{i=0}^{\infty}C_{i+4}^4x^i$

    Số số tự nhiên từ $0$ đến $99999$ có tổng các chữ số là $s$ là :

   $\left [ x^s \right ]f(x)=\binom{s+4}{4}-5\binom{s-6}{4}+10\binom{s-16}{4}-10\binom{s-26}{4}+5\binom{s-36}{4}$

2) Gọi số stn từ $1$ đến $10^k$ thỏa mãn là $M_s$. Xét các trường hợp :

 a) $s=0$ : Không có số nào (từ $1$ đến $10^k$) thỏa mãn yêu cầu ($M_0=0$)

 b) $s=1$ : Có $k+1$ số (từ $1$ đến $10^k$) thỏa mãn yêu cầu ($M_1=k+1$)

 c) $s> 1$ :

     Hàm sinh $f(x)=\left ( \frac{1-x^{10}}{1-x} \right )^k=\left ( 1-C_k^1x^{10}+C_k^2x^{20}-C_k^3x^{30}+... \right )\sum_{i=0}^{\infty}C_{i+k-1}^{k-1}x^i$

   $M_s=\sum_{i=0}^{s}\left [ x^i \right ]f(x)=\binom{k}{0}\binom{s+k}{k}-\binom{k}{1}\binom{s+k-10}{k}+\binom{k}{2}\binom{s+k-20}{k}-...=$

            $=\sum_{j=0}^{k}(-1)^j\binom{k}{j}\binom{s+k-10j}{k}$.
 

Bài viết đã được chỉnh sửa nội dung bởi chanhquocnghiem: 22-05-2023 - 22:45

[Nobodyv3]

1/ Với $ 0\leq s\leq 45$ ta có:
$$\begin{align*}
\Rightarrow [x^s]\left(\frac{1-x^{10}}{1-x}\right)^5
&=[x^s](1-x^{10})^5\sum_{i=0}^{\infty}\binom{-5}{i}(-x)^i\\
&=[x^s]\sum_{j=0}^{5}\binom{5}{j}(-1)^jx^{10j}\sum_{i=0}^{\infty}\binom{i+4}{4}x^i\\
&=\sum_{j=0}^{\lfloor s/10\rfloor}\binom{5}{j}(-1)^j[x^{s-10j}]\sum_{i=0}^{\infty}\binom{i+4}{4}x^i\\
&=\sum_{j=0}^{\lfloor s/10\rfloor}(-1)^j\binom{5}{j}\binom{s-10j+4}{4}
\end{align*}$$

[Nobodyv3]

2/ Xét các số có m chữ số , với $1\leq m\leq k$ và số $10^k$ có k+1 chữ số, tổng chữ số là 1:
- Hàm sinh cho chữ số ngoài cùng bên trái :$\frac {x(1-x^9)}{1-x}$.
- Hàm sinh cho m-1 chữ số còn lại : $\left (\frac {1-x^{10}}{1-x}\right) ^{m-1}$
- Thêm $\frac {1}{1-x}$ để tính tổng các hệ số.
- Cộng thêm 1: là mã hóa số $10^k$.
Vậy ta có :
$$\begin{align*}
[x^s]&\sum_{m=1}^k \frac{x(1-x^9)}{1-x}\left(\frac{1-x^{10}}{1-x}\right)^{m-1}\frac{1}{1-x}+1\\
&=[x^{s-1}]\frac{1-x^9}{(1-x)^2}\sum_{m=1}^k\left(\frac{1-x^{10}}{1-x}\right)^{m-1}+1\\
&=[x^{s-1}]\frac{1-x^9}{(1-x)^2}\sum_{m=0}^{k-1}\left(\frac{1-x^{10}}{1-x}\right)^{m}+1\\
&=[x^{s-1}]\frac{1-x^9}{(1-x)^2}\,\frac{1-\left(\frac{1-x^{10}}{1-x}\right)^k}{1-\frac{1-x^{10}}{1-x}}+1\\
&=[x^s]\left(\frac{\left(1-x^{10}\right)^k}{(1-x)^{k+1}}-\frac{1}{1-x}\right)+1\\
&=[x^s]\frac{\left(1-x^{10}\right)^k}{(1-x)^{k+1}}\\
&=[x^s]\sum_{j=0}^\infty\binom{-(k+1)}{j}(-x)^j\left(1-x^{10}\right)^k\\
&=\sum_{j=0}^s\binom{k+j}{k}[x^{s-j}]\left(1-x^{10}\right)^k\\
&=\sum_{j=0}^s\binom{k+s-j}{k}[x^j]\sum_{l=0}^k\binom{k}{l}(-1)^lx^{10l}\\
&=\sum_{j=0}^{\lfloor s/10\rfloor}\binom{k+s-10j}{k}[x^{10j}]\sum_{l=0}^k\binom{k}{l}(-1)^lx^{10l}\\
&\,\,=\sum_{j=0}^{\lfloor s/10\rfloor}(-1)^j \binom{k}{j} \binom{k+s-10j}{k}
\end{align*}$$