^{1}

^{*}

^{2}

A sentence over a finite alphabet A, is a finite sequence of non-empty words over A. More generally, we define a graphical sentence over A by attaching a non-empty word over A to each arrow and each loop of a connected directed graph (digraph, for short). Each word is written according to the direction of its corresponding arrow or loop. Graphical sentences can be used to encode sets of sentences in a compact way: the readable sentences of a graphical sentence being the sentences corresponding to directed paths in the digraph. We apply combinatorial equations on enriched trees and rooted trees, in the context of combinatorial species and Pólya theories, to analyze parameters in classes of tree-like sentences. These are graphical sentences constructed on tree-like digraphs.

^{1} connected digraph. We define a graphical sentence over a finite alphabet A by attaching a non-empty word over A to each arrow and each loop of a completely unlabelled connected digraph. Each word must be written according to the direction of its corresponding arrow or loop, from source to target.

Graphical sentences can be used to encode sets of ordinary sentences in a compact way: The readable sentences of a graphical sentence being the sentences corresponding to directed paths in its digraph. For example,

TTT C GCCTG CAT CAT GCAATT, is a readable sentence arising from the graphical sentence of

In the present paper we focus our attention on the structure of graphical sentences as combinatorial objects using methods from the theory of combinatorial species [^{2}. Of course, special sentences among the readable sentences can be selected by adding extra structure to graphical sentences (such as source points, sink points, STOP points, counters, extensions of the alphabet by adding special characters such as ò, !, ?, etc). We also leave aside this aspect in our analysis of graphical sentences.

Various descriptive parameters can be attached to each graphical sentence over a given alphabet A. For example, the graphical sentence of

As usual in enumerative combinatorics, families of parameters associated to structures are conveniently encoded by weight-monomials.

Definition 1.1. The weight of a graphical sentence s over an alphabet A is the (commutative) formal monomial^{3}

where

In (1), each letter

Definition 1.2. Let

As usual in enumeration problems, the (explicit or recursive) computation of an inventory of a class of structures provides a great deal of information about the structures to which it is associated. This information is extracted from the inventory through expansion, collection of terms, specialization/confluence of variables, algebraic/differential manipulations and coefficient extraction.

For example, in the present situation, expanding and collecting terms in (3) gives, of course,

where the coefficient

rows, p loops, a total number of q letters,

Assigning the value 1 to each letter a and collecting terms gives

where

where

Letting

where

Let

Moreover, if we let

is a polynomial, where

Of course, a variety of other similar manipulations of the inventory

tion 2 we apply methods from the theory of species and Pólya theory, to express inventories of general classes of graphical sentences in terms of cycle index series. Section 3 deals with specific classes of graphical sentences: linear sentences (corresponding to path-like digraphs) and general tree-like sentences (corresponding to classes of tree-like digraphs). We conclude (Section 4) by giving suggestions for possible extensions and generalizations of our results. Various explicit examples are given and to make the text easier to read, the proofs of the main results are collected in Section 5. In a previous paper, [

We assume that the reader is familiar with Pólya theory [

In order to give a rigorous meaning to the notion of a totally unlabelled digraph and to be able to take into account the possible symmetries within graphical sentences, we must recall first some definitions concerning labelled digraphs. A digraph on (or labelled by) a finite set V of vertices, a finite set

where

If

is an automorphism of the digraph of

We now give a rigorous definition of the notion of a graphical sentence.

Definition 2.1. Let A be a finite alphabet and

^{4}This means that _{1} of arrows and V_{0} of loops, which is closed under arbitrary isomorphisms.

^{5}More precisely, X is the species of singleton vertices, Y is the species of singleton arrows and Z is the species of singleton loops.

Now take any species ^{4}. Our goal is to compute the inventory (3) of the class ^{5}. Any digraph

Following standard notations from the theory of species, the set of all

the bijection

Many power series can be associated to any species

where, for each permutations^{6} of all digraphs^{7} of length i in the cyclic decomposition of

^{6}Or total weight, in the case of weighted digraphs.

^{7}Not to be confused with

^{8}In particular, the empty sequence, 0, has no component and satisfies 0 0.

The sequence of integers

Note that each sequence k has a finite number of nonzero terms and will be considered, in the present text, as a finite sequence with ^{8}

to express this fact. Note also that

in (18). In order to eliminate this redundancy, we regroup monomials which correspond to each of these types, and taking (19) into account we obtain the following more compact variant expression for the cycle index series of

in which each monomial appears only once and

The following proposition is a consequence of general principles from the theory of species and Pólya theory. It shows that the computation of

Proposition 2.1. Let

where

Proof. See Section 5.

Making use of the compact expression (22) for the cycle index series and collecting terms, inventory (23) can be rewritten in the following more explicit form.

Corollary 2.2. The inventory,

where

Note. If

^{9}Where only the vertices are labelled.

^{10}However, for the 3-sort species _{Dig} can be computed explicitly (see Section 4).

As shown in the preceding section, the computation of the inventory of a class ^{9}, the complete cycle index series of the species of all ordinary plane digraphs and all transitive digraphs are still unknown^{10}.

For this reason, we focus our study on the following basic classes of graphical sentences:

1) Linear sentences (arising from the species of path-shaped digraphs).

2) General tree-like sentences (arising from various species of tree-like digraphs).

Note that linear sentences are special kinds of tree-like sentences. Due to their close relationship with ordinary sentences, we have chosen to present first a separate subsection devoted to their study. Our methods will use the fact that species of tree-like digraphs can be built from simpler species by making use of basic combinatorial operations and that cycle index series behave well with respect to these operations. For example, if F, G and H are species, then

where

We say that a digraph

is an automorphism of the path-shaped digraph of

Special kinds of linear sentences over an alphabet include ordinary sentences (

For example, the sentence

is one of the readable sentences in

Proposition 3.1 Let

where,

Proof. See Section 5.

In view of (30)-(32), the alternate general inventory formula (24) in the case of any class of linear sentences, does not involve

Corollary 3.2. For the classes

where

using the convention

Proof. (Sketch) Formulas (34) and (36) are immediate since no loops are involved. Careful computations, starting from (30) and (32) using geometric series, the binomial theorem, and manipulation or indices lead to expansions (33) and (35).

Sample of explicit examples of computations.

Example 3.1. General shape of the inventory of the class

The first few terms of

The coefficients of

zero, due to the fact that

Example 3.2. Counting linear sentences with given parameters.

Corollary 3.2 is particularly useful when one wants to compute an individual term in the inventory of linear sentences. For example, consider the 3-letter alphabet

where

The required number of linear sentences equals the coefficient of

If we take

and (44) goes down to 16882686796464720.

Example 3.3. Manipulating the inventory of linear sentences.

As we have seen in Section 1, manipulations of inventories (specialization of variables, expansions, etc) can be made to analyze various parameters in graphical sentences. Proposition 3.1 is generally more suitable for such manipulations than Corollary 3.2. For example, let

where

asymptotic expansion of

Example 3.4. Fibonacci numbers versus ordinary sentences with loops.

Consider now the class

^{11}, for

where ^{11} and

Finally, making use of (10) and invoking Binet’s formula

where

The reader can check that if we do not allow loops, then (51) is replaced by

A multitude of other similar examples can be obtained using Proposition 3.1 and Corollary 3.2.

We say that a digraph

The tree-like structures of

Definition 3.1. [

1) A R-enriched rooted tree is a rooted tree in which the set of immediate descendants (away from the root) of every vertex is equipped with a R-structure (see

2) A R-enriched tree is a tree in which the set of immediate neighbors of each vertex is equipped with a R-structure (see

Lemma 3.3 [

and the species ^{12}

where

It is easy to see that the species of ordinary rooted trees (resp. ordinary trees) corresponds to the species A_{R} (resp. a_{R}) with the choice_{R} with the choice _{2}, the species of 2-element sets. The species of all plane trees corresponds to the species a_{R} with the choice

For the computation of the inventories of various classes of enriched tree-like graphical sentences, we will make use of the following 3-sort extension of Lemma 3.3 which includes a new extension, (56) below, of the dissymmetry formula (53).

Lemma 3.4. The species

where

The species

where

Proof. See Section 5.

In our analysis of tree-like graphical sentences, we will use of the following useful compact “plethystic notation” which is classical in the theory of species and cycle index series.

Notation 3.5. Let

In particular,

then

in the variables

For example, taking the variables

where

We now describe how to compute the inventory of classes of tree-like sentences.

Proposition 3.6 Given an arbitrary species

over an alphabet A and a set

They can also be expressed explicitly in terms of the cycle index series

where

In the case of the corresponding sets,

Proof. (sketch) Apply Proposition 2.1, taking into account Lemma 3.4.

Note. When written explicitly, (65) takes the form

where

Sample of explicit examples of computations.

Example 3.5. One way free binary rooted tree sentences.

Consider the set

and, since

Of course, as many terms as we want in (72) and (73) can be computed using a computer algebra system. For a more specific application, let

The coefficient of

Example 3.6. Ordinary tree and rooted tree sentences.

Let

the second equation being the classical dissymmetry formula of Leroux. Taking cycle index series in (80) and using

from which ^{13}.

Now, let

Then, by (67)-(69),

For more specific applications, let

The coefficient of

Consider now the 2-letter alphabet

where

If we choose

etc. Again, all the above series, and many variants, can be expanded to arbitrary orders.

Example 3.7. Back to linear sentences.

Since linear sentences are special kinds of tree-like sentences, it is interesting to look at the dissymmetry formula (56) in the context of path-shaped graphs. Take the 1-sort species

R-enriched trees. Moreover, since

where

This formula coincides with formula (124) which is used in the proof of Proposition 3.1.

Example 3.8. Plane tree sentences.

A plane tree is a (unrooted) tree that is embedded in a plane. Such tree-structures have fewer automorphisms than free trees. Take any vertex p of a plane tree

Take

Using the expansion^{14}, we get, from (68) and (69), the following

explicit expressions for the inventory

where

Note that since linearly ordered rooted tree structures are asymmetric structures, no

This time, the coefficient of

As a final illustration, fix

Now, let

which is a polynomial in t, since

where

Again, all the above inventories can be manipulated in a great number of ways.

It would be interesting to extend the above analysis to other classes of graphical sentences arising from other families of 3-sort species of connected digraphs. As said before, this is generally a very difficult task. However, the analysis can be done, for example, for the class of cyclic graphical sentences (for which the underlying simple graphs are unoriented cycles) by making use of (3-sort) cycle index series related to subgroups of the dihedral groups. The analysis can also be done for the whole class of all graphical sentences since the cycle index series of the 3-sort species, ^{15}. In fact,

^{15}The cycle index series of the 1-sort species,

where

Another direction of investigation would be to replace digraphs by dimultigraphs (directed multigraphs) and study associated inventories of classes of multigraphical sentences. For example, in the case of the 3-sort (resp. 2-sort) species

Proof of Proposition 2.1. First, consider the weighted species

Next, let

belled

and for Z in

Taking the cycle index series of (117) we get

Next, assigning a weight

whose cycle index,

Proof of Proposition 3.1. The inventories (30) of the two special kinds of linear graphical sentences,

form

and, since

On the other hand, the inventories of the sets

Let

This pointing induces a global orientation to these pointed structures (see dotted arrow) and implies that the species K is a species of sequences:

As a consequence of the general dissymmetry formula (56) the species P can be expressed in terms of K and

where

since every

Proof of Lemma 3.4. Consider an

arrow (that is, by replacing each such edge by an Y-structure). This establishes (54a). The proof of the combinatorial Equation (54b) is similar, where, this time, each edge adjacent to the root of t is replaced by an outward arrow, an inward arrow or a double arrow (that is, by replacing each such edge by a

But, by (52), the species

The dissymmetry formula (56) is much more difficult to establish since more automorphisms are involved in enriched trees. To prove this combinatorial equality, we express in two ways the auxiliary species

・ The first expression for

To prove it, consider a

1) If

2) If

vertices must be replaced either by a double arrow (i.e.,

・ The second expression for

To prove it, we first split the species

Since the center of a tree is a canonical object, pointing a tree exactly at its center is naturally equivalent to doing nothing to the tree and we have

Now, consider a

1) If

recover

2) If

an arbitrary

This establishes (129) since any

GilbertLabelle,LouiseLaforest, (2015) A Combinatorial Analysis of Tree-Like Sentences. Open Journal of Discrete Mathematics,05,32-53. doi: 10.4236/ojdm.2015.53004