|
| |
|
|
A001791
|
|
a(n) = binomial coefficient C(2n, n-1).
(Formerly M3500 N1421)
|
|
132
|
|
|
|
0, 1, 4, 15, 56, 210, 792, 3003, 11440, 43758, 167960, 646646, 2496144, 9657700, 37442160, 145422675, 565722720, 2203961430, 8597496600, 33578000610, 131282408400, 513791607420, 2012616400080, 7890371113950, 30957699535776, 121548660036300, 477551179875952
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Number of peaks at even level in all Dyck paths of semilength n+1. Example: a(2)=4 because UDUDUD, UDUU*DD, UU*DDUD, UU*DU*DD, UUUDDD, where U=(1,1), D=(1,-1) and the peaks at even level are shown by *. - Emeric Deutsch, Dec 05 2003
Also number of long ascents (i.e., ascents of length at least two) in all Dyck paths of semilength n+1. Example: a(2)=4 because in the five Dyck paths of semilength 3, namely UDUDUD, UD(UU)DD, (UU)DDUD, (UU)DUDD and (UUU)DDD, we have four long ascents (shown between parentheses). Here U=(1,1) and D=(1,-1). Also number of branch nodes (i.e., vertices of outdegree at least two) in all ordered trees with n+1 edges. - Emeric Deutsch, Feb 22 2004
Number of lattice paths from (0,0) to (n,n) with steps E=(1,0) and N=(0,1) which touch or cross the line x-y=1. Example: For n=2 these are the paths EENN, ENEN, ENNE and NEEN. - Herbert Kociemba, May 23 2004
Narayana transform (A001263) of [1, 3, 5, 7, 9, ...] = (1, 4, 15, 56, 210, ...). Row sums of triangles A136534 and A136536. - Gary W. Adamson, Jan 04 2008
Starting with offset 1 = the Catalan sequence starting (1, 2, 5, 14, ...) convolved with A000984: (1, 2, 6, 20, ...). - Gary W. Adamson, May 17 2009
Also number of peaks plus number of valleys in all Dyck n-paths. - David Scambler, Oct 08 2012
Apparently counts UDDUD in all Dyck paths of semilength n+2. - David Scambler, Apr 22 2013
Apparently the number of peaks strictly left of the midpoint in all Dyck paths of semilength n+1. - David Scambler, Apr 30 2013
For n>0, a(n) is the number of compositions of n into at most n parts if zeros are allowed as parts (so-called "weak" compositions). - L. Edson Jeffery, Jul 24 2014
Number of paths in the half-plane x >= 0, from (0,0) to (2n,2), and consisting of steps U=(1,1) and D=(1,-1). For example, for n=2, we have the 4 paths: UUUD, UUDU, UDUU, DUUU. - José Luis Ramírez Ramírez, Apr 19 2015
For n>1, 1/a(n) is the probability that when a stick is broken up at n points independently and uniformly chosen at random along its length any triple of pieces of the n+1 pieces can form a triangle. The corresponding probability for the existence of at least one triple is A339392(n)/A339393(n). - Amiram Eldar, Dec 04 2020
a(n) is the number of lattice paths of 2n steps taken from the step set {U=(1,1), D=(1,-1)} that start at the origin, never go below the x-axis, and end strictly above the x-axis; more succinctly, proper left factors of Dyck paths. For example, a(2)=4 counts UUUU, UUUD, UUDU, UDUU. - David Callan and Emeric Deutsch, Jan 25 2021
Also the number of integer compositions of 2n+1 with alternating sum -1, where the alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. For example, the a(1) = 1 through a(3) = 15 compositions are:
(1,2) (2,3) (3,4)
(1,3,1) (1,4,2)
(1,1,1,2) (2,4,1)
(1,2,1,1) (1,1,2,3)
(1,2,2,2)
(1,3,2,1)
(2,1,1,3)
(2,2,1,2)
(2,3,1,1)
(1,1,1,3,1)
(1,2,1,2,1)
(1,3,1,1,1)
(1,1,1,1,1,2)
(1,1,1,2,1,1)
(1,2,1,1,1,1)
The following relate to these compositions.
- The unordered version is A000070.
- Allowing any negative alternating sum gives A000346.
- The opposite (positive 1) version is A000984.
- The version for reverse-alternating sum is also A001791 (this sequence).
- Taking alternating sum -2 instead of -1 gives A002054.
- The shifted version for alternating sum 0 is counted by A088218 and ranked by A344619.
Equivalently, a(n) counts binary numbers with 2n+1 digits and one more 0 than 1's. For example, the a(2) = 4 binary numbers are: 10001, 10010, 10100, 11000.
(End)
|
|
|
REFERENCES
|
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 828.
Cornelius Lanczos, Applied Analysis, Prentice-Hall, Englewood Cliffs, NJ, 1956, p. 517.
R. C. Mullin, E. Nemeth and P. J. Schellenberg, The enumeration of almost cubic maps, pp. 281-295 in Proceedings of the Louisiana Conference on Combinatorics, Graph Theory and Computer Science. Vol. 1, edited R. C. Mullin et al., 1970.
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
|
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Milan Janjic and Boris Petkovic, A Counting Function, arXiv preprint arXiv:1301.4550 [math.CO], 2013.
|
|
|
FORMULA
|
Convolution of A001700 (central binomial of odd order) and A000108 (Catalan): a(n+1) = Sum_{k=0..n} C(k)*binomial(2*(n-k)+1, n-k), C(k): Catalan. - Wolfdieter Lang
E.g.f.: exp(2x) I_1(2x), where I_1 is Bessel function. - Michael Somos, Sep 08 2002
a(n) = Sum_{k=0..n} C(n, k)*C(n, k+1). - Paul Barry, May 15 2003
a(n) = Sum_{i=1..n} binomial(i+n-1, n).
G.f.: (1-2x-sqrt(1-4x))/(2x*sqrt(1-4x)). - Emeric Deutsch, Dec 05 2003
a(n) = (1/(2*Pi))*Integral_{x=0..4} (x^n*(x-2)/sqrt(x(4-x))) is the moment sequence representation. - Paul Barry, Jan 11 2007
Starting (1, 4, 15, 56, 210, ...) gives the binomial transform of A025566 starting (1, 3, 8, 22, 61, 171, ...). - Gary W. Adamson, Sep 01 2007
D-finite with recurrence: (n-1)*(n+1)*a(n) = 2*n*(2n-1)*a(n-1). - R. J. Mathar, Dec 17 2011
G.f.: -1/(2*x) - G(0) where G(k) = 1 - 1/(2*x - 8*x^3*(2*k+1)/(4*x^2*(2*k+1)- (k+1)/G(k+1))); (continued fraction, 3rd kind, 3-step);
E.g.f.: BesselI(1,2*x)*exp(2*x) = x*G(0) where G(k) = 1 + 2*x*(4*k+3)/((2*k+1)*(2*k+3) - x*(2*k+1)*(2*k+3)*(4*k+5)/(x*(4*k+5) + 2*(k+1)*(k+2)/G(k+1))); (continued fraction, 3rd kind, 3-step).
(End)
a(n) = Sum_{i=1..n} binomial(2*i-2,i-1)*binomial(2*(n-i+1),n-i+2)/(n-i+1). - Vladimir Kruchinin, Sep 07 2015
L.g.f.: 1/(1 - x/(1 - x/(1 - x/(1 - x/(1 - x/(1 - ...)))))) = Sum_{n>=1} a(n)*x^n/n. - Ilya Gutkovskiy, May 10 2017
Sum_{n>=1} 1/a(n) = 1/3 + 5*Pi/(9*sqrt(3)). - Amiram Eldar, Dec 04 2020
Sum_{n>=1} (-1)^(n+1)/a(n) = 1/5 + 14*sqrt(5)*log(phi)/25, where log(phi) = A002390. - Amiram Eldar, Feb 20 2021
a(n) = Product_{i=1..(n - 1)} (((4*i + 6)*i + 2)/((i + 2)*i)), for n>=1. - Neven Sajko, Oct 10 2021
|
|
|
MATHEMATICA
|
Table[Binomial[2n, n-1], {n, 0, 30}] (* Harvey P. Dale, Jul 12 2012 *)
CoefficientList[ Series[(1 - 2x - Sqrt[1 - 4x])/(2x*Sqrt[1 - 4x]), {x, 0, 26}], x] (* Robert G. Wilson v, Aug 10 2018 *)
|
|
|
PROG
|
(PARI) a(n)=if(n<1, 0, (2*n)!/(n+1)!/(n-1)!)
(Maxima) A001791(n):=binomial(2*n, n-1)$
(GAP) List([0..30], n->Binomial(2*n, n-1)); # Muniru A Asiru, Aug 09 2018
|
|
|
CROSSREFS
|
A345197 counts compositions by length and alternating sum.
Cf. A000070, A000302, A000346, A002054, A008549, A032443, A088218, A097805, A163493, A202736, A345910.
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
