A051295 - OEIS

%I #82 Jul 10 2023 10:29:35

%S 1,1,2,5,15,54,235,1237,7790,57581,489231,4690254,49986715,585372877,

%T 7463687750,102854072045,1522671988215,24093282856182,405692082526075,

%U 7242076686885157,136599856992122366,2714409550073698925

%N a(0)=1; thereafter, a(m+1) = Sum_{k=0..m} k!*a(m-k).

%C a(n) = number of permutations on [n] that contain a 132 pattern only as part of a 4132 pattern. For example, a(4) = 15 counts the 14 132-avoiding permutations on [4] (Catalan numbers A000108) and 4132.

%C a(n) is the number of permutations on [n] that contain a (scattered) 342 pattern only as part of a 1342 pattern. For example, 412635 fails because 463 is an offending 342 pattern (= 231 pattern).

%C This sequence gives the number of permutations of {1,2,...,n} such that the elements of each cycle of the permutation form an interval. - _Michael Albert_, Dec 14 2004

%C Starting (1, 2, 5, 15, ...) = row sums of triangle A143965. - _Gary W. Adamson_, Apr 10 2009

%C Number of compositions of n where there are (k-1)! sorts of part k. - _Joerg Arndt_, Aug 04 2014

%H Vincenzo Librandi and Vaclav Kotesovec, <a href="/A051295/b051295.txt">Table of n, a(n) for n = 0..448</a> (first 100 terms from Vincenzo Librandi)

%H David Callan, <a href="http://arxiv.org/abs/math/0507169">A combinatorial interpretation of the eigensequence for composition</a>, arXiv:math/0507169 [math.CO], 2005.

%H David Callan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Callan/callan96.html">A Combinatorial Interpretation of the Eigensequence for Composition</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.4.

%H Stefan Forcey, Aaron Lauve and Frank Sottile, <a href="http://www.combinatorics.net/Annals/Abstract/17_1_105.aspx">Cofree compositions of coalgebras</a>, Annals of Combinatorics 17 (1) pp. 105-130 March, 2013.

%H Richard J. Martin, and Michael J. Kearney, <a href="http://dx.doi.org/10.1007/s00493-014-3183-3">Integral representation of certain combinatorial recurrences</a>, Combinatorica: 35:3 (2015), 309-315.

%H Lara Pudwell, <a href="https://doi.org/10.37236/301">Enumeration Schemes for Permutations Avoiding Barred Patterns</a>, El. J. Combinat. 17 (1) (2010) R29.

%F It appears that the INVERT transform of factorial numbers A000142 gives 1, 2, 5, 15, 54, 235, 1237, ... - _Antti Karttunen_, May 30 2003

%F This is true: translating the defining recurrence to a generating function identity yields A(x)=  1/(1 - (0!x + 1!x^2 + 2!x^3 + ...)) which is the INVERT formula.

%F In other words: let F(x) = Sum_{n>=0} n!*x^n then the g.f. is 1/(1-x*F(x)), cf. A052186 (g.f. F(x)/(1+x*F(x))). - _Joerg Arndt_, Apr 25 2011

%F a(n) = Sum_{k>=0} A084938(n, k). - _Philippe Deléham_, Feb 05 2004

%F G.f. A(x) satisfies: A(x) = (1-x)*A(x)^2 - x^2*A'(x). - _Paul D. Hanna_, Aug 02 2008

%F G.f.: A(x) = 1/(1-x/(1-1*x/(1-1*x/(1-2*x/(1-2*x/(1-3*x/(1-3*x...))))))))) (continued fraction). - _Paul Barry_, Sep 25 2008

%F From _Gary W. Adamson_, Jul 22 2011: (Start)

%F a(n) = upper left term in M^n, M = an infinite square production matrix in which a column of 1's is prepended to Pascal's triangle, as follows:

%F   1, 1, 0, 0, 0, ...

%F   1, 1, 1, 0, 0, ...

%F   1, 1, 2, 1, 0, ...

%F   1, 1, 3, 3, 1, ...

%F   ...

%F Also, a(n+1) = sum of top row terms of M^n. (End)

%F G.f.: 1+x/(U(0)-x) where U(k) = 1 + x*k - x*(k+1)/U(k+1); (continued fraction, 1-step). - _Sergei N. Gladkovskii_, Oct 10 2012

%F G.f.: 1/(U(0) - x) where U(k) = 1 - x*(k+1)/(1 - x*(k+1)/U(k+1)); (continued fraction, 2-step). - _Sergei N. Gladkovskii_, Nov 12 2012

%F a(n) ~ (n-1)! * (1 + 2/n + 7/n^2 + 31/n^3 + 165/n^4 + 1025/n^5 + 7310/n^6 + 59284/n^7 + 543702/n^8 + 5618267/n^9 + 65200918/n^10), for coefficients see A260532. - _Vaclav Kotesovec_, Jul 28 2015

%e a[ 4 ]=15=a[ 3 ]*0!+a[ 2 ]*1!+a[ 1 ]*2!+a[ 0 ]*3!=5*1+2*1+1*2+1*6.

%e As to matrix M, a(3) = 5 since the top row of M^n = (5, 5, 4, 1), with a(4) = 15 = (5 + 5 + 4 + 1).

%p a := proc(n) option remember; `if`(n<2, 1, add(a(n-j-1)*j!, j=0..n-1)) end proc: seq(a(n), n=0..30); # _Vaclav Kotesovec_, Jul 28 2015

%t Table[Coefficient[Series[E^x/(E^x-ExpIntegralEi[x]),{x,Infinity,20}],x,-n],{n,0,20}] (* _Vaclav Kotesovec_, Feb 22 2014 *)

%o (PARI) {a(n)=local(A=1+x+x*O(x^n));for(i=1,n,A=(1+x^2*deriv(A)/A)/(1-x));polcoeff(A,n)} \\ _Paul D. Hanna_, Aug 02 2008

%Y Cf. A051296, A260532.

%Y Row sums of A084938.

%Y Cf. A143965. - _Gary W. Adamson_, Apr 10 2009

%K easy,nonn

%O 0,3

%A _Leroy Quet_

%E More terms from _Vincenzo Librandi_, Feb 23 2013