Tính $S=\sum_{a<b<c<d}abcd$
#1
Đã gửi 27-10-2024 - 20:37
$S=\sum_{a<b<c<d}abcd$ theo $n, \, \forall a,b,c,d\in\lbrace 1,2,3,…,n \rbrace$
- perfectstrong, hxthanh, Leonguyen và 1 người khác yêu thích
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...
- I thought, most of counting problems in combinatorics could be done by generating functions but unfortunately, since my knowledge on them isn't very deep yet, I'm a little lost...
#2
Đã gửi 30-10-2024 - 15:38
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.
#3
Đã gửi 30-10-2024 - 22:40
Em nghĩ hơi hơi giống mà thui! Bài này rối rắm hơn chứ ạ.Giống bài trước nhể
https://diendantoanh...jleq-kleq-nijk/
Em xin trình bày 1 cách :
Ta xét 5 TH:
TH 0: $a,b,c,d$ không có ràng buộc gì.
$$S_0=\sum_{a=1}^{n}\sum_{b=1}^{n}\sum_{c=1}^{n}\sum_{d=1}^{n}abcd=\left (\sum_{a=1}^{n} a \right )\left (\sum_{b=1}^{n} b \right )\left (\sum_{c=1}^{n} c \right )\left (\sum_{d=1}^{n} d \right )=\left[ \frac {n(n+1)}2\right ]^4$$TH 1: có 2 thừa số bằng nhau, giả sử $a=b$.
$$S_1=\sum_{a=1}^{n}\sum_{c=1}^{n}\sum_{d=1}^{n}a^2cd=\left (\sum_{a=1}^{n} a^2 \right )\left (\sum_{c=1}^{n} c \right )\left (\sum_{d=1}^{n} d \right )=\left[ \frac {n(n+1)(2n+1)}6\right ] \left[ \frac {n(n+1)}2\right ]^2$$TH 2: có 2 cặp thừa số bằng nhau, giả sử $a=b,\,c=d$.
$$S_2=\sum_{a=1}^{n}\sum_{c=1}^{n}a^2c^2=\left (\sum_{a=1}^{n} a^2 \right )\left (\sum_{c=1}^{n} c^2 \right )=\left[ \frac {n(n+1)(2n+1)}6\right ]^2$$TH 3: có 3 thừa số bằng nhau, giả sử $a=b=c$.
$$S_3=\sum_{a=1}^{n}\sum_{d=1}^{n}a^3d=\left (\sum_{a=1}^{n} a^3 \right )\left (\sum_{d=1}^{n} d \right )=\left[ \frac {n^2(n+1)^2}4\right ] \left[ \frac {n(n+1)}2\right ]$$TH 4: cả 4 thừa số bằng nhau.
$$S_4=\sum_{a=1}^{n}a^4= \frac {n(n+1)(2n+1)(3n^2+3n-1)}{30}$$Và theo nguyên lý bù trừ, với $a\ne b\ne c\ne d $ ta có :
$$\begin {align*}
\sum_{a=1}^{n}\sum_{b=1}^{n}\sum_{c=1}^{n}\sum_{d=1}^{n}abcd&=S_0-6S_1+3S_2+8S_3-6S_4\\
&=\frac {n(n+1)(n-1)(n-2)(n-3)(15n^3+15n^2-10n-8)}{240}\\
\Rightarrow \sum_{1\leq a<b<c<d}abcd&=\frac 1{4!}\left[ \frac {n(n+1)(n-1)(n-2)(n-3)(15n^3+15n^2-10n-8)}{240} \right ]\\
&=\boldsymbol {\frac {n(n+1)(n-1)(n-2)(n-3)(15n^3+15n^2-10n-8)}{5760}}
\end{align*}$$
Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 30-10-2024 - 22:52
- hxthanh, vutuanhien và DOTOANNANG thích
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...
- I thought, most of counting problems in combinatorics could be done by generating functions but unfortunately, since my knowledge on them isn't very deep yet, I'm a little lost...
#4
Đã gửi 31-10-2024 - 01:10
$S=\sum_{a=1}^{n-3}\sum_{b=a+1}^{n-2}\sum_{c=b+1}^{n-1}\sum_{d=c+1}^n abcd$
từ trong ra ngoài xem có đúng không?
$S=\sum_{a=1}^{n-3}\sum_{b=a+1}^{n-2}\sum_{c=b+1}^{n-1} \dfrac{abc(n+c+1)(n-c)}{2}$
…
thêm 3 lần nữa, mỗi lần tăng thêm 2 bậc kể ra cũng ngại!
Theo WFA thì.. kết quả là
$\dfrac{n(n-2)(n-3)(15n^5+15n^4-25n^3-23n^2+10n+8)}{5760}$
- DOTOANNANG và Nobodyv3 thích
#5
Đã gửi 31-10-2024 - 23:07
Thanks everyone.
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...
- I thought, most of counting problems in combinatorics could be done by generating functions but unfortunately, since my knowledge on them isn't very deep yet, I'm a little lost...
#6
Đã gửi 02-11-2024 - 05:21
Để mình thử sức xem
Đặt các hàm như sau:
\begin{align*}
{F_4}\left( n \right) &= \sum\limits_{1 \le a < b < c < d \le n} {abcd} \\
{F_3}\left( n \right) &= \sum\limits_{1 \le a < b < c \le n} {abc} \\
{F_2}\left( n \right) &= \sum\limits_{1 \le a < b \le n} {ab} \\
{F_1}\left( n \right) &= \sum\limits_{1 \le a \le n} a
\end{align*}
Dễ thấy ${F_1}\left( n \right) = \frac{{n\left( {n + 1} \right)}}{2}$
Tiếp tục, ta tính truy hồi từng hàm theo thứ tự phức tạp tăng dần (phải nhờ Wolfram-Alpha "chun chút" )
\begin{align*}
{F_2}\left( {n + 1} \right) & = \left( {n + 1} \right){F_1}\left( n \right) + {F_2}\left( n \right)\\
& = \frac{{n{{\left( {n + 1} \right)}^2}}}{2} + {F_2}\left( n \right)\\
\Rightarrow {F_2}\left( n \right)& = \frac{1}{2}\sum\limits_{k = 1}^{n - 1} {k{{\left( {k + 1} \right)}^2}} \\
&= \frac{1}{{24}}\left( {n - 1} \right)n\left( {n + 1} \right)\left( {3n + 2} \right)\\
{F_3}\left( {n + 1} \right)& = \left( {n + 1} \right){F_2}\left( k \right) + {F_3}\left( n \right)\\
&= \frac{1}{{24}}\left( {n - 1} \right)n{\left( {n + 1} \right)^2}\left( {3n + 2} \right) + {F_3}\left( n \right)\\
\Rightarrow {F_3}\left( n \right) &= \frac{1}{{24}}\sum\limits_{k = 1}^{n - 1} {\left( {k - 1} \right)n{{\left( {k + 1} \right)}^2}\left( {3k + 2} \right)} \\
&= \frac{1}{{48}}\left( {n - 2} \right)\left( {n - 1} \right){n^2}{\left( {n + 1} \right)^2}\\
{F_4}\left( {n + 1} \right) &= \left( {n + 1} \right){F_3}\left( n \right) + {F_4}\left( n \right)\\
&= \frac{1}{{48}}\left( {n - 2} \right)\left( {n - 1} \right){n^2}{\left( {n + 1} \right)^3} + {F_4}\left( n \right)\\
\Rightarrow {F_4}\left( n \right) &= \frac{1}{{48}}\sum\limits_{k = 1}^{n - 1} {\left( {k - 2} \right)\left( {k - 1} \right){k^2}{{\left( {k + 1} \right)}^3}} \\
&= \frac{1}{{5760}}\left( {n - 3} \right)\left( {n - 2} \right)\left( {n - 1} \right)n\left( {n + 1} \right)\left( {15{n^3} + 15{n^2} - 10n - 8} \right)
\end{align*}
Hú vía ra đúng số với mọi người
Công thức truy hồi tổng quát cho tổng của tích $m$ số nguyên dương phân biệt không quá $n$ là:
\[{F_{m + 1}}\left( {n + 1} \right) = \left( {n + 1} \right){F_m}\left( n \right) + {F_{m + 1}}\left( n \right)\]
Công thức chung của $F_m(n)$ có vẻ là:
\[{F_m}\left( n \right) = \frac{{\left( {n + 1} \right)!}}{{\left( {n - m} \right)!}}\frac{1}{{{C_m}}}{G_m}\left( n \right)\]
Với $C_m$ là một hệ số nguyên theo $m$ và $G_m$ là một đa thức nguyên bậc $m-1$. Mình vẫn chưa tìm ra công thức tổng quát của $C_m$ và $G_m$, đành nhờ mọi người giúp
- hxthanh, DOTOANNANG và Nobodyv3 thích
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.
#7
Đã gửi 02-11-2024 - 13:24
$S=\sum_{1\leq a<b<c<d\leq n}abcd=\sum_{d=4}^{n}\sum_{c=3}^{d-1}\sum_{b=2}^{c-1}\sum_{a=1}^{b-1}abcd$
Ta có :
$$\begin {align*}
\sum_{a=1}^{b-1}a&=\binom b2\\
\sum_{b=2}^{c-1}b\binom b2&= \sum_{b=2}^{c-1}\left [3\binom b3+
2\binom b2\right] =3\binom c4+2\binom c3\\
\sum_{c=3}^{d-1}c\left [3\binom c4+
2\binom c3\right] &=\sum_{c=3}^{d-1}\left [15\binom c5+
20\binom c4+6\binom c3\right] \\
&=15\binom d6+20\binom d5+6\binom d4\\
\Rightarrow S&=\sum_{d=4}^{n}d\left [15\binom d6+
20\binom d5+6\binom d4\right] \\&=\sum_{d=4}^{n}\left [105\binom d7+
210\binom d6+130\binom d5+24\binom d4\right] \\
&=105\binom {n+1}8+210\binom {n+1}7+130\binom {n+1}6+24\binom {n+1}5\\
&=\boldsymbol {\frac{(n-3)(n-2)(n-1)n(n+1)(15n^3+15n^2-10n-8)}{5760}}
\end{align*}$$
- perfectstrong và hxthanh thích
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...
- I thought, most of counting problems in combinatorics could be done by generating functions but unfortunately, since my knowledge on them isn't very deep yet, I'm a little lost...
#8
Đã gửi 02-11-2024 - 20:22
Cách này tuyệt vời nhất!Thú vị quá! Em xin đóng góp 1 lời giải nữa :
$S=\sum_{1\leq a<b<c<d\leq n}abcd=\sum_{d=4}^{n}\sum_{c=3}^{d-1}\sum_{b=2}^{c-1}\sum_{a=1}^{b-1}abcd$
Ta có :…
- perfectstrong và Nobodyv3 thích
#9
Đã gửi 03-11-2024 - 05:56
Cảm ơn thầy. Ý tưởng này có được cũng là từ bài giải của thầy.Cách này tuyệt vời nhất!
- hxthanh yêu thích
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...
- I thought, most of counting problems in combinatorics could be done by generating functions but unfortunately, since my knowledge on them isn't very deep yet, I'm a little lost...
#10
Đã gửi 03-11-2024 - 19:36
Cảm ơn thầy. Ý tưởng này có được cũng là từ bài giải của thầy.
Đấy! Quan trọng ở chỗ học 1 biết 10 của bạn. Với ý tưởng giới hạn khoảng biến thiên của mỗi biến chạy, tôi thực hiện phép lấy tổng từ biến $d \to a$ dẫn tới “cận dưới” nó bị xấu dần đều, ngược lại bạn thực hiện lấy tổng từ $a\to d$ khéo léo dùng tính chất “teleport” của binomial dẫn đến bài toán sáng sủa và ít phép tính đi rất nhiều. Hãy áp dụng cách này cho bài toán cũ của bạn, xem nó hữu dụng như thế nào!
- Nobodyv3 yêu thích
#11
Đã gửi 03-11-2024 - 19:53
Thú vị quá! Em xin đóng góp 1 lời giải nữa :
$S=\sum_{1\leq a<b<c<d\leq n}abcd=\sum_{d=4}^{n}\sum_{c=3}^{d-1}\sum_{b=2}^{c-1}\sum_{a=1}^{b-1}abcd$
Ta có :
$$\begin {align*}
\sum_{a=1}^{b-1}a&=\binom b2\\
\sum_{b=2}^{c-1}b\binom b2&= \sum_{b=2}^{c-1}\left [3\binom b3+
2\binom b2\right] =3\binom c4+2\binom c3\\
\sum_{c=3}^{d-1}c\left [3\binom c4+
2\binom c3\right] &=\sum_{c=3}^{d-1}\left [15\binom c5+
20\binom c4+6\binom c3\right] \\
&=15\binom d6+20\binom d5+6\binom d4\\
\Rightarrow S&=\sum_{d=4}^{n}d\left [15\binom d6+
20\binom d5+6\binom d4\right] \\&=\sum_{d=4}^{n}\left [105\binom d7+
210\binom d6+130\binom d5+24\binom d4\right] \\
&=105\binom {n+1}8+210\binom {n+1}7+130\binom {n+1}6+24\binom {n+1}5\\
&=\boldsymbol {\frac{(n-3)(n-2)(n-1)n(n+1)(15n^3+15n^2-10n-8)}{5760}}
\end{align*}$$
Lời giải này đẹp và tự nhiên Có thể giải thích phần nào ý nghĩa trực quan của $F_m(n)$:
\[{F_m}\left( n \right) = \sum\limits_{k = m + 1}^{2m} {{C_{m,k}}\left( {\begin{array}{*{20}{c}} {n + 1}\\ k \end{array}} \right)} \]
Giờ chỉ còn cái tính các hệ số
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.
#12
Đã gửi 03-11-2024 - 21:29
Xếp theo kiểu “tam giác Pascal” sẽ có:Lời giải này đẹp và tự nhiên Có thể giải thích phần nào ý nghĩa trực quan của $F_m(n)$:
\[{F_m}\left( n \right) = \sum\limits_{k = m + 1}^{2m} {{C_{m,k}}\left( {\begin{array}{*{20}{c}} {n + 1}\\ k \end{array}} \right)} \]
Giờ chỉ còn cái tính các hệ số
\begin{array}{cccccc}
1&&&&&\\
2& 3&&&&\\
6& 20& 15&&&\\
24& 130& 210& 105&&\\
120& 924& 2380 &2520&945&\\
…&…&…&…&…&…&\\
\end{array}
Cột 1 là 1!, 2!, 3!…
Cạnh “huyền” là 1, 1.3, 1.3.5, 1.3.5.7,…
Tổng đan dấu bằng $\pm 1$
20=6+15-1; 24+210=130+105-1; v.v…
Còn dấu hiệu gì nữa nhỉ?
$(2+3).4=20$
$(6+20).5=130$
$(20+15).6=210$
…
Viết lại Hàm $F_m(n)$ của perfectstrong dạng
$$F_m(n)=\sum_{k=1}^m C_{m,k}\binom{n+1}{m+k}$$
Khi đó ta có công thức truy hồi của “Tam giác” trên là:
\begin{equation}C_{m+1,k+1}=(m+k+1)(C_{m,k}+C_{m,k+1})\end{equation}
———
Đến đây xây dựng bài toán kiểu:
Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 05-11-2024 - 14:12
- perfectstrong và Nobodyv3 thích
#13
Đã gửi 04-11-2024 - 20:37
_Yes, Sir.Đấy! Quan trọng ở chỗ học 1 biết 10 của bạn. Với ý tưởng giới hạn khoảng biến thiên của mỗi biến chạy, tôi thực hiện phép lấy tổng từ biến $d \to a$ dẫn tới “cận dưới” nó bị xấu dần đều, ngược lại bạn thực hiện lấy tổng từ $a\to d$ khéo léo dùng tính chất “teleport” của binomial dẫn đến bài toán sáng sủa và ít phép tính đi rất nhiều. Hãy áp dụng cách này cho bài toán cũ của bạn, xem nó hữu dụng như thế nào!
==========
Đề bài : Tính
$$\displaystyle \mathop{\sum\sum\sum}_{1\leq i\leq j\leq k\leq n}ijk $$Giải:
Ta có :
$$\begin{align*} \underbrace{\underset{1\le i\le j\le k\le n}{\mathop{\sum }}\,ijk}_S&=\underbrace{\underset{1\le i< j< k\le n}{\mathop{\sum }}\,ijk}_{S_1} \\
&\quad +\underbrace{\underset{1\le i= j< k\le n}{\mathop{\sum }}\,ijk+\underset{1\le i< j= k\le n}{\mathop{\sum }}\,ijk+\underset{1\le i= j= k\le n}{\mathop{\sum }}\,ijk}_{S_2}
\end{align*}$$- Tính $S_1$:
$$\begin {align*}
S_1&=\sum_{k=3}^{n}\sum_{j=2}^{k-1}\sum_{i=1}^{j-1}ijk\\
\text{mà:}\qquad \qquad &\\
\sum_{i=1}^{j-1}i&=\binom j2\\
\sum_{j=2}^{k-1}j\binom j2&=\sum_{j=2}^{k-1}\left[ 3\binom j3+2\binom j2 \right]=3\binom k4+2\binom k3 \\
\Rightarrow S_1&=\sum_{k=3}^{n}k\left[
3\binom k4+2\binom k3 \right] \\
&=3\sum_{k=3}^{n}\left[
5\binom k5+4\binom k4 \right]+2\sum_{k=3}^{n}\left[
4\binom k4+3\binom k3 \right]\\
&=15\binom{n+1}6+20\binom{n+1}5+6\binom{n+1}4\\
&=\frac 1{48}(n-2)(n-1)n^2(n+1)^2
\end{align*}$$- Tính $S_2$:
$$\begin {align*}
S_2&=\underset{1\le i= j, k\le n}{\mathop{\sum }}\,ijk=\left ( \sum_{j=1}^{n}j^2 \right )\left ( \sum_{k=1}^{n}k \right )\\
&=\frac {1}{6}n(n+1)(2n+1)\cdot \frac {1}{2}n(n+1)\\
&=\frac {1}{12}n^2(n+1)^2(2n+1)
\end{align*}$$Do đó :
$$\begin {align*}
S&=\frac {1}{48}n^2(n+1)^2(n-1)(n-2)+\frac {1}{12}n^2(n+1)^2(2n+1)\\
&=\frac {1}{48}n^2(n+1)^2(n^2+5n+6)\\
&=\boldsymbol {\frac {1}{48}n^2(n+1)^2(n+2)(n+3)}
\end{align*}$$
Chú thích :
Để tính $S_1$, ta sử dụng 2 đẳng thức tổ hợp :
$n\binom nr=(r+1)\binom n{r+1}+r\binom nr$
và (hockey - stick identity) :
$\displaystyle{ \binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + \cdots + \binom{n}{r} = \binom{n+1}{r+1}. }$
Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 04-11-2024 - 21:12
- perfectstrong và hxthanh thích
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...
- I thought, most of counting problems in combinatorics could be done by generating functions but unfortunately, since my knowledge on them isn't very deep yet, I'm a little lost...
#14
Đã gửi 04-11-2024 - 21:13
\begin {align*}
\sum_{a=1}^{b}a&=\binom {b+1}2\\
\sum_{b=1}^{c}b\binom {b+1}2&= \sum_{b=1}^{c}\left [3\binom {b+1}3+
\binom {b+1}2\right] \\&=3\binom {c+2}4+\binom {c+2}3\\
\sum_{c=1}^{n}c\left [3\binom {c+2}4+
\binom {c+2}3\right] &=\sum_{c=1}^{n}\left [15\binom {c+2}5+
10\binom {c+2}4+\binom {c+2}3\right] \\
&=15\binom {n+3}6+10\binom {n+3}5+\binom {n+3}4\\
\Rightarrow \sum_{c=1}^n\sum_{b=1}^c\sum_{a=1}^b abc&=
\boldsymbol {\dfrac{n^2(n+1)^2(n+2)(n+3)}{48}}
\end{align*}
Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 04-11-2024 - 22:58
- perfectstrong và Nobodyv3 thích
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh