|
| |
|
|
A003517
|
|
Number of permutations of [n+1] with exactly 1 increasing subsequence of length 3.
(Formerly M4177)
|
|
42
|
|
|
|
1, 6, 27, 110, 429, 1638, 6188, 23256, 87210, 326876, 1225785, 4601610, 17298645, 65132550, 245642760, 927983760, 3511574910, 13309856820, 50528160150, 192113383644, 731508653106, 2789279908316, 10649977831752, 40715807302800, 155851062397940, 597261490737912
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
2,2
|
|
|
COMMENTS
|
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
Number of standard tableaux of shape (n+3,n-2). - Emeric Deutsch, May 30 2004
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
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
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
|
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
L. W. Shapiro, A Catalan triangle, Discrete Math., Vol. 14, No. 1 (1976), pp. 83-90. [Annotated scanned copy]
|
|
|
FORMULA
|
a(n) = 6*binomial(2*n+1, n-2)/(n+4).
E.g.f.: exp(2*x)*(Bessel_I(2,2*x) - Bessel_I(4,2*x)). - Paul Barry, Jun 04 2007
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
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
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
Sum_{n>=2} 1/a(n) = 7/2 - 34*Pi/(27*sqrt(3)).
Sum_{n>=2} (-1)^n/a(n) = 828*log(phi)/(25*sqrt(5)) - 2819/450, where phi is the golden ratio (A001622). (End)
|
|
|
EXAMPLE
|
a(3)=6 because the only permutations of 1234 with exactly 1 increasing subsequence of length 3 are 1423, 4123, 1342, 2314, 2341, 3124.
|
|
|
MAPLE
|
A003517List := proc(m) local A, P, n; A := [1]; P := [1, 1, 1, 1, 1];
for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), P[-1]]);
A := [op(A), P[-1]] od; A end: A003517List(25); # Peter Luschny, Mar 26 2022
|
|
|
MATHEMATICA
|
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. *)
Table[6 Binomial[2n+1, n-2]/(n+4), {n, 2, 30}] (* Harvey P. Dale, Feb 27 2012 *)
|
|
|
PROG
|
(PARI) x='x+O('x^50); Vec(x^2*((1-(1-4*x)^(1/2))/(2*x))^6) \\ Altug Alkan, Nov 01 2015
|
|
|
CROSSREFS
|
T(n, n+6) for n=0, 1, 2, ..., array T as in A047072.
Cf. A001089, A084249, A000108, A000245, A002057, A000344, A000588, A003518, A003519, A001392, A001622, A214292.
|
|
|
KEYWORD
|
nonn,easy,nice,changed
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
