Chương trình đếm cách sắp A và B sao cho tiền tố/hậu tố đều B≥A trong Python

Cho n chữ A và 2n chữ B. Đếm số hoán vị sao cho mọi tiền tố và hậu tố đều có #B ≥ #A.

Quan sát

• Đây là biến thể của số Catalan / đường Dyck.
• Đáp án: f(1)=1, f(2)=4, f(n) = f(⌊n/2⌋)^2.

Ví dụ

def solve(n):
    if n == 1:
        return 1
    if n == 2:
        return 4
    if n % 2 == 1:
        return solve((n - 1) // 2) ** 2
    else:
        return solve(n // 2) ** 2

print(solve(2))  # Output: 4

Giải thích

n=2: 2A,4B. 4 cách: BBAABB, BABABB, BBABAB, BABBAB.