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

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 |