login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003517 Number of permutations of [n+1] with exactly 1 increasing subsequence of length 3.
(Formerly M4177)
35

%I M4177

%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

%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

%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 Daniel Birmajer, Juan B. Gil, 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 D. 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="http://dx.doi.org/10.1021/ci00026a012">Enumeration of polyene hydrocarbons: a complete mathematical solution</a>, J. Chem. Inf. Comput. Sci., 35 (1995) 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., 35 (1995) 743-751. [Annotated scanned copy]

%H H. H. 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 (2010), No. 2, pp. 265-284 (see 4.3 p. 277).

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

%H R. 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="http://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 N. Lygeros, O. 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. 13 (2010) # 10.7.4.

%H J. Noonan and D. 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 J. 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. 152 (1996), no. 1-3, 307-313.

%H Ran Pan, 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="http://dx.doi.org/10.1016/0012-365X(76)90009-1">A Catalan triangle</a>, Discrete Math. 14 (1976), no. 1, 83-90.

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

%H _Zoran Sunic_, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v10i1n5">Self describing sequences and the Catalan family tree</a>, Elect. J. Combin., 10 (No. 1, 2003).

%F a(n) = 6*C(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(Catalan(i)*Catalan(j)*Catalan(k), i>=1,j>=1,k>=1, i+j+k=n+1).

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

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

%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 Cf. A001089, A084249, A000108, A000245, A002057, A000344, A000588, A003518, A003519, A001392.

%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

%O 2,2

%A _N. J. A. Sloane_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 13:38 EDT 2018. Contains 316361 sequences. (Running on oeis4.)