A185828 -id:A185828 - cp's OEIS frontend

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

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

Offset: 0

Emanuele Munarini

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
Diagonal of the rational function 1 / ((1 - x)*(1 - y) - (x*y)^2). - Ilya Gutkovskiy, Apr 23 2025
a(n) is the number of rooted ordered trees with node weights summing to n, where the root has weight 0, non-root node weights are in {1,2}, and no nodes have the same weight as their parent node. - John Tyler Rascoe, Jun 10 2025

			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.

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).
Cyril Banderier and Paweł 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, Nathanaël Hassler, Sergey Kirgizov, and José L. Ramírez, Grand zigzag knight's paths, arXiv:2402.04851 [math.CO], 2024.
Jean-Luc Baril, Sergey Kirgizov, Rémi Maréchal, and Vincent Vajnovszki, Grand Dyck paths with air pockets, arXiv:2211.04914 [math.CO], 2022.
Jean-Luc Baril and José L. Ramírez, Fibonacci and Catalan paths in a wall, 2023.
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.
Miklós Bóna and Arnold 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).
Emanuele Munarini and Norma Zagaglia Salvi, On the Rank Polynomial of the Lattice of Order Ideals of Fences and Crowns, Discrete Mathematics 259 (2002), 163-177.
Jesús Sistos Barrón and Hua Wang, Balanced n-color compositions, Integers (2024) Vol. 24A, Art. No. A2. See pp. 4, 5, 8, 14.

Cf. main diagonal of A125250, column k=2 of A384747.

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

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

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

makelist(sum(binomial(n-k,k)^2,k,0,floor(n/2)),n,0,40);  /* Emanuele Munarini, Mar 01 2011 */

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

a(n)=sum(k=0,n,binomial(n-k,k)^2) /* Paul D. Hanna */

{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 */

{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

{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

{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

{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

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

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

A302278 T(n,k) = number of n X k 0..1 arrays with every element equal to 1, 2 or 4 horizontally, diagonally or antidiagonally adjacent elements, with upper left element zero.

Original entry on oeis.org

0, 1, 0, 1, 3, 0, 2, 7, 10, 0, 3, 10, 22, 23, 0, 5, 27, 29, 79, 61, 0, 8, 45, 74, 89, 269, 162, 0, 13, 98, 162, 283, 353, 942, 421, 0, 21, 193, 363, 649, 1219, 941, 3401, 1103, 0, 34, 379, 782, 1621, 3621, 3854, 3316, 12283, 2890, 0, 55, 778, 1766, 4209, 14125, 15862, 14639

Offset: 1

R. H. Hardin, Apr 04 2018

Table starts
  1     1     2      3       5        8       13        21         34
  3     7    10     27      45       98      193       379        778
 10    22    29     74     162      363      782      1766       3953
 23    79    89    283     649     1621     4209      9563      25179
 61   269   353   1219    3621    14125    38410    108141     360173
162   942   941   3854   15862    72083   229708    713848    2948380
421  3401  3316  14639   69601   384916  1354563   4386347   20677591
1103 12283 12016  63093  385242  3027442 11370253  43394297  258471515
2890 43006 34060 222254 1809350 17837758 75667277 325745362 2460590443

			Some solutions for n=5, k=4:
  0 0 1 1     0 1 1 1     0 0 0 0     0 0 0 0     0 0 1 0
  1 1 0 0     0 0 1 0     1 1 1 1     0 1 0 1     1 1 0 0
  1 0 1 0     0 0 0 0     0 1 0 1     1 0 1 0     0 0 0 1
  1 0 1 0     0 1 1 1     1 0 1 0     1 1 1 1     0 1 1 1
  0 1 0 1     1 0 0 0     0 1 0 1     0 0 0 0     1 1 0 0

R. H. Hardin, Table of n, a(n) for n = 1..220

Column 2 is A185828.

Row 1 is A000045(n-1).

Empirical for column k:
k=1: a(n) = a(n-1)
k=2: a(n) = 2*a(n-1) + a(n-2) + 2*a(n-3) - a(n-4)
k=3: [order 18]
k=4: [order 72] for n > 73
Empirical for row n:
n=1: a(n) = a(n-1) + a(n-2)
n=2: a(n) = a(n-1) + 3*a(n-2) - 4*a(n-4) for n > 5
n=3: [order 16] for n > 18
n=4: [order 64] for n > 66

A302528 T(n,k)=Number of nXk 0..1 arrays with every element equal to 1, 2, 4 or 5 horizontally, diagonally or antidiagonally adjacent elements, with upper left element zero.

Original entry on oeis.org

0, 1, 0, 1, 3, 0, 2, 7, 10, 0, 3, 10, 28, 23, 0, 5, 27, 42, 115, 61, 0, 8, 45, 100, 168, 497, 162, 0, 13, 98, 290, 539, 902, 2086, 421, 0, 21, 193, 730, 1977, 3683, 3256, 9091, 1103, 0, 34, 379, 1700, 5942, 23909, 17546, 15852, 40575, 2890, 0, 55, 778, 4246, 16733, 128242

Offset: 1

R. H. Hardin, Apr 09 2018

Table starts
.0....1......1......2.......3.........5..........8..........13...........21
.0....3......7.....10......27........45.........98.........193..........379
.0...10.....28.....42.....100.......290........730........1700.........4246
.0...23....115....168.....539......1977.......5942.......16733........49219
.0...61....497....902....3683.....23909.....128242......465323......1918153
.0..162...2086...3256...17546....182773....1275348.....5557469.....29725028
.0..421...9091..15852...92603...1551340...16130212....82774516....506265517
.0.1103..40575..77904..615351..18089458..303355178..1916999716..16636194027
.0.2890.172996.314276.3268978.155010391.3654880956.27228654766.305442540368

			Some solutions for n=5 k=4
..0..0..1..0. .0..1..0..0. .0..0..1..1. .0..1..1..1. .0..0..1..1
..1..1..0..0. .1..0..1..1. .1..1..0..0. .1..0..0..0. .1..0..0..1
..1..0..1..0. .0..1..0..1. .1..0..1..0. .1..1..1..1. .1..1..1..1
..0..0..1..1. .1..1..1..0. .1..0..0..1. .1..1..1..1. .0..0..1..1
..1..1..0..0. .0..0..0..1. .0..1..1..0. .1..0..0..1. .1..1..0..0

R. H. Hardin, Table of n, a(n) for n = 1..180

Column 2 is A185828.
Row 1 is A000045(n-1).
Row 2 is A302279.

Empirical for column k:
k=1: a(n) = a(n-1)
k=2: a(n) = 2*a(n-1) +a(n-2) +2*a(n-3) -a(n-4)
k=3: [order 18]
k=4: [order 72]
Empirical for row n:
n=1: a(n) = a(n-1) +a(n-2)
n=2: a(n) = a(n-1) +3*a(n-2) -4*a(n-4) for n>5
n=3: [order 15] for n>17
n=4: [order 68] for n>69

A302728 T(n,k)=Number of nXk 0..1 arrays with every element equal to 1, 2, 4 or 6 horizontally, diagonally or antidiagonally adjacent elements, with upper left element zero.

Original entry on oeis.org

0, 1, 0, 1, 3, 0, 2, 7, 10, 0, 3, 10, 22, 23, 0, 5, 27, 29, 83, 61, 0, 8, 45, 74, 89, 301, 162, 0, 13, 98, 162, 287, 353, 1079, 421, 0, 21, 193, 363, 689, 1307, 941, 4064, 1103, 0, 34, 379, 782, 1723, 4505, 4491, 3316, 15183, 2890, 0, 55, 778, 1766, 4491, 16265, 20842, 17828

Offset: 1

R. H. Hardin, Apr 12 2018

Table starts
.0....1.....1.....2......3.......5........8........13........21.........34
.0....3.....7....10.....27......45.......98.......193.......379........778
.0...10....22....29.....74.....162......363.......782......1766.......3953
.0...23....83....89....287.....689.....1723......4491.....10433......28009
.0...61...301...353...1307....4505....16265.....46773....136935.....481479
.0..162..1079...941...4491...20842....89121....286746...1022779....4520360
.0..421..4064..3316..17828..104969...532511...1932168...7608792...40495097
.0.1103.15183.12016..80293..623549..4281120..17200486..81226394..547173278
.0.2890.55012.34060.304958.3195095.26823700.120221024.683140749.5901256655

			Some solutions for n=5 k=4
..0..0..0..0. .0..1..1..1. .0..0..1..1. .0..1..0..1. .0..1..1..0
..1..0..1..0. .1..0..0..0. .0..0..1..1. .1..0..1..0. .0..0..0..0
..0..1..0..1. .1..1..1..1. .0..1..0..1. .0..1..0..1. .0..1..1..0
..1..0..1..0. .0..1..1..1. .0..1..1..0. .1..0..1..0. .0..0..0..0
..1..1..1..1. .1..0..0..0. .1..0..0..1. .0..0..0..0. .0..1..1..0

R. H. Hardin, Table of n, a(n) for n = 1..220

Column 2 is A185828.
Column 4 is A302274.
Row 1 is A000045(n-1).
Row 2 is A302279.
Row 3 is A302280.

Empirical for column k:
k=1: a(n) = a(n-1)
k=2: a(n) = 2*a(n-1) +a(n-2) +2*a(n-3) -a(n-4)
k=3: [order 16]
k=4: [order 72] for n>73
Empirical for row n:
n=1: a(n) = a(n-1) +a(n-2)
n=2: a(n) = a(n-1) +3*a(n-2) -4*a(n-4) for n>5
n=3: [order 16] for n>18
n=4: [order 68] for n>69

A303410 T(n,k)=Number of nXk 0..1 arrays with every element equal to 1, 2, 4, 5 or 6 horizontally, diagonally or antidiagonally adjacent elements, with upper left element zero.

Original entry on oeis.org

0, 1, 0, 1, 3, 0, 2, 7, 10, 0, 3, 10, 28, 23, 0, 5, 27, 42, 119, 61, 0, 8, 45, 100, 168, 541, 162, 0, 13, 98, 290, 547, 902, 2327, 421, 0, 21, 193, 730, 2079, 4013, 3256, 10384, 1103, 0, 34, 379, 1700, 6322, 29411, 21361, 15852, 47491, 2890, 0, 55, 778, 4246, 17903

Offset: 1

R. H. Hardin, Apr 23 2018

Table starts
.0....1......1......2.......3.........5..........8..........13............21
.0....3......7.....10......27........45.........98.........193...........379
.0...10.....28.....42.....100.......290........730........1700..........4246
.0...23....119....168.....547......2079.......6322.......17903.........53665
.0...61....541....902....4013.....29411.....160247......660748.......3071197
.0..162...2327...3256...21361....236326....1716995.....8688851......56229035
.0..421..10384..15852..115770...2158662...24386918...158640643....1293822589
.0.1103..47491..77904..803911..27002794..497878411..4298730424...50946692110
.0.2890.208616.314276.4667376.250400003.6748940959.74532460229.1222253462556

			Some solutions for n=5 k=4
..0..1..0..0. .0..1..1..0. .0..1..0..1. .0..0..0..0. .0..0..0..0
..1..0..1..1. .1..0..0..1. .1..0..1..0. .1..1..1..1. .1..0..1..0
..0..0..0..0. .1..1..1..1. .0..1..0..1. .1..0..1..0. .0..1..0..1
..0..1..0..0. .0..1..1..0. .0..0..0..0. .1..1..0..1. .1..1..1..1
..1..0..1..1. .1..0..0..1. .1..1..1..1. .1..0..1..0. .0..0..0..1

R. H. Hardin, Table of n, a(n) for n = 1..180

Column 2 is A185828.
Column 4 is A302524.
Row 1 is A000045(n-1).
Row 2 is A302279.
Row 3 is A302529.

Empirical for column k:
k=1: a(n) = a(n-1)
k=2: a(n) = 2*a(n-1) +a(n-2) +2*a(n-3) -a(n-4)
k=3: [order 18]
k=4: [order 72]
Empirical for row n:
n=1: a(n) = a(n-1) +a(n-2)
n=2: a(n) = a(n-1) +3*a(n-2) -4*a(n-4) for n>5
n=3: [order 15] for n>17
n=4: [order 71] for n>72

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

PARI

PARI

PARI

PARI

PARI

PARI

Python

Formula

A302278 T(n,k) = number of n X k 0..1 arrays with every element equal to 1, 2 or 4 horizontally, diagonally or antidiagonally adjacent elements, with upper left element zero.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A302528 T(n,k)=Number of nXk 0..1 arrays with every element equal to 1, 2, 4 or 5 horizontally, diagonally or antidiagonally adjacent elements, with upper left element zero.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A302728 T(n,k)=Number of nXk 0..1 arrays with every element equal to 1, 2, 4 or 6 horizontally, diagonally or antidiagonally adjacent elements, with upper left element zero.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A303410 T(n,k)=Number of nXk 0..1 arrays with every element equal to 1, 2, 4, 5 or 6 horizontally, diagonally or antidiagonally adjacent elements, with upper left element zero.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A301669 T(n,k)=Number of nXk 0..1 arrays with every element equal to 1, 2 or 4 horizontally or vertically adjacent elements, with upper left element zero.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula