Geodesic
A combinatorial interpretation of the eigensequence for composition
Journal of integer sequences, Tome 9 (2006) no. 1.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: The monic sequence that shifts left under convolution with itself is the Catalan numbers with 130+ combinatorial interpretations. Here we establish a combinatorial interpretation for the monic sequence that shifts left under $composition$: it counts permutations that contain a 3241 pattern only as part of a 35241 pattern. We give two recurrences, the first allowing relatively fast computation, the second similar to one for the Catalan numbers. Among the $4\times 4!=96$ similarly restricted patterns involving 4 letters (such as $4\underline{2}31$: a 431 pattern occurs only as part of a 4231), four different counting sequences arise: 64 give the Catalan numbers, 16 give the Bell numbers, 12 give sequence A051295, in OEIS, and 4 give a new sequence with an explicit formula.
Classification : 05A15
Keywords: eigensequence, 35241OK permutation, restricted pattern, underlined pattern 
@article{JIS_2006__9_1_a3,
     author = {Callan, David},
     title = {A combinatorial interpretation of the eigensequence for composition},
     journal = {Journal of integer sequences},
     publisher = {mathdoc},
     volume = {9},
     number = {1},
     year = {2006},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JIS_2006__9_1_a3/}
}
TY  - JOUR
AU  - Callan, David
TI  - A combinatorial interpretation of the eigensequence for composition
JO  - Journal of integer sequences
PY  - 2006
VL  - 9
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JIS_2006__9_1_a3/
LA  - en
ID  - JIS_2006__9_1_a3
ER  - 
%0 Journal Article
%A Callan, David
%T A combinatorial interpretation of the eigensequence for composition
%J Journal of integer sequences
%D 2006
%V 9
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JIS_2006__9_1_a3/
%G en
%F JIS_2006__9_1_a3
Callan, David. A combinatorial interpretation of the eigensequence for composition. Journal of integer sequences, Tome 9 (2006) no. 1. http://geodesic.mathdoc.fr/item/JIS_2006__9_1_a3/