# [seqfan] A108081 as a combinatorial enumeration

Li-yao Xia li-yao.xia at ens.fr
Fri Oct 23 00:11:01 CEST 2015

```Hello seqfans,

Consider the smallest set X of finite sequences of integer (words), such
that
- 0 belongs to it;
- if a and b are two words in X, let L(a) be the word obtained by
reversing a and subtracting one to every element, and R(b) be the word
obtained by reversing b and adding one to every element, then the
concatenations L(a).b and a.R(b) belong to X.

Examples of L and R values:
L(10,30,20) = 19, 29, 9
R(10,30,20) = 21, 31, 11

Words of X of lengths 1, 2, 3:

0

0,  1
-1,  0

-1,  0,  1 = L(0), 0, 1 = -1, 0, R(0)
0,  2,  1 = 0, R(0, 1)
1, -1,  0 = L(0), -1, 0
0,  1,  0 = 0, R(-1, 0)
0, -1,  0 = L(0, 1), 0
0,  1,  1 = 0, 1, R(0)
-1, -2,  0 = L(-1, 0), 0

The sequence of words of X of length n=1,... starts:
1,2,7,25,92,344,1300,4950,18955,72905,281403,1089343

that matches (up to a shift of indices) A108081(n) = sum(i = 0 .. n, C(2
* n - i, n + i)) but I am at a loss as to how to prove or disprove the
validity of this formula.

The operations L(a).b and a.R(b) in the definition of X come up in the
study of something called pregroup types, somewhere in the intersection
of linguistics and category theory--I don't know any more than that
about their origins. The question of the enumeration of X seems to be
only recreationally motivated, but I found the shortness of the
conjectured formula quite odd.

Any ideas?

Li-yao
```