A086617 -id:A086617 - cp's OEIS frontend

A108296 Diagonal sums of the number triangle associated to A086617.

1, 1, 2, 3, 5, 8, 14, 24, 43, 78, 144, 269, 509, 971, 1868, 3618, 7049, 13805, 27162, 53661, 106405, 211697, 422458, 845386, 1696017, 3410522, 6873060, 13878721, 28077439, 56900936, 115501012, 234807488, 478032437, 974507543, 1989123814

Offset: 0

Paul Barry, May 31 2005

The triangle associated to A086617 is given by T(n,k)=if(k<=n, sum{j=0..n-k, C(n-k,j)C(k,j)C(j)},0). A050253(n)=A108296(n+2)-A108296(n).

G.f.: (1-x^2-sqrt(1-2*x^2-4*x^3-3*x^4))/(2*x^3*(1-x^2)).
a(n) = Sum_{k=0..floor(n/2)} Sum_{j=0..n-2*k} binomial(n-2*k, j)*binomial(k, j) * A000108(j).
Conjecture: (n+3)*a(n) +(-n-2)*a(n-1) +2*(-n-1)*a(n-2) +2*(-n+3)*a(n-3) +(n+1)*a(n-4) +3*(n-2)*a(n-5)=0. - R. J. Mathar, Nov 16 2012

A086615 Antidiagonal sums of triangle A086614.

Original entry on oeis.org

1, 2, 4, 8, 17, 38, 89, 216, 539, 1374, 3562, 9360, 24871, 66706, 180340, 490912, 1344379, 3701158, 10237540, 28436824, 79288843, 221836402, 622599625, 1752360040, 4945087837, 13988490338, 39658308814, 112666081616

Offset: 0

Paul D. Hanna, Jul 24 2003

nonn

Partial sums of the Motzkin sequence (A001006). - Emeric Deutsch, Jul 12 2004
a(n) is the number of distinct ordered trees obtained by branch-reducing the ordered trees on n+1 edges. - David Callan, Oct 24 2004
a(n) is the number of consecutive horizontal steps at height 0 of all Motzkin paths from (0,0) to (n,0) starting with a horizontal step. - Charles Moore (chamoore(AT)howard.edu), Apr 15 2007
This sequence (with offset 1 instead of 0) occurs in Section 7 of K. Grygiel, P. Lescanne (2015), see g.f. N. - N. J. A. Sloane, Nov 09 2015
Also number of plain (untyped) normal forms of lambda-terms (terms that cannot be further beta-reduced.) [Bendkowski et al., 2016]. - N. J. A. Sloane, Nov 22 2017
If interpreted with offset 2, the INVERT transform is A002026 with offset 1. - R. J. Mathar, Nov 02 2021

			a(0)=1, a(1)=2, a(2)=3+1=4, a(3)=4+4=8, a(4)=5+10+2=17, a(5)=6+20+12=38, are upward antidiagonal sums of triangle A086614:
{1},
{2,1},
{3,4,2},
{4,10,12,5},
{5,20,42,40,14},
{6,35,112,180,140,42}, ...
For example, with n=2, the 5 ordered trees (A000108) on 3 edges are
|...|..../\.../\.../|\..
|../.\..|......|........
|.......................
Suppressing nonroot vertices of outdegree 1 (branch-reducing) yields
|...|..../\.../\../|\..
.../.\.................
of which 4 are distinct. So a(2)=4.
a(4)=8 because we have HHHH, HHUD, HUDH, HUHD

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Jean-Luc Baril and José Luis Ramírez, Descent distribution on Catalan words avoiding ordered pairs of Relations, arXiv:2302.12741 [math.CO], 2023.
Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6
Maciej Bendkowski, K. Grygiel, and P. Tarau, Random generation of closed simply-typed lambda-terms: a synergy between logic programming and Boltzmann samplers, arXiv preprint arXiv:1612.07682, 2016
K. Grygiel and P. Lescanne, A natural counting of lambda terms, SOFSEM 2016. Preprint 2015

Cf. A086614 (triangle), A086616 (row sums), A348869 (Seq. Transf.).
Cf. A001006.
Cf. A136788.

A086615 := proc(n)
    option remember;
    if n <= 3 then
        2^n;
    else
        3*(-n-1)*procname(n-1) +(-n+4)*procname(n-2) +3*(n-1)*procname(n-3) ;
        -%/(n+2) ;
    end if;
end proc:
seq(A086615(n),n=0..20) ; # R. J. Mathar, Nov 02 2021

CoefficientList[Series[(1-x-Sqrt[1-2*x-3*x^2])/(2*x-2*x^2)/x, {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 13 2014 *)

G.f.: A(x) = 1/(1-x)^2 + x^2*A(x)^2.
a(n) = Sum_{k=0..floor((n+1)/2)} binomial(n+1, 2k+1)*binomial(2k, k)/(k+1). - Paul Barry, Nov 29 2004
a(n) = n + 1 + Sum_k a(k-1)*a(n-k-1), starting from a(n)=0 for n negative. - Henry Bottomley, Feb 22 2005
a(n) = Sum_{k=0..n} Sum_{j=0..n-k} C(j)*C(n-k, 2j). - Paul Barry, Aug 19 2005
From Paul Barry, May 31 2006: (Start)
G.f.: c(x^2/(1-x)^2)/(1-x)^2, c(x) the g.f. of A000108;
a(n) = Sum_{k=0..floor(n/2)} C(n+1,n-2k)*C(k). (End)
Binomial transform of doubled Catalan sequence 1,1,1,1,2,2,5,5,14,14,... - Paul Barry, Nov 17 2005
Row sums of Pascal-Catalan triangle A086617. - Paul Barry, Nov 17 2005
g(z) = (1-z-sqrt(1-2z-3z^2))/(2z-2z^2)/z - Charles Moore (chamoore(AT)howard.edu), Apr 15 2007, corrected by Vaclav Kotesovec, Feb 13 2014
D-finite with recurrence (n+2)*a(n) +3*(-n-1)*a(n-1) +(-n+4)*a(n-2) +3*(n-1)*a(n-3)=0. - R. J. Mathar, Nov 30 2012
a(n) ~ 3^(n+5/2) / (4 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 13 2014

Edited by N. J. A. Sloane, Oct 16 2006

A086618 a(n) = Sum{k=0..n} binomial(n,k)^2*C(k), where C() = A000108() are the Catalan numbers.

Original entry on oeis.org

1, 2, 7, 33, 183, 1118, 7281, 49626, 349999, 2535078, 18758265, 141254655, 1079364105, 8350678170, 65298467487, 515349097713, 4100346740511, 32858696386766, 265001681344569

Offset: 0

Paul D. Hanna, Jul 24 2003

nonn

Main diagonal of square table A086617 of coefficients, T(n,k), of x^n*y^k in f(x,y) that satisfies f(x,y) = 1/[(1-x)(1-y)] + xy*f(x,y)^2.
a(n) is the number of permutations of length 2n which are invariant under the reverse-complement map and have no decreasing subsequences of length 4. - Eric S. Egge, Oct 21 2008
In 2012, Zhi-Wei Sun proved that for any odd prime p we have the congruence a(1) + ... + a(p-1) == 0 (mod p^2). - Zhi-Wei Sun, Aug 22 2013

			a(5) = 1118 = 1*1^2 + 1*5^2 + 2*10^2 + 5*10^2 + 14*5^2 + 42*1^2.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
D. Daly and L. Pudwell, Pattern avoidance in rook monoids, 2013.
T. Denton, Algebraic and Affine Pattern Avoidance, arXiv preprint arXiv:1303.3767 [math.CO], 2013.
Z.-W. Sun, Congruences for Franel numbers, arXiv preprint arXiv:1112.1034 [math.NT], 2011. See (1.22).
Z.-W. Sun, On sums of Apery polynomials and related congruences, J. Number Theory 132(2012), 2673-2699.

Cf. A086617 (table), A086615 (antidiagonal sums), A003046 (determinants).
Cf. A000108.
Cf. A228456.

Flatten[{1,RecurrenceTable[{(n+3)^2*(4*n+7)*a[n+2]==2*(20*n^3+117*n^2+220*n+135)*a[n+1]-9*(n+1)^2*(4*n+11)*a[n],a[1]==2,a[2]==7},a,{n,1,20}]}] (* Vaclav Kotesovec, Sep 11 2012 *)
Table[HypergeometricPFQ[{1/2, -n, -n}, {1, 2}, 4], {n, 0, 20}] (* Vladimir Reshetnikov, Oct 03 2016 *)

a(n)=sum(k=0,n-1,binomial(n-1,k)^2*binomial(2*k,k)/(k+1)) \\ Charles R Greathouse IV, Sep 12 2012

a(n)=sum(k=0,n-1,(4*k+3)*sum(i=0,k,binomial(k,i)^2*binomial(2*i,i)))/3/n^2 \\ Charles R Greathouse IV, Sep 12 2012

Recurrence: (n+3)^2*(4*n+7)*a(n+2) = 2*(20*n^3+117*n^2+220*n+135)*a(n+1) - 9*(n+1)^2*(4*n+11)*a(n). - Vaclav Kotesovec, Sep 11 2012
a(n) ~ 3^(5/2)/(8*Pi) * 9^n/n^2. - Vaclav Kotesovec, Oct 06 2012
G.f.: (1-(1-9*x)^(1/3)*hypergeom([1/3,1/3],[1],-27*x*(1-x)^2/(1-9*x)^2))/(6*x). - Mark van Hoeij, May 02 2013
a(n) = hypergeom([1/2,-n,-n], [1,2], 4). - Vladimir Reshetnikov, Oct 03 2016
D-finite with recurrence (n+1)^2*a(n) +(-19*n^2+8*n+6)*a(n-1) +9*(11*n^2-30*n+21)*a(n-2) -81*(n-2)^2*a(n-3)=0. - R. J. Mathar, Aug 01 2022

Edited by N. J. A. Sloane, Sep 14 2012. The formula in the new definition was first sent in by Michael Somos, Feb 19 2004

Minor edits Vaclav Kotesovec, Mar 31 2014

A087457 Number of odd length roads between any adjacent nodes in virtual optimal chordal ring of degree 3 (the length of chord < number of nodes/2).

Original entry on oeis.org

1, 5, 31, 213, 1551, 11723, 90945, 719253, 5773279, 46889355, 384487665, 3177879675, 26442188865, 221278343445, 1860908156031, 15717475208853, 133256583398655, 1133591857814363, 9672323357640129, 82752014457666363, 709719620585186529, 6100394753270329605

Offset: 1

B. Dubalski (dubalski(AT)atr.bydgoszcz.pl), Oct 23 2003

nonn

			a(1)=1; a(2)=9*a(1)-2*2=9-4=5; a(3)=9*5-2*7=31; a(4)=9*31-2*33=213; etc

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, MA, 2nd ed. 1998, see page number?

Seiichi Manyama, Table of n, a(n) for n = 1..1052 (terms 1..100 from T. D. Noe)

Cf. A086617, A086618, A002893.

a := 1; s := 0; for k from 1 to 10 do for i from 0 to k do ss := ((2*(i))!/((i)!*(i+1)!))*((k)!/((i)!*(k-i)!))^2; s := s+ss; od; a := (9*a-2*s); s := 0; od;
# Alternative:
a := n -> hypergeom([1/2, -n, -n], [1, 1], 4)/3;
seq(simplify(a(n)), n = 1..22);  # Peter Luschny, Nov 06 2023

Table[Sum[Binomial[n,k]^2*Binomial[2k,k],{k,0,n}]/3,{n,1,20}] (* Vaclav Kotesovec, Oct 14 2012 *)

a(n) = sum(k=0, n, binomial(n,k)^2*binomial(2*k,k))/3; \\ Michel Marcus, May 10 2020

a(1) = 1; a(n) = 9*a(n-1) - 2*A086618(n), where A086618(n) = Sum_{k=0..n} Catalan(n)*binomial(n, k)^2, and Catalan(n) = (2*n)!/(n!*(n+1)!). - Michael Somos
a(n) = A002893(n)/3 = (1/3)*Sum_{k=0..n}binomial(n,k)^2*binomial(2k,k). - Philippe Deléham, Sep 14 2008
Recurrence: n^2*a(n) = (10*n^2-10*n+3)*a(n-1) - 9*(n-1)^2*a(n-2). - Vaclav Kotesovec, Oct 14 2012
a(n) ~ 3^(2*n+1/2)/(4*Pi*n). - Vaclav Kotesovec, Oct 14 2012
G.f.: (hypergeom([1/3, 1/3],[1],-27*x*(x-1)^2/(9*x-1)^2)/(1-9*x)^(2/3)-1)/3.  - Mark van Hoeij, May 14 2013
G.f.: G(0)/(6*x*(1-9*x)^(2/3) ) -1/(3*x), where G(k)= 1 + 1/(1 - 3*(3*k+1)^2*x*(1-x)^2/(3*(3*k+1)^2*x*(1-x)^2 - (k+1)^2*(1-9*x)^2/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 31 2013
a(n) = hypergeom([1/2, -n, -n], [1, 1], 4) / 3. - Peter Luschny, Nov 06 2023

A088925 Square table, read by antidiagonals, of coefficients T(n,k) of x^ny^k in f(x,y) that satisfies f(x,y) = 1/(1-x-y) + xyf(x,y)^3.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 6, 6, 1, 1, 10, 21, 10, 1, 1, 15, 55, 55, 15, 1, 1, 21, 120, 212, 120, 21, 1, 1, 28, 231, 644, 644, 231, 28, 1, 1, 36, 406, 1652, 2617, 1652, 406, 36, 1, 1, 45, 666, 3738, 8685, 8685, 3738, 666, 45, 1, 1, 55, 1035, 7680, 24735, 36345, 24735, 7680

Offset: 0

Paul D. Hanna, Oct 23 2003

The g.f. for A001764 satisfies: g(x) = 1 + x*g(x)^3.

			Rows begin:
{1, 1, 1, 1, 1, 1, 1, 1,..}
{1, 3, 6,10,15,21,28,..}
{1, 6,21,55,120,231,..}
{1,10,55,212,644,..}
{1,15,120,644,..}
{1,21,231,..}

Cf. A088926 (diagonal), A088927 (antidiagonal sums), A086617, A001764.

t[n_, k_] := Sum[ Binomial[n+k, 2*i]*Binomial[n+k-2*i, k-i]*(3*i)!/(i!*(2*i+1)!), {i, 0, k}]; Table[t[n-k, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Nov 18 2013, after Michael Somos *)

T(n, k) = sum(i=0, k, C(n+k, 2i)*C(n+k-2i, k-i)*A001764(i) ), where A001764(i)=(3i)!/(i!(2i+1)!). - from Michael Somos

A089447 Symmetric square table of coefficients, read by antidiagonals, where T(n,k) is the coefficient of x^ny^k in f(x,y) that satisfies: f(x,y) = g(x,y) + xyf(x,y)^4 and where g(x,y) satisfies: 1 + (x+y-1)g(x,y) + xyg(x,y)^2 = 0.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 10, 10, 1, 1, 20, 48, 20, 1, 1, 35, 162, 162, 35, 1, 1, 56, 441, 841, 441, 56, 1, 1, 84, 1036, 3314, 3314, 1036, 84, 1, 1, 120, 2184, 10786, 18004, 10786, 2184, 120, 1, 1, 165, 4236, 30460, 77952, 77952, 30460, 4236, 165, 1, 1, 220, 7689, 77044

Offset: 0

Paul D. Hanna, Nov 02 2003

Explicitly, g(x,y) = ((1-x-y)+sqrt((1-x-y)^2-4xy))/(2xy) = sum(n>=0, sum(k>=0, N(n,k)*x^n*y^k), where N(n,k) are the Narayana numbers: N(n,k) = C(n+k,k)*C(n+k+2,k+1)/(n+k+2). This array is directly related to sequence A002293, which has a g.f. h(x) that satisfies h(x) = 1 + x*h(x)^4. The inverse binomial transform of the rows grows by three terms per row.

			Rows begin:
[1,   1,     1,      1,       1,        1,         1,          1, ...];
[1,   4,    10,     20,      35,       56,        84,        120, ...];
[1,  10,    48,    162,     441,     1036,      2184,       4236, ...];
[1,  20,   162,    841,    3314,    10786,     30460,      77044, ...];
[1,  35,   441,   3314,   18004,    77952,    284880,     912042, ...];
[1,  56,  1036,  10786,   77952,   435654,   2007456,    7951674, ...];
[1,  84,  2184,  30460,  284880,  2007456,  11427992,   55009548, ...];
[1, 120,  4236,  77044,  912042,  7951674,  55009548,  317112363, ...];
[1, 165,  7689, 178387, 2624453, 27870393, 231114465, 1576219474, ...]; ...

Cf. A089448 (diagonal), A089449 (antidiagonal sums), A086617, A088925, A002293.

{L=10; T=matrix(L,L,n,k,1); for(n=1,L-1, for(k=1,L-1, T[n+1,k+1]=binomial(n+k,k)*binomial(n+k+2,k+1)/(n+k+2)+ sum(j3=1,k,sum(i3=1,n,T[n-i3+1,k-j3+1]* sum(j2=1,j3,sum(i2=1,i3,T[i3-i2+1,j3-j2+1]* sum(j1=1,j2,sum(i1=1,i2,T[i2-i1+1,j2-j1+1]*T[i1,j1])); )); )); )); T}

A086614 Triangle read by rows, where T(n,k) is the coefficient of x^ny^k in f(x,y) that satisfies f(x,y) = 1/(1-x)^2 + xyf(x,y)^2.

Original entry on oeis.org

1, 2, 1, 3, 4, 2, 4, 10, 12, 5, 5, 20, 42, 40, 14, 6, 35, 112, 180, 140, 42, 7, 56, 252, 600, 770, 504, 132, 8, 84, 504, 1650, 3080, 3276, 1848, 429, 9, 120, 924, 3960, 10010, 15288, 13860, 6864, 1430, 10, 165, 1584, 8580, 28028, 57330, 73920, 58344, 25740

Offset: 0

Paul D. Hanna, Jul 24 2003

			Rows:
{1},
{2, 1},
{3, 4,    2},
{4, 10,  12,    5},
{5, 20,  42,   40,   14},
{6, 35, 112,  180,  140,   42},
{7, 56, 252,  600,  770,  504,  132},
{8, 84, 504, 1650, 3080, 3276, 1848, 429}, ...

T(n,n) = A000108(n).

Cf. A086615 (antidiagonal sums), A086616 (row sums), A086617, A000292 (column 1), A277935 (column 2), A000580 (column 3 divided by 5), A000582 (column 4 divided by 14).

T := (n,k) -> `if`(k=0, n+1, binomial(2*k, k-1)*binomial(n+k+1, n-k)/k):
for n from 0 to 8 do seq(T(n,k), k=0..n) od; # Peter Luschny, Jan 26 2018

T(n,k) = binomial(2*k, k-1)*binomial(n+k+1, n-k) / k for k > 0. # Peter Luschny, Jan 26 2018

A130671 Triangular sequence based on Pascal's triangle: t(n,m) = 2binomial(m, n) - (1 + n(m - n)).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 7, 4, 1, 1, 5, 13, 13, 5, 1, 1, 6, 21, 30, 21, 6, 1, 1, 7, 31, 57, 57, 31, 7, 1, 1, 8, 43, 96, 123, 96, 43, 8, 1, 1, 9, 57, 149, 231, 231, 149, 57, 9, 1, 1, 10, 73, 218, 395, 478, 395, 218, 73, 10, 1

Offset: 1

Roger L. Bagula and Gary W. Adamson, Jun 27 2007

Suggested by Gary W. Adamson from a previous submission. Very close to (but slightly smaller at 7th row) A086617.

			{1},
{1, 1},
{1, 2, 1},
{1, 3, 3, 1},
{1, 4, 7, 4, 1},
{1, 5, 13, 13, 5, 1},
{1, 6, 21, 30, 21, 6, 1},
{1, 7, 31, 57, 57, 31, 7, 1}

Cf. A086617.

Table[Table[2*Binomial[m, n] - (1 + n*(m - n)), {n, 0, m}], {m, 0, 10}] Flatten[%]

t(n,m) = 2*binomial[m, n] - (1 + n*(m - n)).

cp's OEIS Frontend

A108296 Diagonal sums of the number triangle associated to A086617.

Views

Author

Keywords

Comments

Formula

A086615 Antidiagonal sums of triangle A086614.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A086618 a(n) = Sum{k=0..n} binomial(n,k)^2*C(k), where C() = A000108() are the Catalan numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A087457 Number of odd length roads between any adjacent nodes in virtual optimal chordal ring of degree 3 (the length of chord < number of nodes/2).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A088925 Square table, read by antidiagonals, of coefficients T(n,k) of x^n*y^k in f(x,y) that satisfies f(x,y) = 1/(1-x-y) + xy*f(x,y)^3.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A089447 Symmetric square table of coefficients, read by antidiagonals, where T(n,k) is the coefficient of x^n*y^k in f(x,y) that satisfies: f(x,y) = g(x,y) + xy*f(x,y)^4 and where g(x,y) satisfies: 1 + (x+y-1)*g(x,y) + xy*g(x,y)^2 = 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A086614 Triangle read by rows, where T(n,k) is the coefficient of x^n*y^k in f(x,y) that satisfies f(x,y) = 1/(1-x)^2 + xy*f(x,y)^2.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Formula

A130671 Triangular sequence based on Pascal's triangle: t(n,m) = 2*binomial(m, n) - (1 + n*(m - n)).

Views

Author

Keywords

Comments

A088925 Square table, read by antidiagonals, of coefficients T(n,k) of x^ny^k in f(x,y) that satisfies f(x,y) = 1/(1-x-y) + xyf(x,y)^3.

A089447 Symmetric square table of coefficients, read by antidiagonals, where T(n,k) is the coefficient of x^ny^k in f(x,y) that satisfies: f(x,y) = g(x,y) + xyf(x,y)^4 and where g(x,y) satisfies: 1 + (x+y-1)g(x,y) + xyg(x,y)^2 = 0.

A086614 Triangle read by rows, where T(n,k) is the coefficient of x^ny^k in f(x,y) that satisfies f(x,y) = 1/(1-x)^2 + xyf(x,y)^2.

A130671 Triangular sequence based on Pascal's triangle: t(n,m) = 2binomial(m, n) - (1 + n(m - n)).