The LGV Lemma

Introduction

The Lindström–Gessel–Viennot lemma, or LGV lemma, can be used for problems such as counting vertex-disjoint paths in directed acyclic graphs.

Prerequisites: the basic material in Graph-theoretic concepts, Matrices, and Gaussian Elimination for Determinants.

The LGV lemma applies only to directed acyclic graphs.

Definition

$\omega(P)$ denotes the product of the edge weights along path $P$. (For path counting, all edge weights can be set to $1$.) (In fact, edge weights may be generating functions.)

$e(u, v)$ denotes the sum of $u$ over every path $v$ from $P$ to $\omega(P)$, that is, $e(u, v)=\sum\limits_{P:u\rightarrow v}\omega(P)$.

The source set $A$ is a subset of the vertex set of the directed acyclic graph, with size $n$.

The target set $B$ is also a subset of the vertex set of the directed acyclic graph, also with size $n$.

A vertex-disjoint path family $A\rightarrow B$ from $S$: $S_i$ is a path from $A_i$ to $B_{\sigma(S)_i}$, where $\sigma(S)$ is a permutation; for any $i\ne j$, $S_i$ and $S_j$ have no common vertex.

$t(\sigma)$ denotes the number of inversions in permutation $\sigma$.

Lemma

Here, $\sum\limits_{S:A\rightarrow B}$ denotes the sum over every vertex-disjoint $A\rightarrow B$ path family $S$ satisfying the requirements above.

Proof

By the definition of a determinant,

Observe that $\prod\limits_{i=1}^n \sum\limits_{P:a_i\to b_{\sigma(i)}} \omega(P)$ is exactly the sum of $A$ over all path families $B$ from $\sigma$ to $P$ whose permutation is $\omega(P)$.

Here, $P$ is an arbitrary path family.

Let $U$ be a vertex-disjoint path family and $V$ an intersecting path family.

Suppose $P$ contains an intersecting pair $P_i:a_1 \to u \to b_1,P_j:a_2 \to u \to b_2$. There is necessarily a corresponding intersecting pair $P_i'=a_1\to u\to b_2,P_j'=a_2\to u\to b_1$; all other paths in $P'$ are the same as in $P$. Therefore $\omega(P)=\omega(P'),t(P)=t(P')\pm 1$.

Thus $\sum\limits_{V:A\to B}(-1)^{t(\sigma)}\prod\limits_{i=1}^n \omega(V_i)=0$.

Consequently, $\det(M)=\sum\limits_{U:A\to B}(-1)^{t(U)}\prod\limits_{i=1}^n \omega(U_i)$.

This proves the lemma.¹

Examples

This is a direct application of the LGV lemma. Consider all valid paths. Every path from $(1,1)$ must pass through $A=\{(1,2), (2,1)\}$, and every path reaching the destination must pass through $B=\{(n-1, m), (n, m-1)\}$. Thus $A, B$ can be selected immediately. Applying the LGV lemma gives:

Here, $f(a, b)$ is the number of paths from $a\rightarrow b$ in the graph. The path-counting problem with blocked cells can be solved by an $O(nm)$ DP, so $f$ is easy to obtain. The final complexity is $O(nm)$.

#include <cstring>
#include <iostream>
#include <string>

using namespace std;

using ll = long long;
constexpr int MOD = 1e9 + 7;
constexpr int SIZE = 3010;

string board[SIZE];
int dp[SIZE][SIZE];

int f(int x1, int y1, int x2, int y2) {
  memset(dp, 0, sizeof dp);

  dp[x1][y1] = board[x1][y1] == '.';
  for (int i = 1; i <= x2; i++) {
    for (int j = 1; j <= y2; j++) {
      if (board[i][j] == '#') {
        continue;
      }
      dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
      dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD;
    }
  }
  return dp[x2][y2] % MOD;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;

  for (int i = 1; i <= n; i++) {
    cin >> board[i];
    board[i] = " " + board[i];
  }

  ll f11 = f(1, 2, n - 1, m);
  ll f12 = f(1, 2, n, m - 1);
  ll f21 = f(2, 1, n - 1, m);
  ll f22 = f(2, 1, n, m - 1);

  ll ans = ((f11 * f22) % MOD - (f12 * f21) % MOD + MOD) % MOD;
  cout << ans << '\n';

  return 0;
}

If the paths are disjoint, they must connect $a_i$ to $b_i$, so in the LGV lemma we necessarily have $\sigma(S)_i=i$ and need not consider signs. Set every edge weight to $1$ and apply the lemma directly.

The number of paths from $(1, a_i)$ to $(n, b_j)$ is the number of ways to choose $n-1+b_j-a_i$ downward steps from $n-1$ steps, so $e(A_i, B_j)=\binom{n-1+b_j-a_i}{n-1}$.

The determinant can be computed with Gaussian elimination.

The complexity is $O(n+k(k^2 + \log p))$, where $\log p$ is the complexity of computing a modular inverse.

#include <algorithm>
#include <iostream>

using ll = long long;

constexpr int K = 105;
constexpr int N = 100005;
constexpr int mod = 1e9 + 7;

int T, n, k, a[K], b[K], fact[N << 1], m[K][K];

int qpow(int x, int y) {
  int out = 1;
  while (y) {
    if (y & 1) out = (ll)out * x % mod;
    x = (ll)x * x % mod;
    y >>= 1;
  }
  return out;
}

int c(int x, int y) {
  return (ll)fact[x] * qpow(fact[y], mod - 2) % mod *
         qpow(fact[x - y], mod - 2) % mod;
}

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  fact[0] = 1;
  for (int i = 1; i < N * 2; ++i) fact[i] = (ll)fact[i - 1] * i % mod;

  cin >> T;

  while (T--) {
    cin >> n >> k;

    for (int i = 1; i <= k; ++i) cin >> a[i];
    for (int i = 1; i <= k; ++i) cin >> b[i];

    for (int i = 1; i <= k; ++i) {
      for (int j = 1; j <= k; ++j) {
        if (a[i] <= b[j])
          m[i][j] = c(b[j] - a[i] + n - 1, n - 1);
        else
          m[i][j] = 0;
      }
    }

    for (int i = 1; i < k; ++i) {
      if (!m[i][i]) {
        for (int j = i + 1; j <= k; ++j) {
          if (m[j][i]) {
            std::swap(m[i], m[j]);
            break;
          }
        }
      }
      if (!m[i][i]) continue;
      int inv = qpow(m[i][i], mod - 2);
      for (int j = i + 1; j <= k; ++j) {
        if (!m[j][i]) continue;
        int mul = (ll)m[j][i] * inv % mod;
        for (int p = i; p <= k; ++p) {
          m[j][p] = (m[j][p] - (ll)m[i][p] * mul % mod + mod) % mod;
        }
      }
    }

    int ans = 1;

    for (int i = 1; i <= k; ++i) ans = (ll)ans * m[i][i] % mod;

    cout << ans << '\n';
  }

  return 0;
}

References