Đến nội dung

Hình ảnh

Tính $S=\sum_{a<b<c<d}abcd$

- - - - -

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

#1
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 1067 Bài viết
Tính :
$S=\sum_{a<b<c<d}abcd$ theo $n, \, \forall a,b,c,d\in\lbrace 1,2,3,…,n \rbrace$
===========
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
perfectstrong

perfectstrong

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

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

Giống bài trước nhể :luoi:

https://diendantoanh...jleq-kleq-nijk/


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.

#3
Nobodyv3

Nobodyv3

    Generating Functions Faithful

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

Giống bài trước nhể :luoi:
https://diendantoanh...jleq-kleq-nijk/

Em nghĩ hơi hơi giống mà thui! Bài này rối rắm hơn chứ ạ.
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

===========
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
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3948 Bài viết
Thử tính:
$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}$

#5
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 1067 Bài viết
Ồ, may quá, kết quả trùng với đáp án của thầy.
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
perfectstrong

perfectstrong

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

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

Để mình thử sức xem :D

Đặ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" :D)

\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 :D

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 :D


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.

#7
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 1067 Bài viế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ó :
$$\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*}$$
===========
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
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3948 Bài viế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ó :…

Cách này tuyệt vời nhất!

#9
Nobodyv3

Nobodyv3

    Generating Functions Faithful

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

Cách này tuyệt vời nhất!

Cảm ơn thầy. Ý tưởng này có được cũng là từ bài giải của thầy.
===========
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
hxthanh

hxthanh

    Tín đồ $\sum$

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

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!

#11
perfectstrong

perfectstrong

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

  • Quản lý Toán Ứng dụng
  • 5065 Bài viế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ó :
$$\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 :D 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ố :icon10:


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.

#12
hxthanh

hxthanh

    Tín đồ $\sum$

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

Lời giải này đẹp và tự nhiên :D 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ố :icon10:

Xếp theo kiểu “tam giác Pascal” sẽ có:
\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 toán
Với các số tự nhiên $m,k$, người ta định nghĩa hàm số nguyên $C_{m,k}$ như sau:
$C_{m,0}=0, \forall m\in\mathbb N^*$
$C_{m,k}=0, \forall k> m$
$C_{0,0}=1$
$C_{m+1,k+1}=(m+k+1)(C_{m,k}+C_{m,k+1}),\forall m,k\in \mathbb N$
Hãy tính giá trị của tổng:
$S_n=\sum_{k=1}^n (-1)^kC_{n,k}$

:luoi:

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 05-11-2024 - 14:12


#13
Nobodyv3

Nobodyv3

    Generating Functions Faithful

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

Đấ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!

_Yes, Sir.
==========
Đề 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

===========
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
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3948 Bài viết
Sao lại phức tạp vậy nhỉ?
\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





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

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