Đến nội dung

Hình ảnh

Có bao nhiêu cách chia 37 viên bi vào 5 hộp khác nhau

- - - - -

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

#1
thinhisthenumber1

thinhisthenumber1

    Binh nhất

  • Thành viên mới
  • 28 Bài viết

Một hộp có $37$ viên và chia vào $5$ hộp khác nhau. Giả sử số bi ở lần lượt từng hộp là $x_{1},x_{2},x_{3},x_{4},x_{5}$. Hỏi có bao nhiêu cách chia số bi đó vào $5$ hộp sao cho $1\leq x_{1}\leq x_{2}\leq x_{3}\leq x_{4}\leq x_{5}$


Bài viết đã được chỉnh sửa nội dung bởi thinhisthenumber1: 23-04-2023 - 12:16


#2
hxthanh

hxthanh

    Tín đồ $\sum$

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

Một hộp có $37$ viên và chia vào $5$ hộp khác nhau. Giả sử số bi ở lần lượt từng hộp là $x_{1},x_{2},x_{3},x_{4},x_{5}$. Hỏi có bao nhiêu cách chia số bi đó vào $5$ hộp sao cho $1\leq x_{1}\leq x_{2}\leq x_{3}\leq x_{4}\leq x_{5}$

Hàm sinh cho bài này:
$\dfrac{x^5}{(1-x)(1-x^2)(1-x^3)(1-x^4)(1-x^5)}$
Mặc dù vậy khai triển ra cũng khá mệt.
Đáp số cho bài toán theo máy tính là $f(37,5)=831$
Việc khai triển hàm sinh, tìm hệ số bạn có thể nhờ sự trợ giúp đến từ @Nobodyv3

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 24-04-2023 - 02:46


#3
nguyendanggiap1234

nguyendanggiap1234

    Binh nhì

  • Thành viên mới
  • 10 Bài viết

Hàm sinh cho bài này:
$\dfrac{x^5}{(1-x)(1-x^2)(1-x^3)(1-x^4)(1-x^5)}$
Mặc dù vậy khai triển ra cũng khá mệt.
Đáp số cho bài toán theo máy tính là $f(37,5)=831$
Việc khai triển hàm sinh, tìm hệ số bạn có thể nhờ sự trợ giúp đến từ @Nobodyv3

Bài này mình có thể khai triển theo bổ đề Burnside được không thầy.



#4
hxthanh

hxthanh

    Tín đồ $\sum$

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

Bài này mình có thể khai triển theo bổ đề Burnside được không thầy.

Ý kiến không tệ chút nào!
Nếu các bộ nguyên dương có tổng bằng $n$ được phân loại thành:
$A=\{(a,b,c,d,e\};\;A_2=\{(a,a,b,c,d)\};\;$
$A_{22}=\{(a,a,b,b,c)\};\;A_{23}=\{(a,a,b,b,b)\};\;$
$A_3=\{(a,a,a,b,c)\};\;A_4=\{(a,a,a,a,b)\};\;$
$A_5=\{(a,a,a,a,a)\}$
thì theo bổ đề Burnside sẽ có:
$$|S|=\frac{|A|+10|A_2|+15|A_{22}|+20|A_{23}|+20|A_3|+30|A_4|+24|A_5|}{5!}$$
Các hệ số ở trên được tính bằng:
$\frac{5!}{(\text{số phần tử giống})(\text{số phần tử khác})!(\text{số bộ giống nhau})!}$

Ví dụ hệ số của $|A_2|$ là $\frac{5!}{2.3!}=10$,
hệ số của $|A_{22}|=\frac{5!}{2.2.1!2!}=15$, v.v…
Tiếp theo, ta tính:
$|A|={n-1\choose 4}$
$|A_2|=\sum_{a=1}^{\left\lfloor\frac{n-3}{2}\right\rfloor}\sum_{k=2}^{n-1-2a}(k-1)=…$ (tính cụ thể sau)
$|A_{22}|=\sum_{a=1}^{\left\lfloor\frac{n-3}{2}\right\rfloor}\left\lfloor\frac{n-1-2a}{2}\right\rfloor=\frac{1}{2}\left\lfloor\frac{n-3}{2}\right\rfloor\left\lfloor\frac{n-1}{2}\right\rfloor$
$|A_{23}|=\begin{cases}\left\lfloor\frac{n-2}{6}\right\rfloor\quad\text{nếu n chẵn}\\ \left\lfloor\frac{n+1}{6}\right\rfloor\quad\text{nếu n lẻ}\end{cases}$
$|A_3|=\sum_{a=1}^{\left\lfloor\frac{n-2}{3}\right\rfloor}(n-1-3a)=…$
$|A_4|=\left\lfloor\frac{n-1}{4}\right\rfloor$
$|A_5|=\left\lfloor\frac{n}{5}\right\rfloor-\left\lfloor\frac{n-1}{5}\right\rfloor$ (bằng 1 nếu n chia hết cho 5, ngược lại bằng 0)
(Tính ra cũng… dài không kém!)
Trở lại bài toán với $n=37$
$|A|={36\choose 4}=58905$
$|A_2|=\sum_{a=1}^{17}\frac{(36-2a)(35-2a)}{2}=…=3417$
$|A_{22}|=\frac{1}{2}.17.18=153$
$|A_{23}=\left\lfloor\frac{38}{6}\right\rfloor=6$
$|A_3|=\sum_{a=1}^{11}(36-3a)=198$
$|A_4|=\left\lfloor\frac{36}{4}\right\rfloor=9$
$|A_5|=0$
Số bộ $(a,b,c,d,e)$ nguyên dương sắp thứ tự thoả mãn $a+b+c+d+e=37$ là
$|S|=\frac{58905+10.3417+15.153+20.6+20.198+30.9+24.0}{120}$
$\quad =831$
——
(Ơn trời kết quả chính xác!)

#5
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
Wow, nice solution.
Thầy chịu khó ghê!
===========
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...

#6
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết
Việc giải bài toán như trên khá “lằng nhằng” nên cần giải thích thêm cho các bạn như sau:
Việc tìm nghiệm sắp thứ tự cho phương trình:
$a+b+c+d+e=n$
Nói cách khác là tách $n$ thành $5$ phần nguyên dương, hai cách tách là như nhau khi có các phần như nhau.
$|A|$ là số nghiệm nguyên dương của $a+b+c+d+e=n$
$|A|={n-1\choose 4}$ (cách chia kẹo Eurler)
Lấy $|A|$ chia cho $5!$ các hoán vị sẽ bị thiếu, vì chỉ có các bộ $5$ số nguyên đôi một khác nhau mới cho đủ $5!$ hoán vị.
Công việc của ta là đi đếm các bộ có ít nhất hai số giống nhau, cộng thêm vào tổng cho đủ $5!$ mỗi bộ, khi đó đem tổng chia $5!$ sẽ được kết quả cần tìm.
$|A_2|$ là số nghiệm nguyên dương của phương trình: $2a+b+c+d=n$
Giải pt này bằng cách cho $a$ biến thiên trong khoảng xác định, $b+c=k$ biến thiên phụ thuộc $a$,
$d$ được xác định duy nhất bởi ràng buộc $d=n-2a-k.$
$1\le a=\frac{n-b-c-d}{2}\le \left\lfloor\frac{n-3}{2}\right\rfloor$ là khoảng biến thiên của $a$
$2\le k=b+c=n-d-2a\le n-1-2a$ là khoảng biến thiên của $k$. Với mỗi giá trị $k$ thì phương trình $b+c=k$ có $k-1$ nghiệm $(1\le b=k-c\le k-1)$
Như vậy: $|A_2|=\sum_{a=1}^{\left\lfloor\frac{n-3}{2}\right\rfloor}\sum_{k=2}^{n-1-2a}(k-1)$
Các phương trình còn lại giải tương tự!

#7
hxthanh

hxthanh

    Tín đồ $\sum$

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

Wow, nice solution.
Thầy chịu khó ghê!

Cũng không hẳn vậy! Nếu đúng ra phải tính hết các tổng chứa phần nguyên kia, được một kết quả khá khủng, rồi xét module để rút gọn, cuối cùng đưa ra một công thức tổng quát cho $n$. Nghĩ đến thôi đã thấy mệt rồi :(
Đây là một bài toán đã được đề cập một số lần trên diễn đàn. Cách giải như trên từng được áp dụng cho $f(n,3)$ và $f(n,4)$. Mình cứ nghĩ rằng đó là “của riêng” ai dè giờ mới biết đó chỉ là một ứng dụng của bổ đề Burnside. Đúng thật là ếch ngồi đáy giếng mà!

#8
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
- Một người thầy tận tâm!
- Vâng, khi tính tay ( by hand and paper) các cấu hình đối xứng, em đếm cao lắm là tới $f(n,4)$, nhiều hơn nữa thì rất rối rắm, dễ mắc sai sót...
===========
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...

#9
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
Em tính hệ số của $\left | A_{23} \right |$ là $\frac{5!}{2.3.2!}=10$ không khớp với số liệu 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...

#10
hxthanh

hxthanh

    Tín đồ $\sum$

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

Em tính hệ số của $\left | A_{23} \right |$ là $\frac{5!}{2.3.2!}=10$ không khớp với số liệu của thầy?

À không có $2!$ vì hai bộ $(a,a)$ và $(b,b,b)$ khác nhau. Ở $A_{22}$ mới có vì $(a,a)$ và $(b,b)$ hoán vị được cho nhau!

——
Cùng cách làm này khi tính đến $f(n,6)$ thì kết quả trước khi chia cho $6!$ sẽ là tổng:
\begin{align*}|A|&+15|A_2|+45|A_{22}|+15|A_{222}|+40|A_3|+120|A_{32}|\\&+40|A_{33}|+90|A_4|+90|A_{42}|+144|A_5|+120|A_6|\end{align*}

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 26-04-2023 - 12:39


#11
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết
À, đúng rồi, em đọc không kỹ!
Cám ơn 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...

#12
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3915 Bài viết
Mệnh đề
Số nghiệm nguyên dương của phương trình $a+b+c+d+e=n$ là: $$|A|={n-1\choose 4}$$

Mệnh đề
Số nghiệm nguyên dương của phương trình $2a+b+c+d=n$ là:
$\small |A_2|= \left\lfloor \frac{n-3}2\right\rfloor \left\lfloor \frac{n-1}2\right\rfloor\left(\frac 23 \left\lfloor \frac{n-3}2\right\rfloor-\frac{3n-5}6\right)+$
$\small \qquad\qquad\qquad\qquad\qquad\qquad\qquad+\frac{n-2}2 \left\lfloor\frac n2\right\rfloor \left\lfloor \frac{n-3}2\right\rfloor $

Mệnh đề
Số nghiệm nguyên dương của phương trình $2a+2b+c=n$ là: $$|A_{22}|=\frac 12 \left\lfloor \frac{n-3}2\right\rfloor \left\lfloor \frac{n-1}2\right\rfloor $$

Mệnh đề
Số nghiệm nguyên dương của phương trình $2a+3b=n$ là:
$\small |A_{23}|=\!\left(\!\left\lfloor \!\frac{n\!+\!1}2\!\right\rfloor \!-\!\left\lfloor \frac n2\right\rfloor\!\right)\!\! \left(\!\left\lfloor\! \frac{n\!+\!1}6\!\right\rfloor\!-\!\left\lfloor \!\frac{n\!-\!2}6\!\right\rfloor\!\right)\!+\!\left\lfloor \!\frac{n\!-\!2}6\!\right\rfloor $

Mệnh đề
Số nghiệm nguyên dương của phương trình $3a+b+c=n$ là: $$|A_3|=\left\lfloor \frac{n-2}3\right\rfloor \left(n-1-\frac 32\left\lfloor \frac{n+1}3\right\rfloor\right) $$

Mệnh đề
Số nghiệm nguyên dương của phương trình $4a+b=n$ là: $$|A_4|=\left\lfloor\frac{n-1}4\right\rfloor$$

Mệnh đề
Số nghiệm nguyên dương của phương trình $5a=n$ là: $$|A_5|=\left\lfloor\frac n5\right\rfloor-\left\lfloor\frac {n-1}5\right\rfloor $$

Mệnh đề
Số nghiệm nguyên dương của phương trình
$\begin{cases}a+b+c+d+e=n\\ 1\le a\le b\le c\le d\le e\end{cases}\;\;$ là:
$\small f(n,5)=$
$\small \frac{|A|\!+\!10|A_2|\!+\!15|A_{22}|\!+\!20|A_{23}|\!+\!20|A_3|\!+\!30|A_4|\!+\!24|A_5|}{120}$

Mệnh đề
Số nghiệm nguyên dương của phương trình
$\begin{cases}a+b+c+d+e=n-10\\ 1\le a\le b\le c\le d\le e\end{cases}\;\;$ là:
$\small f(n-10,5)=$
$\small \frac{|A|\!-\!10|A_2|\!+\!15|A_{22}|\!-\!20|A_{23}|\!+\!20|A_3|\!-\!30|A_4|\!+\!24|A_5|}{120}$

Theorem có gợi ý cho bạn công thức đếm nào không?

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 06-05-2023 - 01:35


#13
Orangechess

Orangechess

    Lính mới

  • Thành viên mới
  • 5 Bài viết

Với mệnh đề 8 thầy có cách chứng minh khác để dễ hiểu hơn không ạ






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

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