Generalization of combinatorial generating functions?

  • Thread starter Stephen Tashi
  • Start date
  • Tags
    Functions
In summary, the exposition from this morning is the first of many hits on the subject of generating functions and enumerating answers to combinatorial problems. The idea is to employ algebraic operations on real valued variables to generate strings of symbols that represent the answers to the problem. There is a general direction in the right direction, but more work is needed to fully flesh out the idea.
  • #1
Stephen Tashi
Science Advisor
7,861
1,598
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.
 
Physics news on Phys.org
  • #2
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 [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.
 
  • #3
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?
 
  • #4
mfb said:
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.
 
  • #5
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.
 

1. What is a combinatorial generating function?

A combinatorial generating function is a mathematical tool used in combinatorics, a branch of mathematics that deals with counting and arranging objects. It is a formal power series that represents a sequence of numbers, where each term in the series represents the number of ways to choose or arrange a certain number of objects.

2. How does generalization of combinatorial generating functions work?

Generalization of combinatorial generating functions involves extending the concept of combinatorial generating functions to more complex situations. This can be achieved by introducing new parameters or variables into the generating function, allowing for the representation of more diverse sequences and patterns.

3. What are some applications of generalization of combinatorial generating functions?

Generalization of combinatorial generating functions has various applications in fields such as computer science, physics, and biology. It can be used to solve problems related to graph theory, cryptography, and statistical mechanics, among others.

4. What are the benefits of using generalization of combinatorial generating functions?

Generalization of combinatorial generating functions allows for a more flexible and comprehensive approach to solving combinatorial problems. It can also provide insights and connections between seemingly unrelated problems, leading to new discoveries and advancements in various fields of study.

5. Are there any limitations to generalization of combinatorial generating functions?

While generalization of combinatorial generating functions is a powerful tool, it may not always provide an exact solution to a problem. In some cases, the resulting series may not have a closed form expression, making it difficult to calculate specific values. Additionally, generalization may also introduce more complexity and make the problem more challenging to solve.

Similar threads

  • Special and General Relativity
Replies
4
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
  • Programming and Computer Science
Replies
1
Views
1K
  • Beyond the Standard Models
Replies
3
Views
1K
Replies
2
Views
236
Replies
2
Views
2K
  • Linear and Abstract Algebra
Replies
2
Views
4K
  • STEM Academic Advising
Replies
11
Views
652
  • STEM Academic Advising
Replies
7
Views
1K
  • Sticky
  • Topology and Analysis
Replies
9
Views
5K
Back
Top