login
Number of permutations of [n] with exactly 3 increasing runs of length at least 2.
(Formerly M5323 N2314)
3

%I M5323 N2314 #32 Nov 09 2024 17:00:31

%S 61,1385,19028,206276,1949762,16889786,137963364,1081702420,

%T 8236142455,61386982075,450403628440,3266265481144,23480284103492,

%U 167687984079924,1191656966048088,8436830209386360,59563995267159825,419628657826253805

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

%D F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 260.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Shaoshi Chen, Hanqian Fang, Sergey Kitaev, and Candice X.T. Zhang, <a href="https://arxiv.org/abs/2411.02897">Patterns in Multi-dimensional Permutations</a>, arXiv:2411.02897 [math.CO], 2024. See p. 7.

%H <a href="/index/Rec#order_10">Index entries for linear recurrences with constant coefficients</a>, signature (30, -385, 2776, -12418, 35908, -67818, 82552, -62109, 26190, -4725).

%F 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.

%F 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

%t 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 *)

%o (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

%Y From _Johannes W. Meijer_, May 24 2009: (Start)

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

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

%Y (End)

%K nonn,easy

%O 6,1

%A _N. J. A. Sloane_

%E Definition changed for clarity and for consistency with A008971, and formula and additional terms added by _Jon E. Schoenfield_, Mar 26 2010