Đến nội dung

Hình ảnh

$x_1+x_2+x_3+…+x_7=31$

- - - - -

  • Please log in to reply
Chủ đề này có 55 trả lời

#21
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết

Xét phương trình $x_1+x_2+x_3+…+x_k=n$ ($n\geqslant k$)
Gọi $p$ là số nguyên không âm nhỏ nhất sao cho $n-2k+p\ \vdots\ 3$ ($p$ là số nguyên xác định và $p\in \left \{ 0,1,2 \right \}$)
Gọi $k_1$ là số số hạng ở vế trái có dạng 3t+1. Ta có $k_1=p+3q$ (với $q$ từ $0$ đến $m={ \lfloor \frac{k-p}{3} \rfloor }$)
Xét các trường hợp :
1) $k_1=p$ ($q=0$)
   Chọn ra $p$ số hạng có dạng 3t+1 (có $C_k^p$ cách)
   Đặt tên lại $p$ số hạng 3t+1 là $a_1,…,a_p$ (chú ý $p$ là số nguyên xác định và $p\in\left \{ 0,1,2\right \}$)
   Và $k-p$ số hạng 3t+2 là $b_1,b_2,…,b_{k-p}$. Ta có các trường hợp :
  a) $\left\{\begin{matrix} a_1+...+a_p=p\\b_1+b_2+...+b_{k-p}=n-p \end{matrix} \right.$
     Theo các bổ đề 1 và 2 trên kia thì hệ này có $C_{p-1}^{p-1}C_{\frac{n+k-2p-3}{3}}^{k-p-1}$ nghiệm
  b) $\left\{\begin{matrix} a_1+…+a_p=p+3\\b_1+b_2+…+b_{k-p}=n-p-3 \end{matrix} \right.$
    Hệ này có $C_p^{p-1}C_{\frac{n+k-2p-6}{3}}^{k-p-1}$ nghiệm.
  ……………………………………………….
  Tổng cộng $C_{p-1}^{p-1}C_{\frac{n+k-2p-3}{3}}^{k-p-1}+C_p^{p-1}C_{\frac{n+k-2p-6}{3}}^{k-p-1}+…=C_{\frac{n+k+p-3}{3}}^{k-1}$
   Vậy trường hợp 1 có $C_k^pC_{\frac{n+k+p-3}{3}}^{k-1}$ nghiệm.
2) $k_1=p+3$ ($q=1$)
   Tương tự như trên, tính được trường hợp 2 có $C_k^{p+3}C_{\frac{n+k+p}{3}}^{k-1}$ nghiệm.
…………………………………………………
…………………..…………………………….
m+1) $k_1=p+3m$ ($q=m$)
   Cũng tương tự, trường hợp m+1 có $C_k^{p+3m}C_{\frac{n+k+p+3m-3}{3}}^{k-1}$ nghiệm.
Vậy đáp án cuối cùng là $\sum_{q=0}^{\left \lfloor \frac{k-p}{3} \right \rfloor }C_k^{p+3q}C_{\frac{n+k+p+3q-3}{3}}^{k-1}$
(trong đó $p$ là số được xác định như đã nói ở trên)

Anh kỹ lưỡng quá! Thank you.
Bài em đây, nhờ anh xem giúp:
Vì $\frac{z+z^{2}}{1-z^{3}}=z+z^{2}+z^{4}+z^{5}+z^{7}+z^{8}+...$ nên ta có hàm sinh $g(z)=\left ( \frac{z+z^{2}}{1-z^{3}} \right )^{k}$
Hệ số của số hạng $z^n$:
$ \left [ z^{n} \right ]g(z)=\left [ z^{n-k} \right ]\left ( \frac{1+z}{1-z^{3}} \right )^{k}\\
=\left [ z^{n-k} \right ]\sum_{i=0}^{\infty }\binom{k}{i}z^{i}\sum_{j=0}^{\infty }\left ( -1 \right )^j\binom{-k}{j}z^{3j}=\sum_{j=0}^{\infty }\binom{k}{n-k-3j}\left ( -1 \right )^j\binom{-k}{j}\\
=\sum_{j=0}^{\infty }\binom{k}{n-k-3j}\binom{j+k-1}{j}$
Do đó số nghiệm là :
$\boxed {\sum_{j=0}^{\left \lfloor \frac{n-k}{3} \right \rfloor}\binom{k}{n-k-3j}\binom{j+k-1}{j}}$
===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

#22
chanhquocnghiem

chanhquocnghiem

    Thiếu tá

  • Thành viên
  • 2494 Bài viết

Anh kỹ lưỡng quá! Thank you.
Bài em đây, nhờ anh xem giúp:
Vì $\frac{z+z^{2}}{1-z^{3}}=z+z^{2}+z^{4}+z^{5}+z^{7}+z^{8}+...$ nên ta có hàm sinh $g(z)=\left ( \frac{z+z^{2}}{1-z^{3}} \right )^{k}$
Hệ số của số hạng $z^n$:
$ \left [ z^{n} \right ]g(z)=\left [ z^{n-k} \right ]\left ( \frac{1+z}{1-z^{3}} \right )^{k}\\
=\left [ z^{n-k} \right ]\sum_{i=0}^{\infty }\binom{k}{i}z^{i}\sum_{j=0}^{\infty }\left ( -1 \right )^j\binom{-k}{j}z^{3j}=\sum_{j=0}^{\infty }\binom{k}{n-k-3j}\left ( -1 \right )^j\binom{-k}{j}\\
=\sum_{j=0}^{\infty }\binom{k}{n-k-3j}\binom{j+k-1}{j}$
Do đó số nghiệm là :
$\boxed {\sum_{j=0}^{\left \lfloor \frac{n-k}{3} \right \rfloor}\binom{k}{n-k-3j}\binom{j+k-1}{j}}$

Nhận xét :

- Kết quả 2 bài là tương đương.

- Lời giải của bạn rất ngắn gọn và tuyệt vời. Chúc mừng bạn  :D  :like


...

Ðêm nay tiễn đưa

Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...

 

http://www.wolframal...-15)(x^2-8x+12)


#23
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
Một bài chào mừng "chú lai phoa":
Tính số nghiệm nguyên của
$$x_{1}+x_{2}+x_{3}+x_{4}+x_{5}=21$$
sao cho $x_{i}\geq 0$ và $0\leq x_{1}\leq 3,1\leq x_{2}< 4,x_{3 }\geq 5$
===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

#24
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết

Nhận xét :
- Kết quả 2 bài là tương đương.
- Lời giải của bạn rất ngắn gọn và tuyệt vời. Chúc mừng bạn  :D  :like

Cám ơn anh đã động viên (mặc dù những lời khen của anh là rất hiếm, hiếm hoi như sao buổi sớm vậy!).
Nhân đây, em xin có đôi lời với các bạn đọc. Chắc hẳn các bạn cũng thấy chùm bài giải của em đều dùng hàm sinh. Vâng, đó là em đang PR cho hàm sinh đấy!: em cố gắng chứng minh là hàm sinh (generating functions) là một trong những công cụ rất mạnh để giải các bài toán đếm. Hãy nghiền ngẫm, nghiên cứu chúng ngõ hầu áp dụng khéo léo chúng để giải những bài toán mà trước đó ta nghĩ là không thể...
===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

#25
chanhquocnghiem

chanhquocnghiem

    Thiếu tá

  • Thành viên
  • 2494 Bài viết

Một bài chào mừng "chú lai phoa":
Tính số nghiệm nguyên của
$$x_{1}+x_{2}+x_{3}+x_{4}+x_{5}=21$$
sao cho $x_{i}\geq 0$ và $0\leq x_{1}\leq 3,1\leq x_{2}< 4,x_{3 }\geq 5$

Trong khi chờ đợi bạn giải bằng hàm sinh, mình sẽ tìm phương pháp khác (biết rằng dài dòng hơn nhưng cũng cứ đưa lên đây)

————————————————————-

Đặt $y_2=x_2-1$ ; $y_3=x_3-5$, ta có : $x_1+y_2+y_3+x_4+x_5=15$ 

($0\leqslant x_1\leqslant 3;0\leqslant y_2\leqslant 2;y_3,x_4,x_5\geqslant 0$)

$\Leftrightarrow$ $\left\{ \begin{matrix}x_1+y_2=k\\y_3+x_4+x_5=15-k \end {matrix} \right.$ $(0\leqslant k\leqslant 5)$

Cho $k$ chạy từ $0$ đến $5$, ta có đáp án là $1C_{17}^2+2C_{16}^2+3C_{15}^2+3C_{14}^2+2C_{13}^2+1C_{12}^2=1186$.


Bài viết đã được chỉnh sửa nội dung bởi chanhquocnghiem: 04-07-2022 - 15:36

...

Ðêm nay tiễn đưa

Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...

 

http://www.wolframal...-15)(x^2-8x+12)


#26
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
Cám ơn anh rất nhiệt tình tham gia. Còn dài hay ngắn thì tùy bài toán, chưa chắc dùng hàm sinh thì lời giải ngắn hơn đâu anh ạ!
Vâng, em sử dụng hàm sinh :
Ta có hàm sinh :
$g(z)=\sum_{x_{1}=0}^{3}z^{x_{1}}\sum_{x_{2}=1}^{3}z^{x_{2}}\sum_{x_{3}=5}^{\infty }z^{x_{3}}\sum_{x_{4}=0}^{\infty }z^{x_{4}}\sum_{x_{5}=0}^{\infty }z^{x_5}$
Hệ số của số hạng $z^{21}$:
$\left [ z^{21} \right ]g(z)=\left [ z^{21} \right ] \left ( \left ( \frac{1-z^{4}}{1-z} \right )\left ( \frac{z\left ( 1-z^{3} \right )}{1-z} \right )\left ( \frac{z^{5}}{1-z} \right )\left ( \frac{1}{1-z} \right )\left ( \frac{1}{1-z} \right ) \right )\\
=\left [z^{15} \right ]\left ( \frac{\left ( 1-z^{4} \right )\left ( 1-z^{3} \right )}{\left ( 1-z \right )^5} \right )
=\left [z^{15} \right ]\left ( \frac{1-z^{3}-z^{4}+z^{7}}{\left ( 1-z \right )^{5}} \right )\\
=\left (\left [z^{15} \right ]-\left [z^{12} \right ]-\left [z^{11} \right ] +\left [ z^8 \right ]\right)\sum_{j=0}^{\infty }\binom{j+4}{4}z^j \\
=\binom{15+4}{4}-\binom{12+4}{4}-\binom{11+4}{4}+\binom{8+4}{4}=\boxed {1186}$

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 04-07-2022 - 18:22

===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

#27
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
Em xin đơn cử bài toán quen thuộc :
Có bao nhiêu cách xếp 6 chàng trai và 8 cô gái thành 1 hàng sao cho không có 2 chàng trai liên tiếp.
Bài này giải rất nhẹ nhàng nhưng nếu dùng hàm sinh để giải là cả một vấn đề...
===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

#28
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4991 Bài viết

Em xin đơn cử bài toán quen thuộc :
Có bao nhiêu cách xếp 6 chàng trai và 8 cô gái thành 1 hàng sao cho không có 2 chàng trai liên tiếp.
Bài này giải rất nhẹ nhàng nhưng nếu dùng hàm sinh để giải là cả một vấn đề...

"Hàng" này là hàng dọc hay hàng ngang nhỉ? Nếu mình nhớ thì hàng ngang phải loại trừ trường hợp đối xứng trục chính giữa, còn hàng dọc thì không.


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#29
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết

"Hàng" này là hàng dọc hay hàng ngang nhỉ? Nếu mình nhớ thì hàng ngang phải loại trừ trường hợp đối xứng trục chính giữa, còn hàng dọc thì không.

Dạ, ý em là chỉ đếm cơ bản thôi mà không xét đến cấu hình đối xứng, quay, phản xạ...(nếu có) tức kết quả đơn giản là $8!6!C_{9}^{6}$ đó anh.

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 06-07-2022 - 09:36

===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

#30
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
Tiếp tục chùm bài toán "Tính số nghiệm... "
Tính số nghiệm nguyên của $$x_{1}+x_{2}+x_{3}+x_{4}+x_{5} =41$$ sao cho
$20\geq x_{i}\geq 0$ và $x_{i}$ chẵn với $i$ chẵn, $x_{i}$ lẻ với $i$ lẻ.

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 06-07-2022 - 19:16

===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

#31
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
Cuối tuần...
Tính số nghiệm nguyên của
$$x_{1}+x_{2}+x_{3}+x_{4}+x_{5}=12$$
sao cho $x_{i}\geq 0$ và $x_{1}< x_{2}\leq 4$
===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

#32
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết

Tiếp tục chùm bài toán "Tính số nghiệm... "
Tính số nghiệm nguyên của $$x_{1}+x_{2}+x_{3}+x_{4}+x_{5} =41$$ sao cho
$20\geq x_{i}\geq 0$ và $x_{i}$ chẵn với $i$ chẵn, $x_{i}$ lẻ với $i$ lẻ.

Hàm sinh cho các $x_{2,4}$:
$1+z^{2}+z^{4}+...+z^{20}=\frac{1-z^{22}}{1-z^2}$
Hàm sinh cho các $x_{1,3,5}$:
$z+z^{3}+z^{5}+...+z^{19}=\frac{z\left ( 1-z^{20} \right )}{1-z^{2}}$
Vậy ta có :
$g(z)=\left ( \frac{1-z^{22}}{1-z^2} \right )^{2}\left ( \frac{z\left ( 1-z^{20} \right )}{1-z^{2}} \right )^{3}$
Hệ số của $z^{41}$:
$\left [ z^{41} \right ]g(z)=\left [ z^{38}\right ]\left ( 1-3z^{20}+... \right )\left ( 1-2z^{22}+...\right ) \left ( 1-z^{2} \right )^{-5}\\
=\left [ z^{38} \right ]\left ( 1-3z^{20}-2z^{22}+h(z) \right )\sum_{j=0}^{\infty }\binom{-5}{j}\left ( -z^{2} \right )^{j}\\
=\left ( \left [ z^{38} \right ]-3\left [ z^{18} \right ] -2\left [ z^{16} \right ] \right )\sum_{j=0}^{\infty}\binom{j+4}{4}z^{2j}\\
=\binom{19+4}{4}-3\binom{9+4}{4}-2\binom{8+4}{4}= 8855-2145-990=\boxed {5720}$
===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

#33
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết

Cuối tuần...
Tính số nghiệm nguyên của
$$x_{1}+x_{2}+x_{3}+x_{4}+x_{5}=12$$
sao cho $x_{i}\geq 0$ và $x_{1}< x_{2}\leq 4$

Hàm sinh cho $x_{1},x_{2}$:
$\left ( z+z^2+z^3+z^4 \right )+z\left ( z^2+z^3+z^4 \right )+z^2\left ( z^3+z^4 \right )+z^3z^4=z+z^2+2z^3+2z^4+2z^5+z^6+z^7$
Ta có hàm sinh :
$g(z)= \left ( z+z^2+2z^3+2z^4+2z^5+z^6+z^7 \right )\frac{1}{\left ( 1-z \right )^{3}}$
Hệ số của $z^{12}$:
$\left [ z^{12} \right ]g(z)=\left ( \left [ z^{11} \right ]+\left [ z^{10}\right]+2 \left [ z^{9} \right ]+2 \left [ z^{8} \right ] +2 \left [ z^{7} \right ]+ \left [ z^{6} \right ]+ \left [ z^{5} \right ] \right )\sum_{j=0}^{\infty }\binom{j+2}{2}z^{j}\\
=\binom{13}{2}+\binom{12}{2}+2\binom{11}{2}+2\binom{10}{2}+2\binom{9}{2}+\binom{8}{2}+\binom{7}{2}=\boxed {465}$
===============
Em nghĩ topic cũng khá dài, nên em xin tạm dừng cuộc chơi tại đây (Ai là triệu phú? Không phải là em rồi!), có thể sẽ trở lại chủ đề này vào một thời điểm nào đó, tùy duyên!.
Nhân đây, xin cám ơn anh Chanhquocnghiem, anh Perfectstrong đã đồng hành trong cuộc chơi này.
Au revoir!
===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

#34
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết
Tăng thêm chút nhiệt cho nóng chủ đề này!
Trước tiên mời các bạn xem hình dưới đây
673C6D46-8392-41E7-B518-5D42F8AAB0EE.jpeg
Trong hình kết quả $6842$ là số cách viết số $31$ thành tổng của $k$ số hạng, $k$ chạy từ $1$ đến $31$ Không phân biệt vị trí của các số hạng trong tổng.

Đặt vấn đề:
Gọi $f(n,k)$ là số cách viết $n$ thành tổng gồm $k$ số hạng, không phân biệt vị trí của các số hạng trong tổng.
(Bảng giá trị và biểu đồ trong hình cho thấy sự “biến thiên” của hàm $f(31,k)$)
—-
1. Tính $f(31,7)$
2. Tính $f(n,3)$
3. Nếu có thể hãy tính:
a) $f(n,k)$
b)$\sum_{k=1}^n f(n,k)$
Gợi ý


#35
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
1/ Tính $f(31,7)$
Xét hàm sinh :
$g(x,y)=\prod_{k=1}^{32}\frac{1}{1-x^ky}$
Ta có khai triển:
$g(x,y)=\left ( 1+xy+x^2y^2+x^3y^3+... \right )\left ( 1+x^2y+x^4y^2+x^6y^3+... \right )... =1+y\left ( x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+...\right )+y^2\left ( x^2+x^3+2x^4+2x^5+3x^6+3x^7+4x^8+4x^9+...\right )+y^3\left ( x^3+x^4+2x^5+3x^6+4x^7+5x^8+7x^9+8x^{10}+...\right )+...=...+x^{31}\left ( ...+427y^5+612y^6+733y^7+764y^8+732y^9+... \right )+...$ $(*)$
Hệ số của số hạng $ x^{31}y^{7} $ trong $(*)$ chính là $f(31,7)$ cần tìm và bằng:
$\Rightarrow \left [ x^{31}y^{7} \right ]g\left ( x,y \right )=\boxed {733}$

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 08-08-2022 - 18:51

===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

#36
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
3a/ Tính $f(n,k)$
Ta biết rằng $\prod_{i=1}^{k}\frac{1}{1-x^i}$ là biểu thức tính số cách viết số $n$ thành các tổng có số số hạng nhỏ hơn hoặc bằng $k$. Suy ra, để tính số cách viết $n$ thành tổng có đúng $k$ số hạng thì:
$f(n,k)=[x^n]g(x)=[x^n]x^k\prod_{i=1}^{k}\frac{1}{1-x^i}$ $(*)$
T.dụ: tính $ f(10,5)$:
Áp dụng $(*)$ ta có :
$g(x)=x^5\prod_{i=1}^{5}\frac{1}{\left ( 1-x^i \right )}=...+13x^{12}+10x^{11}+7x^{10}+5x^{9}+3x^{8}+...$
Vậy $f(10,5)=7$

3b/ Suy ra :
$\sum_{k=1}^{n}f(n,k)=[x^n]h(x)=[x^n]\prod_{k=1}^{n}\frac{1}{1-x^k}$

Nhưng... hình như em trả lời không đúng yêu cầu của đề bài thì phải ...

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 09-08-2022 - 18:34

===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

#37
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết

3a/ Tính $f(n,k)$
Ta biết rằng $\prod_{i=1}^{k}\frac{1}{1-x^i}$ là biểu thức tính số cách viết số $n$ thành các tổng có số số hạng nhỏ hơn hoặc bằng $k$. Suy ra, để tính số cách viết $n$ thành tổng có đúng $k$ số hạng thì:
$f(n,k)=[x^n]g(x)=[x^n]x^k\prod_{i=1}^{k}\frac{1}{1-x^i}$ $(*)$
T.dụ: tính $ f(10,5)$:
Áp dụng $(*)$ ta có :
$g(x)=x^5\prod_{i=1}^{5}\frac{1}{\left ( 1-x^i \right )}=...+13x^{12}+10x^{11}+7x^{10}+5x^{9}+3x^{8}+...$
Vậy $f(10,5)=7$

Nhưng... hình như em trả lời không đúng yêu cầu của đề bài thì phải ...

Chỉ ra cách tính bằng hàm sinh đã là một nỗ lực của em rồi. Quả thực bài toán này không hề đơn giản, có một số cách biểu thị cách tính $f(n,k)$ và $\sum_{k=1}^nf(n,k)$
Tuy vậy cũng như tổng cơ bản, không công thức nào thực sự tính được trực tiếp theo $n$ và $k$ cả!
Vấn đề còn lại là với $k$ cụ thể ta sẽ tính thế nào?
2. Chứng minh rằng:
$f(n,3)=\left\lfloor \frac{n^2+3}{12}\right\rfloor$
Khoan hãy nhìn vào kết quả ở vế phải, quá trình “đếm” của lời giải (sẽ trình bày ở post sau) sử dụng một phương pháp tương tự Inclusion-Exclusion (Gộp vào - loại ra) gọi là đếm… thiếu!
Trong cách đếm này ta chỉ thêm chứ không bớt…
Đó cũng là phương pháp mình dùng để tính $f(n,4)$

Mình tin rằng còn nhiều phương án giải quyết cho câu hỏi cụ thể này và hy vọng có được một lời giải đẹp từ phía các bạn!

#38
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
Wow, thú vị quá! Câu chuyện bắt đầu vào cao trào rồi đây! Em háo hức xin lót dép ngồi chờ hóng hớt học hỏi...
PS:  Thưa thầy, ở Câu 2/,  em tiếp cận bài toán theo hướng tính số nghiệm nguyên của :
$ \left\{\begin{matrix}
x+y+z =n \\
1\leq x\leq y\leq z\leq n-2 
\end{matrix}\right.\Leftrightarrow \left\{\begin{matrix}
x+y+z =n-3 \\
0\leq x \leq y \leq z\leq n-3 
\end{matrix}\right. $
...không biết đúng không và chưa nghĩ ra hướng thu kết quả  lại  gọn đẹp như đáp án của thầy!Mong thầy chỉ dẫn ạ.
===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

#39
nhungvienkimcuong

nhungvienkimcuong

    Thiếu úy

  • Hiệp sỹ
  • 669 Bài viết

2. Chứng minh rằng:
$f(n,3)=\left\lfloor \frac{n^2+3}{12}\right\rfloor$

Việc tính $f(n,3)$ cũng chính là đếm số nghiệm nguyên dương của phương trình $x+y+z=n$ với $x\ge y\ge z$ (Cái này đã được thầy Thanh và anh Kool LL xử lí rất chi tiết ở đây  :luoi:)

 

Ngoài ra thì có một cách khác như này: một đẳng thức rất quan trọng trong phân hoạch là $f(n,k)=f(n-1,k-1)+f(n-k,k)$. Với $k=3$ ta có

$$f(n,3)=f(n-1,2)+f(n-3,3).$$

Dễ thấy $f(n,2)=\left \lfloor \frac{n}{2} \right \rfloor$, tới đây quy nạp là thu được điều cần chứng minh. 


Bài viết đã được chỉnh sửa nội dung bởi nhungvienkimcuong: 09-08-2022 - 21:38

Đừng khóc vì chuyện đã kết thúc hãy cười vì chuyện đã xảy ra ~O) 
Thật kì lạ anh không thể nhớ đến tên mình mà chỉ nhớ đến tên em :wub:
Chúa tạo ra vũ trụ của con người còn em tạo ra vũ trụ của anh :ukliam2:


#40
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết

Wow, thú vị quá! Câu chuyện bắt đầu vào cao trào rồi đây! Em háo hức xin lót dép ngồi chờ hóng hớt học hỏi...
PS:  Thưa thầy, ở Câu 2/,  em tiếp cận bài toán theo hướng tính số nghiệm nguyên của :
$ \left\{\begin{matrix}
x+y+z =n \\
1\leq x\leq y\leq z\leq n-2 
\end{matrix}\right.\Leftrightarrow \left\{\begin{matrix}
x+y+z =n-3 \\
0\leq x \leq y \leq z\leq n-3 
\end{matrix}\right. $
...không biết đúng không và chưa nghĩ ra hướng thu kết quả  lại  gọn đẹp như đáp án của thầy!Mong thầy chỉ dẫn ạ.

Đúng hướng đó em!

Việc tính $f(n,3)$ cũng chính là đếm số nghiệm nguyên dương của phương trình $x+y+z=n$ với $x\ge y\ge z$ (Cái này đã được thầy Thanh và anh Kool LL xử lí rất chi tiết ở đây :luoi:)

Ngoài ra thì có một cách khác như này: một đẳng thức rất quan trọng trong phân hoạch là $f(n,k)=f(n-1,k-1)+f(n-k,k)$. Với $k=3$ ta có
$$f(n,3)=f(n-1,2)+f(n-3,3).$$
Dễ thấy $f(n,2)=\left \lfloor \frac{n}{2} \right \rfloor$, tới đây quy nạp là thu được điều cần chứng minh.

Cảm ơn em đã “đào” được cái topic đó lên! Phát hiện công thức hồi quy của em rất đẹp, đúng là dễ dàng chứng minh nó, vậy mà mình chưa từng nghĩ ra, đến là lạ! Không biết công thức này có giúp ích cho việc tìm cttq hay không nhưng nó giúp cho ta chứng minh công thức tìm được bằng quy nạp trở nên đơn giản vô cùng!
Dành cho những ai còn chưa hiểu:
Xét phương trình
$x_1+x_2+…+x_k=n$ Với $1\le x_1\le x_2\le…\le x_k$
- Nếu $x_1=1$ thì $x_2+…+x_k=n-1$ Và $1\le x_2\le…\le x_k$
Số nghiệm này đúng bằng $f(n-1,k-1)$
- Nếu $2\le x_1\le x_2\le…\le x_k$ thì đặt $x_i=y_i+1,\;i=\overline{1,k}$, khi đó ta có
$y_1+y_2+…+y_k=n-k$ Và $1\le y_1\le y_2\le…\le y_k$
Số nghiệm này đúng bằng $f(n-k,k)$
Vậy ta có đẳng thức
$$f(n,k)=f(n-1,k-1)+f(n-k,k)$$
——————
Quay trở lại cách giải bài toán:
Xét các bộ nguyên dương $A=(a,b,c)$ mà $a+b+c=n$
Bằng bài toán chia kẹo Eurler ta có số cách chia là $|A|=\binom{n-1}{2}=\frac{(n-1)(n-2)}{2}$
Vì $(a,b,c)$ có tất cả $3!=6$ hoán vị nên
$f(n,3)=\frac{|A|}{6}\;\;\;???$
Đương nhiên kết luận này là sai vì các bộ $(a,a,b)$ chỉ có 3 hoán vị hay bộ $(a,a,a)$ nếu tồn tại thì chỉ có duy nhất 1 hoán vị.
Vậy thì trước khi chia cho 6, ta hãy đếm các bộ $(a,a,b)$ và $(a,a,a)$ cộng vào trong $A$ sao cho đủ $6$ lần mỗi bộ, rồi khi đó mới chia cho $6$. Ok(!)
Xét các bộ $B=(a,a,b)$
Ta có $a+a+b=n$ hay $b=n-2a$
Như vậy với mỗi giá trị của $a$ thì $b$ có lựa chọn duy nhất là $b=n-2a$
Mà $1\le a=\frac{n-b}{2}\le \frac{n-1}{2}$
Nên $|B|= \left\lfloor\frac{n-1}{2}\right\rfloor$
Bộ $C=(a,a,a)$ tồn tại duy nhất khi và chỉ khi $3\;|\;n$
Hay $|C|=\left\lfloor\frac{n}{3}\right\rfloor- \left\lfloor\frac{n-1}{3}\right\rfloor $
Kết quả là
$$f(n,3)=\frac{|A|+3|B|+2|C|}{6}$$
Để loại bỏ các phép toán phần nguyên, hãy đặt
$n=6p+r=6p+(0,1,2,3,4,5)$
Mỗi số trong ngoặc đại diện cho mỗi trường hợp của $n$
Thay vào và rút gọn lại ta được
$f(n,3)=3p^2+pr+(0,0,0,1,1,2)$
Mặt khác $n^2=36p^2+12pr+r^2=36p^2+12pr+(0,1,4,9,16,25)$
Suy ra $n^2+3= 36p^2+12pr+(3,4,7,12,19,28)$
Khi đó $\left\lfloor\frac{n^2+3}{12}\right\rfloor=3p^2+pr+(0,0,0,1,1,2)$
Có thể kết luận rằng:
$$f(n,3)= \left\lfloor\frac{n^2+3}{12}\right\rfloor = \left\lfloor\frac{n^2+\alpha}{12}\right\rfloor,\;\;\;\; 3\le \alpha<8$$




0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh