OLEIS sequences

Some entries in the The On-Line Encyclopedia of Integer Sequences

I tend to enter these sequences because they mark a calculation in the same way that writing a paper marks some research project. They are a smaller accomplishment (sometimes they are just a germ of an idea) but they reflect some idea that I was thinking about in my research that I was interested in exploring. An entry in the OLEIS for me is a place marker. Because these entries are editable, I (or someone else) can hopefully come back to some day and explain more completely.

I want to organize these entries here because I feel that I am leaving some interesting ideas behind that I might explore more if I had them laid out in a way that I could see them clearer.

Non-commutative invariants and coinvariants

I wrote a number of papers on NCSym, NCQSym, and non-commutative coinvariants. We were able to compute a lot of the sequences below easily when this project started but took a while to figure out what it was we were looking at. For instance we knew about this paper of Wolf that describes the free generators of NCSym_n and this was in the database for a long time. It wasn't really until 2005 that we had a clear combinatorial interpretation for the numbers and formulas for their generating functions and this came from looking at the coinvariants of Q<X_n>/<NCSym_n^+>.

Set partitions, primitive elements and free generators of NCSym
A008277 - triangle of number of set partitions (dimensions of NCSym) by number of parts and size - Stirling numbers of the 2nd kind
A087903 - triangle of non-splitable set partitions (free generators of NCSym) by number of parts and size (Oct 14 2003)
A055105, A055106, A055107 - triangle of irreducible set partitions (free generators of NCSym_n) by number of parts and size
A112340 - triangle of Lyndon set partitions (primitive elements of NCSym) by number of parts and size (Sep 05 2005)

A085686 - primitives of NCSym - 'Lyndon' set partitions - row sums of A112340

A074664 - free generators of NCSym (row sums of A055105, A055106, A055107, A087903) - non-splitable or irreducible set partitions
A001519 - free generators of NCSym_3 - also F(2n-1) - Fibonacci numbers
A124292 - free generators of NCSym_4 (Oct 24 2006)
A124293 - free generators of NCSym_5 (Oct 24 2006)
A124294 - free generators of NCSym_6 (Oct 24 2006)
A124295 - free generators of NCSym_7 (Oct 24 2006)

A000110 - dimension of NCSym - Bell numbers
A000079 - dimension of NCSym_2 - sum of first two Stirling numbers (2nd kind)
A124302 - dimension of NCSym_3
A007581, A124303 - dimension of NCSym_4
A056272 - dimension of NCSym_5
A056273 - dimension of NCSym_6
A099262 - dimension of NCSym_7
A099263 - dimension of NCSym_8

set compositions, free generators and primitive elements of NCQSym
A109062 - triangle of atomic set compositions (primitives/free gen of NCQSym) by number of parts and size (Aug 24 2005)
A095989 - atomic set compositions- row sums of A109062
A095993 - 'Lyndon' set compositions (if there were commutative generators of NCQSym)

Non-commutative harmonics (with respect to twisted derivative) NCHar_n \otimes NCSym_n = Q< x_1, x_2, ..., x_n >
A122367 - dimension of NCHar_3 (note essentially the same as A001519 - free generators of NCSym_3)
A122368 - dimension of NCHar_4
A122369 - dimension of NCHar_5
A122370 - dimension of NCHar_6
A122371 - dimension of NCHar_7
A122372 - dimension of NCHar_8

Non-commutative harmonics (with respect to the Hausdorff derivative) MHar_n \otimes Sym_n = Q< x_1, x_2, ..., x_n > also MHar_n = A_n' \otimes H_n
A122391 - dimension of MHar_2
A122392 - dimension of MHar_3
A122393 - dimension of MHar_4
A122394 - dimension of MHar_5

proper polynomials, or universal enveloping algebra of derived free Lie algebra A_n' or intersection of all kernels of \partial_{x_i} (non-commutative setting)
A118264 - dimension of A_3'
A118265 - dimension of A_4'
A118266 - dimension of A_5'

Pattern avoidance with a fixed number of descents/valleys

With Murray Elder and Andrew Rechnizter we conjectured and proved that the number of pattern avoiding permutations with a fixed number of descents or valleys has a rational generating function. We made this conjecture because the the number of permutations with a fixed number of descents also has a rational generating function. It turns out that this result can be shown to be a consequence of work by Albert and Atkinson because having a bounded number of descents is a 'closed' property. This was a bit disappointing because we worked very hard for a long while before we found this connection and so we were unable to publish the result. We even wrote a computer program to build a DFA which generated a language which was in bijection with the permutations with at most k descents and avoids a given pattern. I used this computer program to compute a handful of examples of sequences of this type with rational generating functions.

We used these techniques to show that growth of 1324 avoiding permutations was greater than 10^n and it was previously conjectured to be 9^n (Andrew immediately saw through the conjecture within 10 minutes of looking at some data).

A000292 - Number of permutations of n+3 which have exactly 1 descent and avoid the pattern 1324
A098992 - Number of permutations of [n] with exactly 2 descents which avoid the pattern 1324
A098994 - Number of permutations of [n] with exactly 3 descents which avoid the pattern 1324
A098995 - Number of permutations of [n] with exactly 4 descents which avoid the pattern 1324
A099743 - Number of permutations of [n] with exactly 1 valley which avoid the pattern 1324
A099745 - Number of permutations of [n] with exactly 2 valleys which avoid the permutation 1324
A000217 - Number of permutations of [n] which avoid the pattern 132 and have exactly 1 descent
A002415 - Number of permutations of [n] which avoid the pattern 132 and have exactly 2 descents
A006542 - Number of permutations of n+4 which avoid the pattern 132 and have exactly 3 descents
A095889 - Number of permutations of [n] with exactly 3 descents which avoid the pattern 4321
A027660 - Number of 135246-avoiding permutations of n+2 with exactly 1 descent

The Connectivity Set of an element of a Coxeter group

In work with Christophe Hohlweg and Nantel Bergeron we studied the elements of Coxeter groups generated by different numbers of simple reflections. We define the connectivity set of element of a Coxeter group to be the set of simple reflections which do not appear in a reduced expression for the element (this was to correspond to language used in paper by Stanley). For elements of the families of Coxeter groups of type A, B and D we were able to use the Dynkin diagram to find recurrences and give generating functions for the elements which use all the simple reflections and the tables of the numbers of simple elements which use exactly k simple reflections.

The reason that this work arose is that we were looking at the number of free generators of NCQSym and a partial order which defined a nice multiplicative basis. When we looked at the partial order on the elements of NCQSym which correspond to permutations we were surprised to find that this order was new and defined a graded poset on permutations where the rank was the number of simple reflections which appear in a reduced expression. By translating this information to all Coxeter groups we were able to prove interesting properties of the poset.

A003319 - Number of connected permutations of [1..n] (those not fixing [1..j] for 0<j<n). Also called indecomposable permutations
A059438 - Triangle T(n,k) (1<=k<=n) read by rows: T(n,k) = no. of permutations of [1..n] with k components

A109253 - Number of elements of the Coxeter group of type B where a reduced word contains all of the simple reflections.
A109281 - Triangle T(n,k) of elements of n-th Coxeter group of type B whose reduced word uses n-k generators.

A112225 - Number of elements of a Coxeter group of order 2^{n-1} n! of type D for which a reduced word contains all of the simple reflections.
A112226 - Table T(n,k) of number of elements of Coxeter group of type D of order 2^{n-1} n! such that a reduced word uses exactly n-k distinct simple reflections 0 <= k <= n, n>=1.

Kronecker products and constant term identities

One of the oldest and hardest problems in algebraic combinatorics is to find an interpretation for the coefficients in the Kronecker product of two Schur functions (alternatively, the decomposition of an internal tensor product of two irreducible S_n representations) (alternatively, the decomposition of an irrreducible GL_{n^2} representation into GL_n \otimes GL_n representations).

I do not know how to do this in general, but I do not think that it is hopeless. I have gotten interested in special cases of this problem because certain families of Kronecker coefficients are well behaved. The reason I got interested in the first place is that Adriano Garsia asked me a question that was posed to him by Nolan Wallach related to the computation of dimensions of invariants which are equivalent to taking k-fold Kronecker products of s_(d,d). This lead to an interesting formula for s_(d,d) * s_(d,d) which is the sum of all partitions with 4 parts which are all even or all odd (0 counts as an even part).

Eventually this lead to questions about how to take constant terms of rational functions and work with Guoce Xin.

A008763 - < s_{(d,d)}^{\otimes 4}, s_{2d} >
A082437 - < s_{(d,d)}^{\otimes 5}, s_{2d} >
A082424 - < s_{(d,d)}^{\otimes 6}, s_{2d} >
A115375 - < s_{(d,d)}^{\otimes 3}, h_{d,d} >
A115376 - < s_{(d,d)}^{\otimes 3}, h_{d+1,d-1} >
A129548 - measures of entanglement in 3-qbits
A129549 - measures of entanglement in 4-qbits
A129550 - number of real polynomial invariants for 4 copies of U(2) on \otimes^4 C^2

This lead to the study of the behavior of the Kronecker product with s_{d,d} and in particular that
s_{d,d} * (s_{d,d} + s_{d+1,d-1}) = sum s_\la
with \la running over partitions of 2d with length <= 4. When you convert this into a statement about standard tableaux it says:
A005817 - (products of Catalan) standard tableaux with height less than or equal to four
A047889 - pairs of standard tableaux of the same shape of height less than or equal to four

A001006 - (Motzkin) standard tableaux with height less than or equal to three
A005802 - pairs of standard tableaux with the same shape of height less than or equal to three
A129130 - triples of standard tableaux with the same shape of height less than or equal to three

A001405 - (C(n,floor(n/2))) standard tableaux with height less than or equal to two
A000108 - (Catalan) pairs of standard tableaux of the same shape of height less than or equal to two
A003161 - triples of standard tableaux of the same shape of height less than or equal to two
A129123 - 4-tuples of standard tableau with height less than or equal to two

Self avoiding walks and self avoiding polygons

I got interested in self avoiding walks because I realized you could see them as an application of non-commutative Grobner bases. We began to look at self avoiding walks on lattices of reflection groups in hopes that it would be possible to apply techniques of Coxeter groups and non-commutative algebra to what would normally be considered a statistical mechanical or combinatorics question.

A249565 - self avoiding walks on the truncated square lattice, (4,8^2)-lattice
A249795 - self avoiding walks on the truncated trihexagonal tiling or (4,8,12)-lattice

The sequences below are the ones that I have authored. Most of these are listed above, but a few do not fit a patterns of topics like those listed above. Two people contacted me over the sequence A060350 because it arose in their research and they wanted to know why I was thinking about it (I was imagining an algebra much like what they both found).

Sequences from The On-Line Encyclopedia of Integer Sequences:
A060350, A060351, A082424, A082437, A087903, A095718, A095719, A095889, A095989, A095993, A098992, A098994, A098995, A099743, A099745, A107713, A109062, A109253, A109281, A112225, A112226, A112339, A112340, A112354, A115375, A115376, A118264, A118265, A118266, A122367, A122368, A122369, A122370, A122371, A122372, A122391, A122392, A122393, A122394, A123223, A123915, A123916, A124292, A124293, A124294, A124295, A124302, A124303, A124720, A124721, A124722, A124723, A124810, A124811, A124812, A124813, A124814, A129123, A129130, A129548, A129549, A129550, A249565 A249795