## Cdmm_ugm2013.nb

Making simple proofs simplerPietro Codara, Ottavio D’Antona, Francesco Marigo, Corrado Monti
Dipartimento di Informatica, Università degli Studi di Milano
An open partition p [Cod09a, Cod09b] of a tree

*T *is a partition of the vertices of

*T * with the property that, foreach block

*B * of p, the upset of

*B * is a union of blocks of p. This paper deals with the number, NP(

*n*), of openpartitions of the tree,

*Vn*, made of two chains with

*n* points each, that share the root. We prove that the numberof such partitions is given by the formula
1, 5, 26, 130, 628, 2954, 13612, 61716, .

On the other hand, from the On-Line Encyclopedia of Integer Sequences [OEIS] we learn that such a numericalsequence is generated by the formula
In this note we exploit Mathematica to explain the not so simple derivation of the following novel identity, thatwill prove the equivalence between the above formulas:
Min

*k*,

*j* =

*n *+ 1 22

*n*-3 -

*k *-

*h*

*n *- 1
In so doing we show that visual enumeration can make simple proofs simpler!
In our research we often deal with combinatorial problems, sometimes quite complex, on ordered structures. Recall that a partially ordered set (poset, for short) is a set together with a reflexive, transitive, and antisymmet-ric binary relation (usually denoted by b) on the elements of the set. Posets are usually represented as a Hasse diagram, as in [Cod10b]; that is, the bigger elements (according to b) are drawn on the top, and line starting in the element x connects it to all its direct successors (any z for which zbx but there are not y such that zbybx). If zby and ybx, nodes are drawn in this order, from bottom to top, in the Hasse diagram. Uncomparable nodes (

*x,y *such that neither

*x*b

*y *nor

*y*b

*x*) are not connected by a bottom-to-top path, neither with nor without nodes in the middle.

**2 ** * cdmm_ugm2013.nb*
Our attention is mainly addressed to a certain category of posets: those composed by two chains that share the same root. The Hasse diagram for this kind of structures is this:

**catL Join1,Range2, n21,2;**

catR Range1, n21,2;

nodes UnioncatL,catR;

poset MakeGraphnodes,IsEdge;

PosetPlotposet
This will allow us to call a structure of this kind a

**V-Poset**.

Now, we are interested in partitions of a poset: namely, a

**partition** of a poset is a division of its nodes into non-

overlapping and non-empty

**blocks **whose union is the set of nodes. There are many ways to define classes of

possible partitions on posets that are useful to conserve some property about the relationship that defines the

poset. In particular, we will use

**open partitions **[Cod09a, Cod09b]: an open partition of a Poset is, informally

speaking, a partition where, for any block X, every node that is under a node included in X is part of a block

where all the nodes are under an element of X.

We can formally describe this property using the notion of filter. A filter of an element x of a Poset (P,b) is a set,

denoted as Æx, of all the elements yœP such that ybx. We can now associate to a partition p another relation-

ship ‚ such that B‚C for B,C œ p if $ b œ B and $ c œ C for which bbc. Now, if p is an open partition, for each of

its blocks B exists a collection kŒp of blocks of p such that

This can be easily decribed in this way: the filter of a block does not “break” any other block.

Partitions will be drawn in this work automatically by a simple Mathematica package we developed, by means of colors: elements in the same block will have same color; those in different blocks will have different colors. We remind the reader that, since a block of a partition is defined only by its member, the color is not important: given a partition, and swapping all the colors of its blocks, we will have exactly the same partition; no matter what the color of its blocks are, that will not be a different partition.

Now let us see how an open partition of a V-poset look like:

**aPartition1,2,3, 4, 5;**

PosetPlotposet, aPartition
We can see how under the red block we have the blue one, but no node of the other blocks; in the same way, under the yellow block we have the green one and the blue one, but no other elements for the other blocks.

*cdmm_ugm2013.nb * **3**
3. How many open partitions could we have?
We are interested in the following combinatorial problem: given a V-poset composed by two chains of

*n *ele-ments each, how many open partitions could we have? Is there a closed form? Can this be expressed withoutexplicit summations?To count these kind of partitions, it is convenient to define them in a simpler way. Indeed, we can note that theyare completely defined by:
a number of blocks to join, at the bottom, between the two partitions (we necessarily have to join the bottom
block of both, because they share the root node)

**Note:** to see the Manipulating boxes,

**please execute all Initial-**
**ization Cells**:

MenuEvalutationEvaluate Initialization Cells
This provides naturally a counting of the partitions on the V-poset. All we need to know is that the number of
open partitions on a chain of

*n *elements in

*k *block is n 1 (to briefly prove this fact, just think as putting k-1
“separators” on the edges of the chain). Therefore, we can count all the possibile partitions on each chain with

*k *and

* j *blocks respectively, and we know that they can be joined in

* Min{ k , j } *different ways. Calling

*n *the num-ber of nodes in each chain, this gives us the following formula:

**n**
**n**
**n ****- 1**
**n ****- 1**
**NP***n*** = **
**Min***k***, ***j*****
**k ****- 1**
**j ****- 1**
**k****=1 ***j***=1**
With

*Mathematica*, we can illustrate the meaning of this:

*n * 1

*n * 1 Min

*k*,

*j*

**4 ** * cdmm_ugm2013.nb*
This first statement is simple but not exactly trivial. It can be proved with algebra; we also tried to do it symboli-cally with

*Mathematica *but effort was of little avail. First,
NP(n) =

*n *

*n *Min

*k*,

*h*ÿ
since every couple

*k,h *is counted exactly Min[

*k,h*] times if the index of the inner summation starts with

*j*.

Now, let us move the first binomial coefficient out:

*cdmm_ugm2013.nb * **5**
Nevertheless, we know the meaning of the first formula, and we have visualized it. We could prove the equiva-lence in a combinatorial way, just by understanding why the second formula counts exactly the same objects counted by the first one. Proving the fact that the two expressions count the same objects is the same as proving that they are equal. With

*Mathematica* we can visualize these summatories and show explicitly how the objects that are counted are, again, all the open partitions of a V-poset:

**6 ** * cdmm_ugm2013.nb*
NP

*n* = 2

*n*-1 *

*n *+ 1 2

*n*-2 -

*k *-

*h*

*n *- 1
This proof is not simple in algebraic ways.

We start from the equation

*m i n*

*h*,

*k*

*n *- 1
In order to give another expression to

*NP(n)*, we use the following lemma:

**Lemma 1.**

Let

*ai*,

*bi* with

*i=1,.,n *be two symmetric sequences of positive real numbers, that is

*ai* =

*an*+1-

*i* and

*bi* =

*bn*+1-

*i*.

*cdmm_ugm2013.nb * **7**
*i*=1

*i* and

*B *

*i*=1

*i* be the sums of the two sequences. Then

*m i n*

*h*,

*k*

*a*
*m i n*

*h*,

*k*

*a*
We can change the indexes into

* h *Ø

*n *+ 1 -

*h and k *Ø

*n *+ 1 -

*k *, and, because of the simmetry of the two sequences, we have

*n *+ 1 -

*m a x*

*h*,

*k*

*a*
Summing the two expressions for

*X*, we have

*n *+ 1 +

*m i n*

*h*,

*k* -

*m a x*

*h*,

*k*

*a*

*n *+ 1 -

*k *-

*h *

*a*

*n *+ 1

*A B *- 2

*n*
*X *

*n*+1

*A B *-

*n*
This result is also very similar to the one proved by Codara in [Cod10a]. Now we apply this lemma to our equa-tion, with the sequences

*m i n*

*h*,

*k*

*n *- 1

*NP*

*n*

*n *+ 1 22

*n*-3 -

*n*
Again, to prove the statement in a combinatorial way, we just have to show that it counts all the open partitions of a V-poset. This time, though, we do not have directly a summation, but the formula is composed by a differ-ence instead. So, we will recognize what every part of this difference means for our partitions.

The first part — the minuend — is a product. A product, in combinatorics, very often means a cartesian product between two sets: this is the case. In fact, this product can be seen as the product between these two sets. The

**8 ** * cdmm_ugm2013.nb*
following, of 2

*n*-1elements, is the set of all the open partitions of the left chain of the V-poset:
The equivalence between the sommation of binomials with the same top number and the corrispondent power of 2 is indeed well known.

The second set of the cartesian product is made by all the pairings of an open partition on the right chain, and a number that can be seen as a join level. This number will range from 1 to the number of blocks defined by the partition on this chain. So we have these objects:

*cdmm_ugm2013.nb * **9**
The trick to understand the subtraction of our formula is that not all the pairings between these two sets are legal. What is counted by the subtrahend of the formula are extacly these uncorrect pairings. Let us see this directly:

*k *

*h*

*n * 1

*n * 1

**10 ** * cdmm_ugm2013.nb*
So our formula can be seen as a subtraction of elements from a product, and can be represented in this way:

**n k****-1**
**2***n***-1 * ***n ***+ 1 2***n***-2 - ***k ***- ***h*** ***n ***- 1 ***n ***- 1 **
**h ****- 1**
**k ****- 1**
**k****=1 ***h***=1**
*cdmm_ugm2013.nb * **11**
**join 1**
**join 1**
**join 2**
**join 1**
**join 2**
**join 1**
**join 2**
**join 3**
Proving that the above formula counts all the elements of the first one we have indirectly proved the equation itself, without all the algebraic machinery otherwise involved.

Moreover, thanks to a result by Hirchhorn [Hirsch96] that says that

*n *

*k*-1

*k *-

*h*

*n *- 1
we can build — on the top of our result — this derivative form:
NP(

*n*)=

*n *+ 1 22

*n*-3 -

*n*-1
That is a formula for P that avoid explicits summation (and, therefore, is computationally cheaper). Additional results — like the generalization of this new form to the case where the two chains differ in length — can be also proved without much effort, using the interpretation we have (literally!) seen.

[Cod09a] Pietro Codara,

*Partitions of a finite partially ordered set*, From Combinatorics to Philosophy: The
Legacy of G.-C. Rota, Springer, New York (2009), 45-59.

[Cod09b] Pietro Codara, Ottavio M. D’Antona, Vincenzo Marra,

*Open Partitions and Probability Assignments*
*in Gödel Logic*,

*Symbolic and Quantitative Approaches to Reasoning with Uncertainty. *Lecture Notes inComputer Science Volume 5590, 2009, pp 911-922.

[Cod10a] P. Codara, O. M. D’Antona, E. Munarini:

*Mathematica sa fare le somme?* Mathematica Italia User
Group Meeting (UGM) 2010, Italian. (2010)
[Cod10b] P. Codara:

*A Mathematica package to cope with partially ordered sets. * Mathematica Italia User
[Hirsch96] M. Hirschhorn.

*Calkin’s binomial identity*. Discrete Mathematics, 159(1- 3):273-278, 1996.

[OEIS] Sloane, Neil JA.

*The on-line encyclopedia of integer sequences.* (2003).

Source: http://www.cody.it/pietrocodara_files/pub_cdmm_ugm2013_pre.pdf

LIST OF CONTROLLED MEDICATION FOR DOGS As of February 8th 2013 1. Antibiotics administered orally . A Veterinary Form 1, Medication Administration Form must be filled out by the treating veterinarian to indicate medication, dosage, and reason for treating. If antibiotic treatment must be initiated on a dog prior to an event, the form should be filled out by the attending veterinarian, a

ANY QUESTIONS FOR THE PHARMACIST? Charles F. Caley, Pharm.D., addressed questions from audience members in the Brace Professor Auditorium at the Tully Health Center in Stamford on March 17th. The audience of 35 to 40 included NAMI Stamford/Greenwich affiliate board members, as well as those living with mental illnesses and their families. Dr. Caley is an Associate Clinical Professor of Pharma