A000507 Number of permutations of [n] with exactly 3 increasing runs of length at least 2.

61, 1385, 19028, 206276, 1949762, 16889786, 137963364, 1081702420, 8236142455, 61386982075, 450403628440, 3266265481144, 23480284103492, 167687984079924, 1191656966048088, 8436830209386360, 59563995267159825, 419628657826253805

Offset: 6

Author

N. J. A. Sloane

Keywords

• nonn
• easy

References

• F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 260.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Shaoshi Chen, Hanqian Fang, Sergey Kitaev, and Candice X.T. Zhang, Patterns in Multi-dimensional Permutations, arXiv:2411.02897 [math.CO], 2024. See p. 7.
• Index entries for linear recurrences with constant coefficients, signature (30, -385, 2776, -12418, 35908, -67818, 82552, -62109, 26190, -4725).

Crossrefs

From Johannes W. Meijer, May 24 2009: (Start)

The a(n) sequence equals the fourth left hand column of A008971.

The a(2*n) sequence equals the fourth left hand column of A160486.

(End)

Programs

Magma

[(3*7^n-(6*n-9)*5^n+(6*n^2-18*n+3)*3^n-4*n^3+18*n^2-8*n-15)/192: n in [6..30]]; // Vincenzo Librandi, Feb 09 2016

Mathematica

t[n_, 0] = 1; t[n_, k_] /; k > n/2 = 0; t[n_, k_] /; k <= n/2 := t[n, k] = (2k+1) t[n-1, k] + (n-2k+1) t[n-1, k-1]; a[n_] := t[n, 3]; Table[a[n], {n, 6, 23}] (* Jean-François Alcover, Feb 09 2016 *)

Formula

a(n) = (3*7^n-(6*n-9)*5^n+(6*n^2-18*n+3)*3^n-4*n^3+18*n^2-8*n-15)/192.

G.f.: x^6*(61 - 445*x + 963*x^2 - 675*x^3)/((1 - 5*x)^2*(1 - x)^4*(1 - 3*x)^3*(1 - 7*x)). - Stefano Spezia, Nov 09 2024

Extensions

Definition changed for clarity and for consistency with A008971, and formula and additional terms added by Jon E. Schoenfield, Mar 26 2010