Are there diagrams that show the structure of combinatorial problems?

129 Views Asked by At

According to Principles and Techniques of Combinatorics, any given counting problem can always be decomposed into sub-problems that can be solved by the addition or multiplication principles.

This becomes fairly obvious as examples increase. A problem that can be divided into disjoint cases needs to add the results of those cases, and a problem that can be composed into ordered events, needs to multiply the number of ways each event can occur.

For some of the more complicated problems, visualizing this structure becomes difficult. I'm imagining a kind of structure chart or tree diagram. I've paged through a couple of my combinatorics books, and I don't see anything resembling what I'm thinking of.

Is there an existing method of diagramming the structure of a counting problem?

1

There are 1 best solutions below

1
On

bogart 2005

Generating functions are encoding the additive and the multiplicative principles using the addition and the multiplication signs. A $G.F.$ or an $e.g.f.$ is -without doubt - a diagram and not a "function", even we may do some algebra around it. We may draw the terms vertically using an accolade, or we may draw them in a circle like they would be the molecules of a gas.

However :

  • Only addition and multiplication do not suffice. For example, when counting binary sequences that avoid 110, we have a $Lin(X+Y-X.X.Y)$ formula, where the sign $-$ has a combinatorial meaning, i.e. excluding some over-counted strings. There is also a division, something like $\frac{\{x,x,x,x,x \}}{\{x,x,x\}} = {\{x,x\}}$. There is also a composition and so on.

  • It is not necessarily easier to read/write (exponential) generating functions than just solve the problem. The diagrams get clumsy very quickly and the combinatorics glamour vanishes... Combinatorial logic does not sell well.

  • Finally, the combinatorial sum and product reveal themselves having roots in a (well said before) nasty underworld of cycles, permutations and groups of permutations.

ADD thanks Gustav for feedback; the apple-pears-bananas diagram is a quote from Kenneth Bogart, 2004, professor at Dartmouth College, whom was inspired by Polya. The idea that GF's are diagrams not just polynomials is again inspired by Polya :

enter image description here