|
|
A051286
|
|
Whitney number of level n of the lattice of the ideals of the fence of order 2n.
|
|
41
|
|
|
1, 1, 2, 5, 11, 26, 63, 153, 376, 931, 2317, 5794, 14545, 36631, 92512, 234205, 594169, 1510192, 3844787, 9802895, 25027296, 63972861, 163701327, 419316330, 1075049011, 2758543201, 7083830648, 18204064403, 46812088751, 120452857976
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
A Chebyshev transform of the central trinomial numbers A002426: image of 1/sqrt(1-2x-3x^2) under the mapping that takes g(x) to (1/(1+x^2))*g(x/(1+x^2)). - Paul Barry, Jan 31 2005
This is the second kind of Whitney numbers, which count elements, not to be confused with the first kind, which sum Mobius functions. - Thomas Zaslavsky, May 07 2008
Apply the Riordan array (1/(1-x+x^2),x/(1-x+x^2)) to the aerated central binomial coefficients with g.f. 1/sqrt(1-4x^2).
a(n) is the number of lattice paths in L[n]. The members of L[n] are lattice paths of weight n that start at (0,0), end on the horizontal axis and whose steps are of the following four kinds: an (1,0)-step h with weight 1, an (1,0)-step H with weight 2, a (1,1)-step U with weight 2, and a (1,-1)-step D with weight 1. The weight of a path is the sum of the weights of its steps. Example: a(3)=5 because we have hhh, hH, Hh, UD, and DU; a(4)=11 because we have hhhh, hhH, hHh, Hhh, HH, hUD, UhD, UDh, hDU, DhU, and DUh (see the Bona-Knopfmacher reference).
Apparently the number of peakless grand Motzkin paths of length n. - David Scambler, Jul 04 2013
A bijection between L[n] (as defined above) and peakless grand Motzkin paths of length n is now given in arXiv:2002.12874. - Sergi Elizalde, Jul 14 2021
a(n) is also the number of unimodal bargraphs with a centered maximum (i.e., whose column heights are weakly increasing in the left half and weakly decreasing in the right half) and semiperimeter n+1. - Sergi Elizalde, Jul 14 2021
|
|
LINKS
|
Andrei Asinowski, Axel Bacher, Cyril Banderier and Bernhard Gittenberger, Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Enumerative Aspects, in International Conference on Language and Automata Theory and Applications, S. Klein, C. Martín-Vide, D. Shapira (eds), Springer, Cham, pp 195-206, 2018.
Jean-Luc Baril, Nathanaël Hassler, Sergey Kirgizov, and José L. Ramírez, Grand zigzag knight's paths, arXiv:2402.04851 [math.CO], 2024.
Edyta Hetmaniok, Barbara Smoleń and Roman Wituła, The Stirling triangles, Proceedings of the Symposium for Young Scientists in Technology, Engineering and Mathematics (SYSTEM 2017), Kaunas, Lithuania, April 28, 2017, p. 35-41.
|
|
FORMULA
|
G.f.: 1/sqrt(1 - 2*x - x^2 - 2*x^3 + x^4).
a(n) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*(-1)^k*A002426(n-2k). - Paul Barry, Jan 31 2005
a(n) = Sum_{k=0..n} C(n-k, k)^2.
Limit_{n->oo} a(n+1)/a(n) = (sqrt(5)+3)/2.
G.f.: 1/sqrt((1+x+x^2)*(1-3*x+x^2)). (End)
a(n) = Sum_{k=0..n} (C(k,k/2)*(1+(-1)^k)/2) * Sum_{j=0..n} (-1)^((n-j)/2)*C((n+j)/2,j)*((1+(-1)^(n-j))/2)*C(j,k). -Paul Barry, Mar 31 2010
G.f.: exp( Sum_{n>=1} (x^n/n)*Sum_{k=0..n} C(2n,2k)*x^k ). - Paul D. Hanna, Mar 18 2011
D-finite with recurrence: n*a(n) - (2*n-1)*a(n-1) - (n-1)*a(n-2) - (2*n-3)*a(n-3) + (n-2)*a(n-4) = 0. - R. J. Mathar, Dec 17 2011
The g.f. A(x) satisfies the differential equation (1-2*x-x^2-2*x^3+x^4)*A'(x) = (1+x+3*x^2-2*x^3)*A(x), from which the recurrence conjectured by Mathar follows. - Emanuele Munarini, Dec 18 2017
a(n) ~ phi^(2*n + 2) / (2 * 5^(1/4) * sqrt(Pi*n)), where phi = A001622 = (1 + sqrt(5))/2 is the golden ratio. - Vaclav Kotesovec, Jan 05 2013, simplified Dec 18 2017
G.f.: Sum_{n>=0} x^n * Sum_{k=0..n} C(n,k)^2 * x^k.
G.f.: Sum_{n>=0} x^n *[Sum_{k>=0} C(n+k,k)^2 * x^k] * (1-x)^(2*n+1).
G.f.: Sum_{n>=0} x^(2*n) * [Sum_{k>=0} C(n+k,k)^2 * x^k].
G.f.: Sum_{n>=0} x^(2*n) * [Sum_{k=0..n} C(n,k)^2 * x^k] /(1-x)^(2n+1).
(End)
|
|
EXAMPLE
|
a(3) = 5 because the ideals of size 3 of the fence F(6) = { x1 < x2 > x3 < x4 > x5 < x6 } are x1*x3*x5, x1*x2*x3, x3*x4*x5, x1*x5*x6, x3*x5*x6.
|
|
MAPLE
|
seq( sum('binomial(i-k, k)*binomial(i-k, k)', 'k'=0..floor(i/2)), i=0..30 ); # Detlef Pauly (dettodet(AT)yahoo.de), Nov 09 2001
# second Maple program:
a:= proc(n) option remember; `if`(n<4, [1$2, 2, 5][n+1],
((2*n-1)*a(n-1)+(n-1)*a(n-2)+(2*n-3)*a(n-3)-(n-2)*a(n-4))/n)
end:
|
|
MATHEMATICA
|
CoefficientList[Series[1/Sqrt[1-2*x-x^2-2*x^3+x^4], {x, 0, 20}], x] (* Vaclav Kotesovec, Jan 05 2013 *)
a[n_] := HypergeometricPFQ[ {(1-n)/2, (1-n)/2, -n/2, -n/2}, {1, -n, -n}, 16]; Table[a[n], {n, 0, 29}] (* Jean-François Alcover, Feb 26 2013 *)
|
|
PROG
|
(PARI) a(n)=polcoeff(1/sqrt((1+x+x^2)*(1-3*x+x^2)+x*O(x^n)), n)
(PARI) {a(n)=polcoeff( exp(sum(m=1, n, sum(k=0, m, binomial(2*m, 2*k)*x^k) *x^m/m) +x*O(x^n)), n)} /* Paul D. Hanna, Mar 18 2011 */
(PARI) {a(n)=local(A=1); A=sum(m=0, n, x^m*sum(k=0, m, binomial(m, k)^2*x^k) +x*O(x^n)); polcoeff(A, n)} \\ Paul D. Hanna, Sep 05 2014
(PARI) {a(n)=local(A=1+x); A=sum(m=0, n, x^m*sum(k=0, n, binomial(m+k, k)^2*x^k) * (1-x)^(2*m+1) +x*O(x^n)); polcoeff(A, n)} \\ Paul D. Hanna, Sep 05 2014
(PARI) {a(n)=local(A=1+x); A=sum(m=0, n\2, x^(2*m) * sum(k=0, n, binomial(m+k, k)^2*x^k) +x*O(x^n)); polcoeff(A, n)} \\ Paul D. Hanna, Sep 05 2014
(PARI) {a(n)=local(A=1+x); A=sum(m=0, n\2, x^(2*m) * sum(k=0, m, binomial(m, k)^2*x^k) / (1-x +x*O(x^n))^(2*m+1) ); polcoeff(A, n)} \\ Paul D. Hanna, Sep 05 2014
(Maxima) makelist(sum(binomial(n-k, k)^2, k, 0, floor(n/2)), n, 0, 40); /* Emanuele Munarini, Mar 01 2011 */
(Python)
from sympy import binomial
def a(n): return sum(binomial(n - k, k)**2 for k in range(n//2 + 1))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|