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

[Saturina]

Cho em hỏi có công thức nào tính nhanh tổng này không ạ

$$\sum_{i=0}^{m} \binom{n}{i}$$  với ($m \le n$)

[tienmai]

Mình đoán ý bạn ở câu hỏi trên là tổng đó có một công thức dạng đóng nào không, theo kiểu $\sum^{n}_{k=1} k = \frac{n(n+1)}{2}$. Câu trả lời là: đến nay vẫn chưa có một công thức dạng đóng nào cho tổng $\displaystyle\sum^{m}_{i=0}\binom{n}{i}$.

 

Mình dám nói là chưa có công thức dạng đóng nào vì mình đã tìm kiếm hồi lâu với Google, theo câu tìm kiếm: "partial sum of binomial coefficients". Mặt khác, tổng trên có ý nghĩa thế này: tổng các chuỗi nhị phân độ dài $n$, trong đó số $1$ xuất hiện không quá $m$ lần. Với tổng trên, người ta quan tâm đến cận trên của nó, chưa tim ra (và rất chắc là không có) công thức dạng đóng. "Chấp niệm" này nên bỏ qua thôi. Trong thực tế, có nhiều thứ không có công thức dạng đóng.

 

Còn để tính nhanh, cũng chưa có một cách tính trên giấy mà hiệu quả, ngoại trừ rất ít trường hợp đặc biệt của $m$. Cách tính nhanh nhất hiện giờ là viết một chương trình nhỏ (một hàm) để tính tổng trên. Nếu bạn làm theo cách này thì hãy cẩn thận với giai thừa vì giai thừa tăng rất nhanh.

 

Mình nghĩ là bạn có một mục tiêu hoặc vấn đề toán học/khoa học nào khác để mà dẫn tới nhu cầu tính tổng trên một cách hiệu quả. Nếu là vậy, việc thảo luận vấn đề gốc có thể sẽ có ích hơn, bởi biết đâu lại có một hướng đi không cụt.

[Saturina]

Mình đoán ý bạn ở câu hỏi trên là tổng đó có một công thức dạng đóng nào không, theo kiểu $\sum^{n}_{k=1} k = \frac{n(n+1)}{2}$. Câu trả lời là: đến nay vẫn chưa có một công thức dạng đóng nào cho tổng $\displaystyle\sum^{m}_{i=0}\binom{n}{i}$.

 

Mình dám nói là chưa có công thức dạng đóng nào vì mình đã tìm kiếm hồi lâu với Google, theo câu tìm kiếm: "partial sum of binomial coefficients". Mặt khác, tổng trên có ý nghĩa thế này: tổng các chuỗi nhị phân độ dài $n$, trong đó số $1$ xuất hiện không quá $m$ lần. Với tổng trên, người ta quan tâm đến cận trên của nó, chưa tim ra (và rất chắc là không có) công thức dạng đóng. "Chấp niệm" này nên bỏ qua thôi. Trong thực tế, có nhiều thứ không có công thức dạng đóng.

 

Còn để tính nhanh, cũng chưa có một cách tính trên giấy mà hiệu quả, ngoại trừ rất ít trường hợp đặc biệt của $m$. Cách tính nhanh nhất hiện giờ là viết một chương trình nhỏ (một hàm) để tính tổng trên. Nếu bạn làm theo cách này thì hãy cẩn thận với giai thừa vì giai thừa tăng rất nhanh.

 

Mình nghĩ là bạn có một mục tiêu hoặc vấn đề toán học/khoa học nào khác để mà dẫn tới nhu cầu tính tổng trên một cách hiệu quả. Nếu là vậy, việc thảo luận vấn đề gốc có thể sẽ có ích hơn, bởi biết đâu lại có một hướng đi không cụt.

mình cảm ơn bạn nhé, thực ra mình đang có một vấn đề về lập trình, nhưng vấn đề là việc tính tổng đó mất nhiều thời gian ( thời gian của máy tính ấy ) nên là mình muốn xem có công thức nào không )

[tienmai]

Mình viết một chương trình Python 3.

 

Ý tưởng trong đoạn code đi kèm là memoize tam giác Pascal bằng đệ quy với công thức Pascal thay vì dùng công thức hệ số nhị thức.

 

Dùng tam giác Pascal thì chỉ cần cộng. Dùng công thức hệ số nhị thức còn phải nhân nữa, nhân rất nhiều. Mình đã chạy thử với input như bên dưới, chỉ mất vài giây trong thời gian thực tế.

def partial_binomial(n: int, m: int) -> int:
    if m > n:
        return 0
    elif m == n:
        return 2 ** n
    else:
        # key: (int, int), value: int
        # key is an int 2-tuple, value is an int
        binomials = dict({})
        def calculate_binomial(n: int, k: int) -> None:
            for r in range(0, n+1):
                if r == 0:
                    binomials[(0, 0)] = 1
                elif r == 1:
                    binomials[(1, 0)] = 1
                    binomials[(1, 1)] = 1
                else:
                    for s in range(0, r+1):
                        if s == 0:
                            binomials[(r, s)] = 1
                        elif r-1 < s:
                            binomials[(r, s)] = binomials.get((r-1,s-1)) 
                        else:
                            binomials[(r, s)] = binomials.get((r-1,s-1)) + binomials.get((r-1,s))

        calculate_binomial(n, m)
        sum = 0
        for j in range(0,m+1):
            sum = sum + binomials.get((n, j))
        return sum

print(partial_binomial(1000, 223))

[Konstante]

Sử dụng trực tiếp công thức của hệ số nhị thức có lẽ nhanh hơn rất nhiều so với kỹ thuật memoization của dynamic programming. Với lưu ý là vì $i! \mid \prod_{j=1}^{i} (n-j+1)$ với mọi $1 \leq i \leq n$ nên có thể thực hiện phép chia ngay lập tức mà không cần phải tính hết toàn bộ hàm giai thừa.

 

Ví dụ đoạn code Python này:

 

(n, k) = (1000, 223)
b = 1

for i in range(1,k+1):
    b = (b * (n - i + 1)) // i

assert(b == math.comb(n,k))
print(int(b))

tính $\binom{1000}{223}$ chỉ mất vài micro giây.

Bài viết đã được chỉnh sửa nội dung bởi Konstante: 16-08-2023 - 16:46

[perfectstrong]

Nhận xét của bạn tienmai rất xác đáng. Nên thay đổi góc nhìn trong bài toán gốc để tìm ra công thức đóng, hoặc ít nhất là một công thức hồi quy để giảm thiểu tính toán.