For typical #P-hard problems on graphs, we have recently proposed an approach to solve
those problems of moderate size rigorously by means of the binary decision diagram, BDD
[12, 13]. This paper extends this approach to counting problems on linear matroids, graphic
arrangements and partial orders, most of which are already known to be #P-hard, with using
geometric properties. Efficient algorithms are provided to the following problems.
ffl Computing the BDD representing all bases of a binary or ternary matroid in an output-
size sensitive manner; by using this BDD, the Tutte polynomial of the matroid and the
weight enumeration of an (n; k) linear code over GF(2) and GF(3) can be computed in
time proportional to the size of the BDD.
ffl Computing the Tutte polynomial of a linear matroid over the reals via the arrangement
construction algorithm in computational geometry.
ffl Computing the number of acyclic orientations of a graph, i.e., the number of cells in the
corresponding graphic arrangement, and further the number of its lower-dimensional faces.
ffl Computing the number of ideals in a partially ordered set, i.e., the number of some faces
of the corresponding cone in the graphic arrangement