Delannoy Numbers คืออะไร? หาเลข Delannoy ใน C++

Delannoy Numbers คืออะไร?

Delannoy Number D(m,n) = จำนวนเส้นทางจาก (0,0) ไป (m,n) บน Grid โดยเดินได้ 3 ทิศทาง:

• → East (Right): (x+1, y)
• ↑ North (Up): (x, y+1)
• ↗ Northeast (Diagonal): (x+1, y+1)

Recurrence Relation

D(m,n) = D(m-1,n) + D(m,n-1) + D(m-1,n-1)
Base: D(0,0) = 1
D(m,0) = 1, D(0,n) = 1 (Only East or Only North)

ตัวอย่าง

D(3,3) = 63 paths

Central Delannoy Numbers: D(n,n)

1, 3, 13, 63, 321, 1683, 8989, 48639, ... (OEIS A001850)

โค้ด C++

1. Recursive (Naive - Slow)

int delannoyRec(int m, int n) {
    if (m == 0 || n == 0) return 1;
    return delannoyRec(m-1, n) + delannoyRec(m, n-1) + delannoyRec(m-1, n-1);
}

2. Dynamic Programming (Bottom-up)

#include <bits/stdc++.h>
using namespace std;

int delannoyDP(int m, int n) {
    vector<vector<long long>> dp(m+1, vector<long long>(n+1, 0));
    
    for (int i = 0; i <= m; i++) dp[i][0] = 1;
    for (int j = 0; j <= n; j++) dp[0][j] = 1;
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1];
        }
    }
    return dp[m][n];
}

3. Space Optimized (1D Array)

int delannoy1D(int m, int n) {
    if (m < n) swap(m, n); // Ensure m >= n for smaller array
    vector<long long> dp(n+1, 1); // dp[0..n] = 1 initially
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            dp[j] = dp[j] + dp[j-1] + (i > 1 ? prev[j-1] : 1); // Need previous row
        }
        // Actually need to track previous row properly
    }
    // Correct 1D:
    vector<long long> prev(n+1, 1), curr(n+1);
    for (int i = 1; i <= m; i++) {
        curr[0] = 1;
        for (int j = 1; j <= n; j++) {
            curr[j] = prev[j] + curr[j-1] + prev[j-1];
        }
        swap(prev, curr);
    }
    return prev[n];
}

4. Closed Form (Combinatorial)

D(m,n) = Σ(k=0 to min(m,n)) C(m,k) * C(n,k) * 2^k
       = Σ(k) (m choose k) * (n choose k) * 2^k

long long nCr(int n, int r) {
    if (r > n) return 0;
    long long res = 1;
    for (int i = 1; i <= r; i++) {
        res = res * (n - r + i) / i;
    }
    return res;
}

long long delannoyFormula(int m, int n) {
    long long sum = 0;
    for (int k = 0; k <= min(m, n); k++) {
        sum += nCr(m, k) * nCr(n, k) * (1LL << k);
    }
    return sum;
}

โค้ดสมบูรณ์พร้อมทดสอบ

int main() {
    cout << "Delannoy Numbers:" << endl;
    for (int n = 0; n <= 6; n++) {
        cout << "D(" << n << "," << n << ") = " << delannoyDP(n, n) << endl;
    }
    
    cout << "\nD(3,3) = " << delannoyDP(3, 3) << endl; // 63
    cout << "D(5,2) = " << delannoyDP(5, 2) << endl; // 51
    cout << "D(4,4) formula = " << delannoyFormula(4, 4) << endl; // 321
    
    // Large values (need BigInt for > D(20,20))
    cout << "D(10,10) = " << delannoyDP(10, 10) << endl; // 8097453
    
    return 0;
}

Complexity

ผลลัพธ์

Delannoy Numbers:
D(0,0) = 1
D(1,1) = 3
D(2,2) = 13
D(3,3) = 63
D(4,4) = 321
D(5,5) = 1683
D(6,6) = 8989

D(3,3) = 63
D(5,2) = 51
D(4,4) formula = 321
D(10,10) = 8097453

สรุป

Delannoy Numbers นับเส้นทาง Grid ด้วย 3 ทิศทาง (E, N, NE) คำนวณได้ด้วย DP O(mn) หรือ Formula O(min(m,n)) ใช้ใน Combinatorics, Chess (King moves), Lattice Paths