login
Whitney number of level n of the lattice of the ideals of the fence of order 2n.
51

%I #174 May 20 2024 11:24:18

%S 1,1,2,5,11,26,63,153,376,931,2317,5794,14545,36631,92512,234205,

%T 594169,1510192,3844787,9802895,25027296,63972861,163701327,419316330,

%U 1075049011,2758543201,7083830648,18204064403,46812088751,120452857976

%N Whitney number of level n of the lattice of the ideals of the fence of order 2n.

%C 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

%C a(n) has same parity as Fibonacci(n+1) = A000045(n+1); see A107597. - _Paul D. Hanna_, May 22 2005

%C 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

%C From _Paul Barry_, Mar 31 2010: (Start)

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

%C Hankel transform is A174882. (End)

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

%C Apparently the number of peakless grand Motzkin paths of length n. - _David Scambler_, Jul 04 2013

%C 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

%C 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

%H Vincenzo Librandi and Alois P. Heinz, <a href="/A051286/b051286.txt">Table of n, a(n) for n = 0..1000</a>

%H Andrei Asinowski, Axel Bacher, Cyril Banderier and Bernhard Gittenberger, <a href="http://doi.org/10.1007/978-3-319-77313-1_15">Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Enumerative Aspects</a>, 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.

%H Andrei Asinowski, Axel Bacher, Cyril Banderier and Bernhard Gittenberger, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/patterns2019.pdf">Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata</a>, Laboratoire d'Informatique de Paris Nord (LIPN 2019).

%H Cyril Banderier and Paweł Hitczenko, <a href="http://doi.org/10.1016/j.dam.2011.12.011">Enumeration and asymptotics of restricted compositions having the same number of parts</a>, Disc. Appl. Math. 160 (18) (2012) 2542-2554. See Puzzle 3.1.

%H Jean-Luc Baril, Nathanaël Hassler, Sergey Kirgizov, and José L. Ramírez, <a href="https://arxiv.org/abs/2402.04851">Grand zigzag knight's paths</a>, arXiv:2402.04851 [math.CO], 2024.

%H Jean-Luc Baril, Sergey Kirgizov, Rémi Maréchal, and Vincent Vajnovszki, <a href="https://arxiv.org/abs/2211.04914">Grand Dyck paths with air pockets</a>, arXiv:2211.04914 [math.CO], 2022.

%H Jean-Luc Baril and José L. Ramírez, <a href="http://jl.baril.u-bourgogne.fr/pathwall.pdf">Fibonacci and Catalan paths in a wall</a>, 2023.

%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Barry4/barry142.html">On a Generalization of the Narayana Triangle</a>, J. Int. Seq. 14 (2011) # 11.4.5.

%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Barry/barry321.html">Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices</a>, Journal of Integer Sequences, 19, 2016, #16.3.5.

%H Hacène Belbachir and Abdelghani Mehdaoui, <a href="https://doi.org/10.2989/16073606.2020.1729269">Recurrence relation associated with the sums of square binomial coefficients</a>, Quaestiones Mathematicae (2021) Vol. 44, Issue 5, 615-624.

%H Miklós Bóna and Arnold Knopfmacher, <a href="http://dx.doi.org/10.1007/s00026-010-0060-7">On the probability that certain compositions have the same number of parts</a>, Ann. Comb., 14 (2010), 291-306.

%H Steffen Eger, <a href="http://arxiv.org/abs/1511.00622">On the Number of Many-to-Many Alignments of N Sequences</a>, arXiv:1511.00622 [math.CO], 2015.

%H Steffen Eger, <a href="https://arxiv.org/abs/1704.04964">The Combinatorics of Weighted Vector Compositions</a>, arXiv:1704.04964 [math.CO], 2017.

%H Sergi Elizalde, <a href="https://arxiv.org/abs/2002.12874">The degree of symmetry of lattice paths</a>, arXiv:2002.12874 [math.CO], 2021.

%H Edyta Hetmaniok, Barbara Smoleń and Roman Wituła, <a href="http://ceur-ws.org/Vol-1853/p07.pdf">The Stirling triangles</a>, Proceedings of the Symposium for Young Scientists in Technology, Engineering and Mathematics (SYSTEM 2017), Kaunas, Lithuania, April 28, 2017, p. 35-41.

%H Ivo L. Hofacker, Christian M. Reidys, and Peter F. Stadler, <a href="http://dx.doi.org/10.1016/j.disc.2011.06.004">Symmetric circular matchings and RNA folding</a>. Discr. Math., 312:100-112, 2012. See Prop. 5, C_l^{1}(z).

%H Emanuele Munarini and Norma Zagaglia Salvi, <a href="http://dx.doi.org/10.1016/S0012-365X(02)00378-3">On the Rank Polynomial of the Lattice of Order Ideals of Fences and Crowns</a>, Discrete Mathematics 259 (2002), 163-177.

%H Jesús Sistos Barrón and Hua Wang, <a href="https://math.colgate.edu/~integers/a2Proc23/a2Proc23.pdf">Balanced n-color compositions</a>, Integers (2024) Vol. 24A, Art. No. A2. See pp. 4, 5, 8, 14.

%F G.f.: 1/sqrt(1 - 2*x - x^2 - 2*x^3 + x^4).

%F a(n) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*(-1)^k*A002426(n-2k). - _Paul Barry_, Jan 31 2005

%F From _Paul D. Hanna_, May 22 2005: (Start)

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

%F Limit_{n->oo} a(n+1)/a(n) = (sqrt(5)+3)/2.

%F G.f.: 1/sqrt((1+x+x^2)*(1-3*x+x^2)). (End)

%F a(n) = Sum_{k=0..n} A049310(n, k)^2. - _Philippe Deléham_, Nov 21 2005

%F 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

%F G.f.: exp( Sum_{n>=1} (x^n/n)*Sum_{k=0..n} C(2n,2k)*x^k ). - _Paul D. Hanna_, Mar 18 2011

%F Logarithmic derivative equals A185828. - _Paul D. Hanna_, Mar 18 2011

%F 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

%F 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

%F 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

%F From _Paul D. Hanna_, Sep 05 2014: (Start)

%F G.f.: Sum_{n>=0} x^n * Sum_{k=0..n} C(n,k)^2 * x^k.

%F G.f.: Sum_{n>=0} x^n *[Sum_{k>=0} C(n+k,k)^2 * x^k] * (1-x)^(2*n+1).

%F G.f.: Sum_{n>=0} x^(2*n) * [Sum_{k>=0} C(n+k,k)^2 * x^k].

%F G.f.: Sum_{n>=0} x^(2*n) * [Sum_{k=0..n} C(n,k)^2 * x^k] /(1-x)^(2n+1).

%F (End)

%e 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.

%p 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

%p # second Maple program:

%p a:= proc(n) option remember; `if`(n<4, [1$2, 2, 5][n+1],

%p ((2*n-1)*a(n-1)+(n-1)*a(n-2)+(2*n-3)*a(n-3)-(n-2)*a(n-4))/n)

%p end:

%p seq(a(n), n=0..35); # _Alois P. Heinz_, Aug 11 2016

%t 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 *)

%t CoefficientList[Series[1/Sqrt[1-2*x-x^2-2*x^3+x^4], {x, 0, 20}], x] (* _Vaclav Kotesovec_, Jan 05 2013 *)

%t 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 *)

%o (PARI) a(n)=polcoeff(1/sqrt((1+x+x^2)*(1-3*x+x^2)+x*O(x^n)),n)

%o (PARI) a(n)=sum(k=0,n,binomial(n-k,k)^2) /* _Paul D. Hanna_ */

%o (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 */

%o (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

%o (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

%o (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

%o (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

%o (Maxima) makelist(sum(binomial(n-k,k)^2,k,0,floor(n/2)),n,0,40); /* _Emanuele Munarini_, Mar 01 2011 */

%o (Python)

%o from sympy import binomial

%o def a(n): return sum(binomial(n - k, k)**2 for k in range(n//2 + 1))

%o print([a(n) for n in range(31)]) # _Indranil Ghosh_, Apr 18 2017

%Y Main diagonal of A125250.

%Y Cf. A051291, A051292, A107597, A185828 (log). Cf. A174882 (Hankel transf.).

%K nonn,nice,easy

%O 0,3

%A _Emanuele Munarini_