Generalization of combinatorial generating functions?

[Stephen Tashi]

Generating functions defined in terms of algebraic operations on real valued variables are used to enumerate answers to certain combinatorial problems. ( This morning, the exposition http://www.cs.cornell.edu/courses/cs485/2006sp/lecture notes/lecture11.pdf is the first of many hits on the subject.)

Is there a useful generalization of the idea of generating functions that would employ operations on other structures? - matrices, for example.

 

[Stephen Tashi]

In anticipation of the automated courtesy bump, I'll elaborate.

For example, take this scenario from another thread:

we have an association with 10 members, but in this case 5 men and 5 women. The association shall elect a board with 4 members, one chairperson, one vice chairperson, one secretary, and one treasurer. According to the statutes, the chairperson and the vice chairperson must have different sexes, and no person can uphold more than one of these four positions. There are no other restrictions of how the board can be composed

To enumerate the possible boards, suppose we think of column vectors with 3 entires. The entries aren't numbers, they are just symbols. An entry like \begin{pmatrix} x_2\\ M\\C \end{pmatrix}
has the interpretation that x_2 denotes particular individual, the M denotes he is male. The C indicates he is selected as the chairperson.

We try to represent the boards as terms in the symbolic multiplication (vector entry by vector entry):

\big( \begin{pmatrix} x_1 \\ M\\ C \end{pmatrix} + ...+ \begin{pmatrix} x_{10} \\ F \\ C \end{pmatrix} \big)
\big( \begin{pmatrix} x_1 \\ M\\ V \end{pmatrix} + ...+ \begin{pmatrix} x_{10} \\ F \\ V \end{pmatrix} \big)
\big( \begin{pmatrix} x_1 \\ M\\ S \end{pmatrix} + ...+ \begin{pmatrix} x_{10} \\ F \\ S \end{pmatrix} \big)
\big( \begin{pmatrix} x_1 \\ M\\ T \end{pmatrix} + ...+ \begin{pmatrix} x_{10} \\ F \\ T \end{pmatrix} \big)

But this multiplication produces terms that represent illegal selections such as
\begin{pmatrix} x_1 x_5 x_6 x_6 \\ M M F F \\ C V S T\end{pmatrix}
which has the flaws that member x_6 holds two offices and the chairperson (C) and vice chairperson (V) have the same gender.

To rectify this, we could stipulate that the symbols come from some algebraic structure that makes the illegal combinations equal to a kind of zero ( or "unity" or anything that makes them conveniently distinguishable as illegal). For example, we could say that x_i^2 = 0 and
\begin{pmatrix} x_i x_j \\ M^2 \\ CV \end{pmatrix} = \begin{pmatrix} x_i x_j \\ F^2 \\ CV \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}
and further any column vector with a 0 entry is equivalent to a column vector of all zeroes.

Rather than such ad hoc stipulations, it would be nice to find a construction using well known mathematical structures where the stipulations are properties of the structures.

 

[mfb]

If you represent the genders as booleans, (chair) XOR (vice) is true exactly if the gender condition is satisfied, else it is false.
You can also represent them as 1 and 0 in the field of 2 elements, and require that their addition gives the result of 1.

Is that in the right direction?

 

[Stephen Tashi]

If you represent the genders as booleans, (chair) XOR (vice) is true exactly if the gender condition is satisfied, else it is false.
You can also represent them as 1 and 0 in the field of 2 elements, and require that their addition gives the result of 1.

Is that in the right direction?

Yes, that's the right general direction. I'm curious if making the symbols elements of a structure (boolean algebra, ring, group etc.) can enumerate various combinatorial problems. (I don't know if column vectors is the right way to go.)

Thinking in a very general way, a combinatorial problem can be regarded as a directed tree where each not represents a choice. In textbook combinatorial problems you have general rules about the nodes that enforce constraints on the structure of the graph (e.g. the chairperson and vice chairperson can't be the same gener). However you could conceive of a combinatorial problem that was capricious - as if the permissible choices were decreed by some scatterbrained person who followed no generalities (e.g. "If we pick willy as chair person then Agnes won't do as vicechair. You can pick Sally or Flora. But if pick Flora then we won't need a secretary and treasurer because Flora is so capable".)

It tempting to think that if you have a combinatorial problem with an orderly set of rules that you will be able to find a way to map each path down its tree diagram to a string of symbols in some sort of symbolic calculation.

 

[mfb]

Well, you can always make up functions that are zero exactly if Willy is chair and Agnes is vice chair (and so on), just by defining them that way.