What constitutes a proof in combinatorics?

[Stephen Tashi]

Proofs in most mathematical topics refer theorems with impressive names and use technical terminology. Proofs of combinatorial results often say something like "imagine we have n numbered balls ...". . ( If we wanted to give the proof a prehistoric sound , we could say "imagine we have n sticks of different shapes...".).

I myself have no objection to such proofs, but I'm curious if there are books where a more dignified method of proof is used.

 

[Erland]

I don't know of any such books. But I have also thought about this. It seems to me that if we want to formalize combinatorics, we must talk about cardinalities of sets of sets and functions which satisfy certain conditions.

For example: P(n,k) is the cardinality of the set of all injective functions from {1,2,...n} to subsets of itself with cardinality k. C(n.k) is the cardinality of the set of all subsets with cardinality k of {1,2,..n}.

 

[Stephen Tashi]

In a formalization of combinatorics, the frequently encountered terms "alike", "identical", "distinct" and "different" would need attention. It's slghtly amusing to hear a results about "...N identical objects...". If two objects are "identical", why aren't they the same object? The straightforward way to fix this would be to talk about the equivalence classes of some equivalence relation.

The terminology of "order" also needs fixing. That might be more complicated . There is obviously a mathematics of order relations, but what does "without regard to order" really mean? If the answer to a combinatorial problem is to be the cardinality of a set, there is the awkward fact that the bare properties of a set don't define an order to its elements. So when we need to deal with questions of order, we have to create a set whose elements portray different orders by virtue of being different elements. In a complicated problem, you might have some orders that matter (e.g. the circular order of bridge hands as North,East,South, West) some orders that don't (e.g. the order of the cards from left t right as they are held in the hands of an individual bridge player).

 

[Erland]

In a formalization of combinatorics, the frequently encountered terms "alike", "identical", "distinct" and "different" would need attention. It's slghtly amusing to hear a results about "...N identical objects...". If two objects are "identical", why aren't they the same object? The straightforward way to fix this would be to talk about the equivalence classes of some equivalence relation.

I agree.

The terminology of "order" also needs fixing. That might be more complicated . There is obviously a mathematics of order relations, but what does "without regard to order" really mean? If the answer to a combinatorial problem is to be the cardinality of a set, there is the awkward fact that the bare properties of a set don't define an order to its elements. So when we need to deal with questions of order, we have to create a set whose elements portray different orders by virtue of being different elements. In a complicated problem, you might have some orders that matter (e.g. the circular order of bridge hands as North,East,South, West) some orders that don't (e.g. the order of the cards from left t right as they are held in the hands of an individual bridge player).

The easiest way, I think, is to talk about functions f: {1,2,...k} --> M, where M is the set from which k elements should be selected. Every such function represents a selection of k ordered elements from M. If we want some weaker kind of ordering, such as the circular one you mentioned, we can try to define appropriate equivalence classes of such functions.

 

[Erland]

I would like to give you a challenge:

The Product Rule or Multiplication Principle is a cornerstone in combinatorics. One can say that it is the basic principle upon most of at least elementary combinatorics rests. Looking it up at Wikipedia and other sites, I find that it is not stated there in full generality, so let me state it in the most general way I know of:

If a task should be performed in n steps, and there are numbers m₁, m₂, ... m_n, such that for each k (1<=k<=n), the k:th step can be performed in m_k ways, then the entire task can be performed in m₁m₂...m_n ways.

Important to notice here is that the ways available for the k:th step may very well (but need not) depend of how the previuos steps were performed, but the number of such available ways is always m_k, independently of the previous steps.
For example, if we are to select m distinct elements from set with n elements, with respect to order, we first select the first element, then the second, etc. When we select the kth element, there are n-k+1 elements not already selected to choose from, but exactly which these elements are depends upon which elements are already selected. Nevertheless, the number of elements, n-k+1, to select from, is independent of which elements are already selected. So in this case: m_k=n-k+1.

The challenge for you is: Formulate and prove the product rule (as informally stated above) rigorously.

For myself, I have some ideas of how to do that, but it will be quite complicated...

 

[Stephen Tashi]

I'll consider 2 steps instead of n. :)

We should invent some terminology for a finite set of consecutive integers whose least integer member is 1. For the time being, I'll call such a set a "selection set". Let $D_k$ and $R_k\$ $k = 1,2$ be selection sets. Let $M_k$ be the set consisting of the 1-to-1 mappings of $D_k$ into $R_k$.

There is probably standard terminology to define the set of maps $M_1 \times M_2$ from the cartesian product $D_1 \times D_2$ into $R_1 \times R_2$ such that the maps use "component by component" operations. Perhaps this can be expressed in category theory. If we use this terminology to properly specify $M_1 \times M_2$ then the result we wish to prove is $Card( M_1 \times M_2) = Card(M_1) \times Card(M_2)$.

How's that for a start?

 

[Erland]

Hmm, your approach is not sufficiently general. Even if there are only two steps, the second step may depend upon the first, so that $R_2$ is not a fixed set.

Take for example the following simple problem: An association which has 10 members shall appoint a chairperson and a secretary. In how many ways can this be done?

The answer is: 10 x 9 = 90 ways. This an application of the multiplication principle / procuct rule, because there are 10 possible choices for the chairperson, and, once the chairperson is appointed, there are 9 persons left which can be appointed to sectretary. So, with your terminomogy, $R_1$ would be the 10-element set of all the members of the association. $R_2$ would be the set of the set of 9 members which were not appointed to chairperson. But this set is of course not fixed, it is dependent upon which person was appointed to chairperson.

So the set $R_2$ is not fixed, but the cardinality of $R_2$ is: there are always 9 persons who were not appointed to chairperson and therefore can be appointed to sectretary. Therefore, the multiplication principle / product rule is appliciable in this case.

I will return with my own suggestion of how to formulate this principle formally...

 

[Stephen Tashi]

But this set is of course not fixed, it is dependent upon which person was appointed to chairperson.

How mathematics is applied is subjective. The integers in R2 can represent "the second set of choices, arbitrarily labeled" rather than "the second set of persons". However, I agree with the spirit of your objection from the perspective of computation combinatorics - i.e. from the viewpoint that our objective will be to specify the set of possibilities in a manner that elements can be unambiguously identified as a particular "solutions" to some problem.

The goal of counting the number of solutions is different than the goal of listing all the solutions. For me, it's easy to think of how to write a computer program to list the solutions of the problem you gave, but not easy to say what I'm doing in terms of pure mathematics. I'll be interested to see your approach.

 

[Erland]

I would formulate the Multiplication Principle / Product Rule (in the sense given in Post #5 above) formally like this (using your definition of $D_k$, with $D_0=$ ∅):

Let $M$ be a set, let $S$ be a set of functions $f: D_n\to M$, and let $p: D_n\to ℕ$, for some $n\in ℕ$.
Assume that for every $k$: $(1\le k\le n)$, and every function $g: D_{k-1}\to M$ which is the restriction of some function(s) $f\in S$, the set $T_g$ of all functions $h: D_k\to M$ which are both extensions of $g$ and restrictions of functions in $S$ has cardinality $p(k)$.

Then, $S$ has cardinality $p(1)\,p(2)\,\dots\, p(n)$.

This is then quite easy to prove by induction.

This formulation might be quite hard to grasp, but this probably is in nature's sake.

 

[Stephen Tashi]

and let $p: D_n\to ℕ$, for some $n\in ℕ$.

I don't understand what the notation says about $p$. Is it a function?

 

[Erland]

I don't understand what the notation says about $p$. Is it a function?

Yes it is a function. I could equally well (but perhaps a little bit less formal) have talked about a finite sequence $a_1,\, a_2,\,\dots, a_n$ of positive integers.

Btw, we must change the assumptions slightly: The codomain of p must be Z₊ (positive integers) instead of N, and S must be nonempty.

 

[Stephen Tashi]

I don't understand that definition yet. When it comes to the restriction of functions, it isn't clear to me which functions are "given".

An intuitive (to a mathematican) approach to the problem of post #5 would be to first define the "free selection set" that gives all ways of doing things without any constraints. (i.e. picking a sequence of any finite number things from n things "with replacement"). Next define various constrained problems (like picking 3 of N people for a committee) as subsets of the free selection set.

I'm confident that a "free selection" set can be defined. I don't yet see a useful way to define "constraints" in a general way. You are incorporating constraints in you definition, but I don't understand how.

A "completely general" constraint says that if you have made some given initial selections, your next selection is restricted to a certain set of functions. I think the most general specification of "initial selections" would consider the order of the selections as well as the "result" of the selections. A general constraint "at step k" is a function from the set of "initial selections" prior to step k to a subset of the "free selection functions" on step k.

I see why there must be struggle with restriction and extension. The thought is that the total selection process is a composition of functions. To compose the functions, the range of one function must be a subset of the domain of the next function that operates. So a constraint must be a mapping from the set of "initial selections" (which I have not defined yet) to the "free selection functions" on step k such that..." and we must have some words that say the allowed functions on step k can be applied to the ranges of the "initial selection" function that maps to them.

 

[Erland]

To clarify my formalism, let me give an example, slightly more complicated then the one with the chairperson and the secretary. Again, assume that 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.

In how many ways can the board be composed?

This can be viewed as a task to be performed in 4 steps:

1. Elect a chairperson.
2. Elect a vice chairperson.
3. Elect a sectretary.
4. Elect a treasurer.

With my formalism in this case, $n=4$ = the number of steps (selections), $M$ = the set of members of the association. Each possible board is represented as a function $f: D_4\to M$, with $f(1)$ = the chairperson, $f(2)$ = the vice chairperson, $f(3)$ = the secretary, and $f(4)$ = the treasurer, for the particular possible board represented by $f$. $S$ is the set of all possible boards, and the question above is equivalent to asking what the cardinality of $S$ is.
For each $k$ ($1\le k\le 4$), $p(k)$ = the number of persons which can be elected to the $k$:th position, after the first $k-1$ positions are filled. Thus:

$p(1)=10$ (anyone of the 10 members),
$p(2)=5$ (the 5 women if the elected chairperson is a man, the 5 men if the elected chairperson is a woman),
$p(3)=8$ (anyone of the 8 persons elected to neither chairperson nor vice chairperson),
$p(4)=7$ (anyone of the 7 persons not elected to any of first three positions).

To see how this with restrictions and extensions works, suppose, for example, that the chairperson and vice chairpersons are already elected, let's say their names are Jack and Jane, but not the remaining two positions. This partial board with Jack and Jane is represented by a function $g: D_2 \to M$. It can be completed to a full board in 8*7=56 ways, represented by 56 functions $f\in S$. $g$ is then a restriction of each of these 56 functions.
In completing this Jack+Jane partial board, a secretary is first to be elected. When a sectretary is elected, we get a larger partial board, which is represented by a function $h: D_3\to M$ (Jack+Jane+some secretary). Any such function $h$ is an extension of $g$, and a restriction of 7 functions $f \in S$, representing full boards containing Jack, Jane, the same secretary as in the $h$-case, and some treasurer. There are $p(3)=8$ such functions $h$, one for each possible secretary which can be added to the Jack-Jane partial board. $T_g$ is the set of these 8 functions in this case (for which $k=3$), so the cardinality of $T_g$ is $p(3)=8$.

The claim is then, in this case, that the caridinality of $S$, i.e. the number of possible boards, is $p(1)\,p(2)\,p(3)\,p(4)=10*5*8*7=2800$.

I hope it is a little more clear now...

 

[Erland]

$S$ is the set of all possible boards

Clarification: $S$ is the set of all functions $f: D_4\to M$ which represent (all) possible boards.

 

[Stephen Tashi]

$S$ is the set of all possible boards

I would be better to say that $S$ is the set of functions that pick feasible boards.

To see how this with restrictions and extensions works, suppose, for example, that the chairperson and vice chairpersons are already elected, let's say their names are Jack and Jane, but not the remaining two positions. This partial board with Jack and Jane is represented by a function $g: D_2 \to M$. It can be completed to a full board in 8*7=56 ways, represented by 56 functions $f\in S$. $g$ is then a restriction of each of these 56 functions.

Ok, I understand that a given function that represents picking the first $j$ items can be viewed as a restriction of certain functions that pick $k > j$ items. To justify counting functions by multiplication depends on a statement about the functions in $S$ - something like: There exists an integer $p$ such that for each function $g$ that picks the first $j$ items there exists a set $R$ containing exactly $p$ functions in $S$ that are extensions of $g$

Your method "starts" with the set $S$ of functions that make the possible selections -i.e. we imagine we have the answer to the problem at hand - whatever that problem may be. We study how the elements of $S$ can be expressed in a tree structure. A node in the tree represents a function defined on some subset of the domain of the functions in $S$. The branches of the node lead to nodes representing functions that extend that function to larger subsets of the domain. So all combinatorial problems amount to counting the final ("leaf") nodes by using facts about the branching structure.