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

1, 1, 2, 5, 15, 54, 235, 1237, 7790, 57581, 489231, 4690254, 49986715, 585372877, 7463687750, 102854072045, 1522671988215, 24093282856182, 405692082526075, 7242076686885157, 136599856992122366, 2714409550073698925, 56674981258436882463, 1240409916125255533662

Offset: 0

Author

Leroy Quet

Keywords

• easy
• nonn
• changed

Comments

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.

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).

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

Starting (1, 2, 5, 15, ...) = row sums of triangle A143965. - Gary W. Adamson, Apr 10 2009

Number of compositions of n where there are (k-1)! sorts of part k. - Joerg Arndt, Aug 04 2014

Examples

			a[ 4 ]=15=a[ 3 ]*0!+a[ 2 ]*1!+a[ 1 ]*2!+a[ 0 ]*3!=5*1+2*1+1*2+1*6.
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).
		

Links

• Vincenzo Librandi and Vaclav Kotesovec, Table of n, a(n) for n = 0..448 (first 100 terms from Vincenzo Librandi)
• David Callan, A combinatorial interpretation of the eigensequence for composition, arXiv:math/0507169 [math.CO], 2005.
• David Callan, A Combinatorial Interpretation of the Eigensequence for Composition, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.4.
• Stefan Forcey, Aaron Lauve and Frank Sottile, Cofree compositions of coalgebras, Annals of Combinatorics 17 (1) pp. 105-130 March, 2013.
• Richard J. Martin, and Michael J. Kearney, Integral representation of certain combinatorial recurrences, Combinatorica: 35:3 (2015), 309-315.
• Lara Pudwell, Enumeration Schemes for Permutations Avoiding Barred Patterns, El. J. Combinat. 17 (1) (2010) R29.

Crossrefs

Cf. A051296, A260532.

Row sums of A084938.

Cf. A143965. - Gary W. Adamson, Apr 10 2009

Column k=0 of A381529.

Programs

Maple

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

Mathematica

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

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

Formula

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

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.

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

a(n) = Sum_{k>=0} A084938(n, k). - Philippe Deléham, Feb 05 2004

G.f. A(x) satisfies: A(x) = (1-x)*A(x)^2 - x^2*A'(x). - Paul D. Hanna, Aug 02 2008

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

From Gary W. Adamson, Jul 22 2011: (Start)

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:

1, 1, 0, 0, 0, ...

1, 1, 1, 0, 0, ...

1, 1, 2, 1, 0, ...

1, 1, 3, 3, 1, ...

...

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

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

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

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

Extensions

More terms from Vincenzo Librandi, Feb 23 2013