A003517 - OEIS

%I M4177 #152 Jan 28 2025 00:02:47

%S 1,6,27,110,429,1638,6188,23256,87210,326876,1225785,4601610,17298645,

%T 65132550,245642760,927983760,3511574910,13309856820,50528160150,

%U 192113383644,731508653106,2789279908316,10649977831752,40715807302800,155851062397940,597261490737912

%N Number of permutations of [n+1] with exactly 1 increasing subsequence of length 3.

%C a(n-4) = number of n-th generation vertices in the tree of sequences with unit increase labeled by 5 (cf. _Zoran Sunic_ reference). - _Benoit Cloitre_, Oct 07 2003

%C Number of standard tableaux of shape (n+3,n-2). - _Emeric Deutsch_, May 30 2004

%C a(n) = A214292(2*n,n-3) for n > 2. - _Reinhard Zumkeller_, Jul 12 2012

%C a(n) is the number of North-East paths from (0,0) to (n,n) that cross the diagonal y = x horizontally exactly once. By symmetry, it is also the number of North-East paths from (0,0) to (n,n) that cross the diagonal y = x vertically exactly once. Details can be found in Section 3.3 in Pan and Remmel's link. - _Ran Pan_, Feb 02 2016

%C a(n) is the number of permutations pi of [n+3] such that s(pi)=321456...(n+3), where s denotes West's stack-sorting map. - _Colin Defant_, Jan 14 2019

%C a(n) is also the number of permutations of [n+1] avoiding the pattern 321. For permutations avoiding any of the other permutations of [3] (that is, any of 132, 213, 231, or 312) see A002054. - _N. J. A. Sloane_, Nov 26 2022

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

%H Vincenzo Librandi, <a href="/A003517/b003517.txt">Table of n, a(n) for n = 2..1000</a>

%H Anwar Al Ghabra, K. Gopala Krishna, Patrick Labelle, and Vasilisa Shramchenko, <a href="https://arxiv.org/abs/2301.09765">Enumeration of multi-rooted plane trees</a>, arXiv:2301.09765 [math.CO], 2023.

%H Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, <a href="https://arxiv.org/abs/1707.09918">Bounce statistics for rational lattice paths</a>, arXiv:1707.09918 [math.CO], 2017, p. 9.

%H David Callan, <a href="https://arxiv.org/abs/math/0211380">A recursive bijective approach to counting permutations...</a>, arXiv:math/0211380 [math.CO], 2002.

%H S. J. Cyvin, J. Brunvoll, E. Brendsdal, B. N. Cyvin, and E. K. Lloyd, <a href="https://doi.org/10.1021/ci00026a012">Enumeration of polyene hydrocarbons: a complete mathematical solution</a>, J. Chem. Inf. Comput. Sci., Vol. 35, No. 4 (1995), pp. 743-751.

%H S. J. Cyvin, J. Brunvoll, E. Brendsdal, B. N. Cyvin, and E. K. Lloyd, <a href="/A002057/a002057.pdf">Enumeration of polyene hydrocarbons: a complete mathematical solution</a>, J. Chem. Inf. Comput. Sci., Vol. 35, No. 4 (1995), pp. 743-751. [Annotated scanned copy]

%H Olivier Danvy, <a href="https://arxiv.org/abs/2412.03127">Summa Summarum: Moessner's Theorem without Dynamic Programming</a>, arXiv:2412.03127 [cs.DM], 2024. See p. 31.

%H Hilmar Haukur Gudmundsson, <a href="http://puma.dimai.unifi.it/21_2/9_Gudmundsson.pdf">Dyck paths, standard Young tableaux, and pattern avoiding permutations</a>, PU. M. A., Vol. 21 , No. 2 (2010), pp. 265-284 (see 4.3 p. 277).

%H Richard K. Guy, <a href="/A005555/a005555.pdf">Letter to N. J. A. Sloane, May 1990</a>.

%H Richard K. Guy, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/GUY/catwalks.html">Catwalks, sandsteps and Pascal pyramids</a>, J. Integer Sequences, Vol. 3 (2000), Article 00.1.6.

%H V. E. Hoggatt, Jr., <a href="/A005676/a005676.pdf">7-page typed letter to N. J. A. Sloane with suggestions for new sequences</a>, circa 1977.

%H V. E. Hoggatt, Jr. and M. Bicknell, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/14-5/hoggatt1.pdf">Catalan and related sequences arising from inverses of Pascal's triangle matrices</a>, Fib. Quart., 14 (1976), 395-405.

%H Markus Kuba and Alois Panholzer, <a href="http://ajc.maths.uq.edu.au/pdf/74/ajc_v74_p216.pdf">Stirling permutations containing a single pattern of length three</a>, Australasian Journal of Combinatorics, Vol. 74, No. 2 (2019), pp. 216-239.

%H Nik Lygeros and Olivier Rozier, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Lygeros/lygeros5.html">A new solution to the equation tau(rho) == 0 (mod p)</a>, J. Int. Seq., Vol. 13 (2010), Article 10.7.4.

%H John Noonan, <a href="http://dx.doi.org/10.1016/0012-365X(95)00247-T">The number of permutations containing exactly one increasing subsequence of length three</a>, Discrete Math., Vol. 152, No. 1-3 (1996), pp. 307-313.

%H John Noonan and Doron Zeilberger, <a href="https://arxiv.org/abs/math/9808080">The Enumeration of Permutations With a Prescribed Number of "Forbidden" Patterns</a>, arXiv:math/9808080 [math.CO], 1998.

%H Ran Pan and Jeffrey B. Remmel, <a href="http://arxiv.org/abs/1601.07988">Paired patterns in lattice paths</a>, arXiv:1601.07988 [math.CO], 2016.

%H L. W. Shapiro, <a href="https://doi.org/10.1016/0012-365X(76)90009-1">A Catalan triangle</a>, Discrete Math., Vol. 14, No. 1 (1976), pp. 83-90.

%H L. W. Shapiro, <a href="/A003517/a003517.pdf">A Catalan triangle</a>, Discrete Math., Vol. 14, No. 1 (1976), pp. 83-90. [Annotated scanned copy]

%H Zoran Sunic, <a href="https://doi.org/10.37236/1745">Self describing sequences and the Catalan family tree</a>, Elect. J. Combin., Vol. 10 (2003), Article N5.

%F a(n) = 6*binomial(2*n+1, n-2)/(n+4).

%F G.f.: x^2*C(x)^6, where C(x) is g.f. for the Catalan numbers (A000108). - _Emeric Deutsch_, May 30 2004

%F E.g.f.: exp(2*x)*(Bessel_I(2,2*x) - Bessel_I(4,2*x)). - _Paul Barry_, Jun 04 2007

%F Let A be the Toeplitz matrix of order n defined by: A[i,i-1]=-1, A[i,j]=Catalan(j-i), (i<=j), and A[i,j]=0, otherwise. Then, for n >= 5, a(n-3) = (-1)^(n-5)*coeff(charpoly(A,x),x^5). - _Milan Janjic_, Jul 08 2010

%F a(n) = Sum_{i>=1, j>=1, k>=1, i+j+k=n+1} Catalan(i)*Catalan(j)*Catalan(k). _T. D. Noe_, Dec 22 2010

%F D-finite with recurrence -(n+4)*(n-2)*a(n) + 2*n*(2*n+1)*a(n-1) = 0. - _R. J. Mathar_, Dec 04 2012

%F From _Amiram Eldar_, Jan 02 2022: (Start)

%F Sum_{n>=2} 1/a(n) = 7/2 - 34*Pi/(27*sqrt(3)).

%F Sum_{n>=2} (-1)^n/a(n) = 828*log(phi)/(25*sqrt(5)) - 2819/450, where phi is the golden ratio (A001622). (End)

%F a(n) ~ 3*4^(n+1)/(n^(3/2)*sqrt(Pi)). - _Stefano Spezia_, Apr 17 2024

%F a(n) = A000108(n+3) - 4*A000108(n+2) + 3*A000108(n+1). - _Taras Goy_, Jul 15 2024

%F a(n) = 6*(2*n+1)!*(n-1)!/((2*n-4)!*(n+4)!)*A000108(n-2). - _Taras Goy_, Dec 21 2024

%e a(3)=6 because the only permutations of 1234 with exactly 1 increasing subsequence of length 3 are 1423, 4123, 1342, 2314, 2341, 3124.

%p A003517List := proc(m) local A, P, n; A := [1]; P := [1,1,1,1,1];

%p for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), P[-1]]);

%p A := [op(A), P[-1]] od; A end: A003517List(25); # _Peter Luschny_, Mar 26 2022

%t f[x_] = (Sqrt[1 - 4 x] - 1)^6/(64 x^4); CoefficientList[Series[f[x], {x, 0, 25}], x][[3 ;; 26]] (* _Jean-François Alcover_, Jul 13 2011, after g.f. *)

%t Table[6 Binomial[2n+1,n-2]/(n+4),{n,2,30}] (* _Harvey P. Dale_, Feb 27 2012 *)

%o (PARI) a(n)=6*binomial(2*n+1,n-2)/(n+4) \\ _Charles R Greathouse IV_, May 18 2015

%o (PARI) x='x+O('x^50); Vec(x^2*((1-(1-4*x)^(1/2))/(2*x))^6) \\ _Altug Alkan_, Nov 01 2015

%Y T(n, n+6) for n=0, 1, 2, ..., array T as in A047072.

%Y See also A002054.

%Y Cf. A001089, A084249, A000108, A000245, A002057, A000344, A000588, A003518, A003519, A001392, A001622, A214292.

%Y First differences are in A026017.

%Y A diagonal of any of the essentially equivalent arrays: A009766, A030237, A033184, A059365, A099039, A106566, A130020, A047072.

%K nonn,easy,nice,changed

%O 2,2

%A _N. J. A. Sloane_