Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Generalization of combinatorial generating functions?

  1. Dec 31, 2014 #1

    Stephen Tashi

    User Avatar
    Science Advisor

    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.
     
  2. jcsd
  3. Jan 3, 2015 #2

    Stephen Tashi

    User Avatar
    Science Advisor

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

    For example, take this scenario from another thread:
    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 [itex] \begin{pmatrix} x_2\\ M\\C \end{pmatrix} [/itex]
    has the interpretation that [itex] x_2 [/itex] denotes particular individual, the [itex] M [/itex] denotes he is male. The [itex] C [/itex] indicates he is selected as the chairperson.

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

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

    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 [itex] x_i^2 = 0 [/itex] and
    [itex] \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} [/itex]
    and further any column vector with a [itex] 0 [/itex] 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.
     
  4. Jan 3, 2015 #3

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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?
     
  5. Jan 4, 2015 #4

    Stephen Tashi

    User Avatar
    Science Advisor

    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.
     
  6. Jan 4, 2015 #5

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Generalization of combinatorial generating functions?
  1. Generating function (Replies: 2)

  2. Generating Functions! (Replies: 7)

  3. Generating function (Replies: 8)

  4. Generating function (Replies: 6)

Loading...