login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

a(n) has same parity as Fibonacci(n+1) = A000045(n+1); see A107597. - Paul D. Hanna, May 22 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

From Paul Barry, Mar 31 2010: (Start)

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

Hankel transform is A174882. (End)

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

Vincenzo Librandi and Alois P. Heinz, Table of n, a(n) for n = 0..1000

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.

Andrei Asinowski, Axel Bacher, Cyril Banderier and Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Laboratoire d'Informatique de Paris Nord (LIPN 2019).

C. Banderier and P. Hitczenko, Enumeration and asymptotics of restricted compositions having the same number of parts, Disc. Appl. Math. 160 (18) (2012) 2542-2554. See Puzzle 3.1.

Jean-Luc Baril, Sergey Kirgizov, Rémi Maréchal, and Vincent Vajnovszki, Grand Dyck paths with air pockets, arXiv:2211.04914 [math.CO], 2022.

Paul Barry, On a Generalization of the Narayana Triangle, J. Int. Seq. 14 (2011) # 11.4.5.

Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.

Hacène Belbachir and Abdelghani Mehdaoui, Recurrence relation associated with the sums of square binomial coefficients, Quaestiones Mathematicae (2021) Vol. 44, Issue 5, 615-624.

M. Bona and A. Knopfmacher, On the probability that certain compositions have the same number of parts, Ann. Comb., 14 (2010), 291-306.

Steffen Eger, On the Number of Many-to-Many Alignments of N Sequences, arXiv:1511.00622 [math.CO], 2015.

Steffen Eger, The Combinatorics of Weighted Vector Compositions, arXiv:1704.04964 [math.CO], 2017.

Sergi Elizalde, The degree of symmetry of lattice paths, arXiv:2002.12874 [math.CO], 2021.

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.

Ivo L. Hofacker, Christian M. Reidys, and Peter F. Stadler, Symmetric circular matchings and RNA folding. Discr. Math., 312:100-112, 2012. See Prop. 5, C_l^{1}(z).

E. Munarini and N. Zagaglia Salvi, On the Rank Polynomial of the Lattice of Order Ideals of Fences and Crowns, Discrete Mathematics 259 (2002), 163-177.

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

From Paul D. Hanna, May 22 2005: (Start)

a(n) = Sum_{k=0..n} C(n-k, k)^2.

Lim_{n->infinity} 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} A049310(n, k)^2. - Philippe Deléham, Nov 21 2005

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

Logarithmic derivative equals A185828. - 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

From Paul D. Hanna, Sep 05 2014: (Start)

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:

seq(a(n), n=0..35); # Alois P. Heinz, Aug 11 2016

MATHEMATICA

Table[Sum[Binomial[n-k, k]^2, {k, 0, Floor[n/2]}], {n, 0, 40}] (* Emanuele Munarini, Mar 01 2011; corrected by Harvey P. Dale, Sep 12 2012 *)

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)=sum(k=0, n, binomial(n-k, k)^2) /* Paul D. Hanna */

(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))

print([a(n) for n in range(31)]) # Indranil Ghosh, Apr 18 2017

CROSSREFS

Cf. A051291, A051292.

Cf. A107597, A185828 (log). Cf. A174882 (Hankel transf.).

Sequence in context: A095981 A247471 A082397 * A192475 A192400 A308154

Adjacent sequences: A051283 A051284 A051285 * A051287 A051288 A051289

KEYWORD

nonn,nice,easy

AUTHOR

Emanuele Munarini

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 5 17:04 EST 2022. Contains 358588 sequences. (Running on oeis4.)