Combinatorial Structures Flashcards
What is a combinatorial class?
It is a finite or denumerable set. On this set, a size function is defined. It has two properties.
(1) the size of any element is non-negative.
(2) the number of elements of any given size is finite.
What is the counting sequence of a combinatorial class?
It is the sequence of integers that counts of the number of objects of a given size within the combinatorial class. Notationally (card(A_n)) subscript n>=0.
When are two combinatorial classes A, B said to be isomorphic?
IFF there counting sequences are identical. This means there exists a bijection from A to B that preserves the size function.
What is the definition of an admissible construction?
So we have a construction, say phi, or m arity. So it takes m arguments. Suppose these arguments are combinatorial classes. Then the construction phi is admissible if and only if the counting sequence of the new combinatorial class defined by phi depends solely on the counting sequences of its m arguments.