A381529 -id:A381529 - cp's OEIS frontend

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

Leroy Quet

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

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

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.

Cf. A051296, A260532.
Row sums of A084938.
Cf. A143965. - Gary W. Adamson, Apr 10 2009
Column k=0 of A381529.

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

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

{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

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

More terms from Vincenzo Librandi, Feb 23 2013

A126673 Third diagonal of A126671.

Original entry on oeis.org

0, 2, 26, 274, 2844, 30708, 351504, 4292496, 55988640, 779171040, 11545476480, 181705299840, 3029581820160, 53376951801600, 991337037465600, 19363464423475200, 396915849843609600, 8520964324004966400, 191220598650009600000, 4477883953203763200000, 109242544826541772800000

Offset: 2

N. J. A. Sloane and Carlo Wood (carlo(AT)alinoe.com), Feb 13 2007

nonn

It appears that a(n) = sum of invc(p) over all permutations p of {1,2,...,n}, where invc(p) is defined (by Carlitz) in the following way: express p in standard cycle form (i.e., cycles ordered by increasing smallest elements with each cycle written with its smallest element in the first position), then remove the parentheses and count the inversions in the obtained word. a(3)=2 because the six permutations 123,132,312,213,231 and 321 of {1,2,3} yield the words 123,123,132,123,123 and 132, respectively, having a total of 0+0+1+0+0+1 = 2 inversions. a(n) = Sum_{k>=0} k*A129178(n,k). - Emeric Deutsch, Oct 10 2007

L. Carlitz, Generalized Stirling numbers, Combinatorial Analysis Notes, Duke University, 1968, 1-7.

G. C. Greubel, Table of n, a(n) for n = 2..445
M. Shattuck, Parity theorems for statistics on permutations and Catalan words, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 5, Paper A07, 2005.
N. J. A. Sloane, Notes on Carlo Wood's Polynomials

Cf. A129178, A381529.

[Factorial(n)*(n*(n-5)/4 + HarmonicNumber(n)): n in [2..25]]; // G. C. Greubel, May 05 2019

seq(n!*(sum(1/k, k = 1 .. n)+(1/4)*n*(n-5)), n = 2 .. 21); # Emeric Deutsch, Oct 10 2007

Table[n!*(n*(n-5)/4 + HarmonicNumber[n]), {n,2,25}] (* G. C. Greubel, May 05 2019 *)

my(x='x+O('x^30)); concat([0], Vec(serlaplace( (2*x - 3*x^2 + 2*(1-x)^2*log(1-x))/(2*(-1+x)^3) ))) \\ G. C. Greubel, May 05 2019

[factorial(n)*(n*(n-5)/4 + harmonic_number(n)) for n in (2..25)] # G. C. Greubel, May 05 2019

a(n) = n! * (n*(n-5)/4 + 1 + 1/2 + ... + 1/n). - Emeric Deutsch, Oct 10 2007
E.g.f.: (2*x - 3*x^2 + 2*(1-x)^2 * log(1-x)) / (2*(-1+x)^3). - G. C. Greubel, May 05 2019
a(n) = 2 * Sum_{k>=1} k * A381529(n,k). - Alois P. Heinz, Feb 26 2025

A381531 Number of permutations of [n] having the maximal possible number of pairs of integers i

Original entry on oeis.org

1, 1, 2, 1, 4, 5, 2, 14, 34, 34, 12, 132, 540, 1020, 888, 288, 4608, 28800, 89280, 143712, 113472, 34560, 760320, 6773760, 31449600, 81527040, 117089280, 85847040, 24883200, 721612800, 8709120000, 56783462400, 217205452800, 495200563200, 651939840000, 450584985600, 125411328000

Offset: 0

Alois P. Heinz, Feb 26 2025

nonn

The sequence has local minima at positions n in { A000217 }. The values at these positions are superfactorials (A000178).

			a(4) = 4: (1,4)(2)(3), (1,4)(2,3), (1,3,4)(2), (1,4,3)(2) with 2 pairs each.
a(6) = 2: (1,5,6)(2,4)(3), (1,6,5)(2,4)(3) with 7 pairs each.

Alois P. Heinz, Table of n, a(n) for n = 0..406
Wikipedia, Inversion
Wikipedia, Permutation

Cf. A000178, A000217, A125811, A381529.

b:= proc(o, u, t) option remember; (p-> (d-> coeff(p, x, d)
      *x^d)(degree(p)))(expand(`if`(u+o=0, max(0, t-1)!,
      `if`(t>0, b(u+o, 0$2)*(t-1)!, 0)+add(x^(u+j-1)*
        b(o-j, u+j-1, t+1), j=`if`(t=0, 1, 1..o)))))
    end:
a:= n-> coeffs(b(n, 0$2)):
seq(a(n), n=0..36);

a(n) = A381529(n,A125811(n)-1).

a(A000217(n)) = A000178(n-1) for n>=1.

A381539 Number of permutations of [n] having exactly one pair of integers i

Original entry on oeis.org

0, 0, 0, 1, 5, 21, 89, 408, 2106, 12529, 86579, 691287, 6296333, 64454418, 731532528, 9101244205, 122993164505, 1792140943473, 27987008885201, 466072881110268, 8241676745580774, 154187446760870761, 3042028843184493887, 63114652818792762987, 1373581948592359961909

Offset: 0

Alois P. Heinz, Feb 26 2025

nonn

			a(4) = 5: (1)(2,4)(3), (1,2,4)(3), (1,4,2)(3), (1,3)(2)(4), (1,3)(2,4).

Alois P. Heinz, Table of n, a(n) for n = 0..300
Wikipedia, Inversion
Wikipedia, Permutation

Column k=1 of A381529.

b:= proc(o, u, t) option remember; series(`if`(u+o=0, max(0, t-1)!,
     `if`(t>0, b(u+o, 0$2)*(t-1)!, 0)+add(x^(u+j-1)*
        b(o-j, u+j-1, t+1), j=`if`(t=0, 1, 1..o))), x, 2)
    end:
a:= n-> coeff(b(n, 0$2), x, 1):
seq(a(n), n=0..25);

A381545 Number of permutations of [n] having exactly n pairs of integers i

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 28, 239, 2789, 24970, 247089, 2289028, 23926282, 244031780, 2795283827, 32671509063, 426329260855, 5714045982473, 86176948036417, 1327311505233240, 22831768389870460, 401597165962560396, 7782893107559342148, 153285768850390602735, 3316598607281771351415

Offset: 0

Alois P. Heinz, Feb 26 2025

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..140

Main diagonal of A381529.

b:= proc(o, u, t, k) option remember; `if`(u+o=0, `if`(k=0,
       max(0, t-1)!, 0), `if`(t>0, b(u+o, 0$2, k)*(t-1)!, 0)+
       add(`if`(k+1 b(n, 0$2, n):
seq(a(n), n=0..30);

a(n) = A381529(n,n).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A126673 Third diagonal of A126671.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A381531 Number of permutations of [n] having the maximal possible number of pairs of integers i

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A381539 Number of permutations of [n] having exactly one pair of integers i

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A381545 Number of permutations of [n] having exactly n pairs of integers i

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula