Combinatorial and noncommutative list-processing and associated graphs

Recently the authors have proposed a list-processing approach to the modeling of algebraic quantum field theory methods in quantum mechanics in which the noncommutative algebra of quantum-mechanical operators is emulated by lists. The processing produces reordered sequences of elements of a ring with a unit commutator and generates dynamic structures which, for some initial arrangements, correspond to partially ordered graphs characterized by recurrence relations and combinatorial identities. Likewise, in another list-processing application to physical problems, a simulation of Feynman diagrams hinged on predominantly combinatorial aspects and demanded explicit generation of certain combinatorial objects. This motivated an investigation into the combinatorial nature of noncommutative list-processing and of recursive algorithms for explicit construction of combinatorial lists, which we now present. The emphasis is also placed on the consideration of associated graphs and the graph-theoretic origin of the appearance of recurrence relations in the reordering theorems of the noncommutative algebra.