|
|
A005717
|
|
Construct triangle in which n-th row is obtained by expanding (1 + x + x^2)^n and take the next-to-central column.
(Formerly M1612)
|
|
33
|
|
|
1, 2, 6, 16, 45, 126, 357, 1016, 2907, 8350, 24068, 69576, 201643, 585690, 1704510, 4969152, 14508939, 42422022, 124191258, 363985680, 1067892399, 3136046298, 9217554129, 27114249960, 79818194925, 235128465026, 693085098852, 2044217638456, 6032675068061
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Number of ordered trees with n+1 edges, having root of even degree and nonroot nodes of outdegree at most 2. - Emeric Deutsch, Aug 02 2002
The connection to Motzkin numbers comes from the Lagrange inversion formula. - Michael Somos, Oct 10 2003
Number of horizontal steps in all Motzkin paths of length n. - Emeric Deutsch, Nov 09 2003
Number of UHD's in all Motzkin paths of length n+2 (here U=(1,1), H=(1,0) and D=(1,-1)). Example: a(2)=2 because in the nine Motzkin paths of length 4, HHHH, HHUD, HUDH, H(UHD), UDHH, UDUD, (UHD)H, UHHD and UUDD, we have altogether two UHD's (shown between parentheses). - Emeric Deutsch, Dec 26 2003
Number of ordered trees with n+1 edges, having exactly one leaf at even height. Number of Dyck path of semilength n+1, having exactly one peak at even height. Example: a(3)=6 because we have uuu(ud)ddd, u(ud)dudud, udu(ud)dud, ududu(ud)d, u(ud)uuddd and uuudd(ud)d (here u=(1,1),d=(1,-1) and the unique peak at even height is shown between parentheses). - Emeric Deutsch, Mar 10 2004
a(n) is the number of Dyck (n+1)-paths containing exactly one UDU. - David Callan, Jul 15 2004
Number of peaks in all Motzkin paths of length n+1. - Emeric Deutsch, Sep 01 2004
This is a kind of Motzkin transform of A059841 because the substitution x -> x*A001006(x) in the independent variable of the g.f. of A059841 generates 1,0,1,2,6,16,... that is 1,0 followed by this sequence here. - R. J. Mathar, Nov 08 2008
a(n) is the number of lattice paths avoiding N^(>=3) from (0,0) to (n,n). - Shanzhen Gao, Apr 20 2010
a(n+1) is the number of binary strings having n 0's and n 1's and no appearance of 000. For example, for n = 1, there 2 strings: 01 and 10. For n = 2, there are 6: 0011, 0101, 0110, 1001, 1010, 1100. - Toby Gottfried, Sep 12 2011
a(n) is the number of paths in the half-plane x>=0, from (0,0) to (n,1), and consisting of steps U=(1,1), D=(1,-1) and H=(1,0). For example, for n=3, we have the 6 paths HHU, HUH, UDU, UUD, UHH, DUU. - José Luis Ramírez Ramírez, Apr 19 2015
|
|
REFERENCES
|
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 78.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{k=1..n} T(k, k-1), where T is the array defined in A025177.
G.f.: 2*x/(1-2*x-3*x^2+(1-x)*sqrt(1-2*x-3*x^2)). - Emeric Deutsch, Aug 14 2002
E.g.f.: exp(x) * I_1(2x), where I_1 is the Bessel function. - Michael Somos, Sep 09 2002
a(n) = Sum_{k=0..floor((n-1)/3)} (-1)^k * binomial(n,k) * binomial(2n-2-3k, n-1). - David Callan, Jul 03 2006
a(n) = n*Sum_{k=0..floor((n-1)/2), C(n-1,2k)*C(k)}, C(n) = A000108(n).
a(n) = Sum_{k=0..floor((n-1)/2)} (2k+1)*C(n,2k+1)*C(k).
a(n) = Sum_{k=0..n-1} ( Sum_{j=0..floor(k/2)} C(k,2j)*C(2j+1,j) ). (End)
a(n) = Sum_{i=0..floor(n/2)} C(n+1,n-i) * C(n-i,i). - Shanzhen Gao, Apr 20 2010
D-finite with recurrence: (n+1)*a(n) - 3*n*a(n-1) - (n+3)*a(n-2) + 3*(n-2)*a(n-3) = 0. - R. J. Mathar, Nov 28 2011
0 = a(n) * 3*(n+1)*(n+2) + a(n+1) * (n+2)*(2*n+3) - a(n+2) * (n+1)*(n+3) for all n in Z. - Michael Somos, Apr 03 2014
Working with an offset of 0, a(n) = [x^n](1 + x + x^2)^(n+1); binomial transform is A076540. - Peter Bala, Jun 15 2015
a(n) = Sum_{k=0..n-1} binomial(n,k)*binomial(n-k, k+1) [Krymski and Okhotin]. - Michel Marcus, Dec 04 2020
|
|
EXAMPLE
|
G.f. = x + 2*x^2 + 6*x^3 + 16*x^4 + 45*x^5 + 126*x^6 + 357*x^7 + ...
|
|
MAPLE
|
seq(add(binomial(i, k) *binomial(i-k, k+1), k=0..floor(i/2)), i=1..30); # Detlef Pauly (dettodet(AT)yahoo.de), Nov 09 2001
M:= proc(n) option remember; `if` (n<2, 1, (3*(n-1)*M(n-2) +(2*n+1) *M(n-1))/ (n+2)) end: A005717 := n -> n*M(n-1):
a := n -> simplify(GegenbauerC(n, -n-1, -1/2)):
|
|
MATHEMATICA
|
Table[Coefficient[Expand[(1+x+x^2)^n], x, n-1], {n, 1, 40}]
Table[n*Hypergeometric2F1[(1 - n)/2, 1 - n/2, 2, 4], {n, 29}] (* Arkadiusz Wesolowski, Aug 13 2012 *)
|
|
PROG
|
(PARI) {a(n) = if( n<0, 0, polcoeff( (1 + x + x^2)^n, n-1))}; /* Michael Somos, Sep 09 2002 */
(PARI) {a(n) = if( n<0, 0, n * polcoeff( serreverse( x / (1 + x + x^2) + x * O(x^n)), n))}; /* Michael Somos, Oct 10 2003 */
(PARI)
N=10^3; x='x+'x*O('x^N);
gf = 2*x/(1-2*x-3*x^2+(1-x)*sqrt(1-2*x-3*x^2));
v005717 = Vec(gf);
(Sage, Python)
def A():
a, b, n = 0, 1, 1
while True:
yield b
n += 1
a, b = b, (3*(n-1)*n*a+(2*n-1)*n*b)//((n+1)*(n-1))
(Maxima) makelist(ultraspherical(n, -n-1, -1/2), n, 0, 12); /* Emanuele Munarini, Oct 20 2016 */
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|