---
tag: ZD4Z8Z1NJ2
kind: statement
role: proposition
name: Talaska's formula
sources:
  - wikipedia: en:31847498@r1371973165
    locator: Lindström–Gessel–Viennot lemma, section Generalizations > Talaska's formula
    note: adopted
    mention: wikipedia://en/31847498#6O99
    sections: [Statement]
inventory: [8559FZV67G]
---

## Statement

The acyclicity of *G* is an essential assumption in the Lindström–Gessel–Viennot lemma; it guarantees (in reasonable situations) that the sums $e(a, b)$ are well-defined, and it advects into the proof (if *G* is not acyclic, then *f* might transform a self-intersection of a path into an intersection of two distinct paths, which breaks the argument that *f* is an involution). Nevertheless, Kelli Talaska's 2012 paper establishes a formula generalizing the lemma to arbitrary digraphs. The sums $e(a, b)$ are replaced by [[formal power series|033WGN00BF]], and the sum over nonintersecting path tuples now becomes a sum over collections of nonintersecting and non-self-intersecting paths and cycles, divided by a sum over collections of nonintersecting cycles. The reader is referred to Talaska's paper for details.