A026670 -id:A026670 - cp's OEIS frontend

A026725 Triangular array, T, read by rows: T(n,0) = T(n,n) = 1. For n >= 2 and 1<=k<=n-1, T(n,k) = T(n-1,k-1) + T(n-2,k-1) + T(n-1,k) if n is odd and k=n/2, otherwise T(n,k) = T(n-1,k-1) + T(n-1,k).

1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 5, 7, 4, 1, 1, 6, 16, 11, 5, 1, 1, 7, 22, 27, 16, 6, 1, 1, 8, 29, 65, 43, 22, 7, 1, 1, 9, 37, 94, 108, 65, 29, 8, 1, 1, 10, 46, 131, 267, 173, 94, 37, 9, 1, 1, 11, 56, 177, 398, 440, 267, 131, 46, 10, 1, 1, 12, 67, 233

Offset: 0

Clark Kimberling

T(n+2,n) = A134869(n+1). - Philippe Deléham, Feb 01 2014

			Triangle begins:
1
1  1
1  2  1
1  4  3   1
1  5  7   4   1
1  6 16  11   5    1
1  7 22  27  16    6   1
1  8 29  65  43   22   7   1
1  9 37  94 108   65  29   8   1
1 10 46 131 267  173  94  37   9  1
1 11 56 177 398  440 267 131  46 10  1
1 12 67 233 575 1105 707 398 177 56 11 1
... - _Philippe Deléham_, Feb 01 2014

G. C. Greubel, Rows n = 0..99 of triangle, flattened
Rob Arthan, Comments on A026674, A026725, A026670

Cf. A026674.

T:= function(n,k)
    if k=0 or k=n then return 1;
    elif 2*k=n-1 then return T(n-1, k-1) + T(n-2, k-1) + T(n-1, k);
    else return T(n-1, k-1) + T(n-1, k);
    fi;
  end;
Flat(List([0..14], n-> List([0..n], k-> T(n,k) ))); # G. C. Greubel, Jul 16 2019

A026725 := proc(n,k)
    option remember;
    if n < 0 or k < 0 then
        0;
    elif k=0 or k=n then
        1;
    elif 2*k = n-1 then
      procname(n-1,k-1)+procname(n-2,k-1)+procname(n-1,k) ;
   else
       procname(n-1,k-1)+procname(n-1,k) ;
    end if;
end proc: # R. J. Mathar, Oct 21 2019

T[n_, k_]:= T[n, k]= If[k==0||k==n, 1, If[OddQ[n] && k==(n-1)/2, T[n-1, k -1] + T[n-2, k-1] + T[n-1, k], T[n-1, k-1] + T[n-1, k]]];
Table[T[n, k], {n,0,14}, {k,0,n}]//Flatten (* G. C. Greubel, Jul 16 2019 *)

T(n,k) = if(k==n || k==0, 1, if(2*k==n-1, T(n-1, k-1) + T(n-2, k-1) + T(n-1, k), T(n-1, k-1) + T(n-1, k) ));
for(n=0,11, for(k=0,n, print1(T(n,k), ", "))) \\ G. C. Greubel, Jul 16 2019

@CachedFunction
def T(n, k):
    if (k==0 or k==n): return 1
    elif (mod(n,2)==0 and k==(n-1)/2): return T(n-1, k-1) + T(n-2, k-1) + T(n-1, k)
    else: return T(n-1, k-1) + T(n-1, k)
[[T(n, k) for k in (0..n)] for n in (0..14)] # G. C. Greubel, Jul 16 2019

T(n, k) = number of paths from (0, 0) to (n-k, k) in directed graph having vertices (i, j) and edges (i, j)-to-(i+1, j) and (i, j)-to-(i, j+1) for i, j >= 0 and edges (i, i+1)-to-(i+1, i+2) for i >= 0.

Comment from Rick L. Shepherd, Aug 05 2002: Probably this should be changed to "and edges (i+1, i)-to-(i+2, i+1) for i >= 0."

Title and offset corrected by G. C. Greubel, Jul 16 2019, again by R. J. Mathar, Oct 21 2019, again by Sean A. Irvine, Oct 25 2019

A026671 Number of lattice paths from (0,0) to (n,n) with steps (0,1), (1,0) and, when on the diagonal, (1,1).

Original entry on oeis.org

1, 3, 11, 43, 173, 707, 2917, 12111, 50503, 211263, 885831, 3720995, 15652239, 65913927, 277822147, 1171853635, 4945846997, 20884526283, 88224662549, 372827899079, 1576001732485, 6663706588179, 28181895551161, 119208323665543, 504329070986033, 2133944799315027

Offset: 0

Clark Kimberling, Miklos Bona

1, 1, 3, 11, 43, 173, ... is the unique sequence for which both the Hankel transform of the sequence itself and the Hankel transform of its left shift are the powers of 2 (A000079). For example, det[{{1, 1, 3}, {1, 3, 11}, {3, 11, 43}}] = det[{{1, 3, 11}, {3, 11, 43}, {11, 43, 173}}] = 4. - David Callan, Mar 30 2007
From Paul Barry, Jan 25 2009: (Start)
a(n) is the image of F(2n+2) under the Catalan matrix (1,xc(x)) where c(x) is the g.f. of A000108.
The sequence 1,1,3,... is the image of A001519 under (1,xc(x)). This sequence has g.f. given by 1/(1-x-2x^2/(1-3x-x^2/(1-2x-x^2/(1-2x-x^2/(1-... (continued fraction). (End)
Binomial transform of A111961. - Philippe Deléham, Feb 11 2009
From Paul Barry, Nov 03 2010: (Start)
The sequence 1,1,3,... has g.f. 1/(1-x/sqrt(1-4x)), INVERT transform of A000984.
It is an eigensequence of the sequence array for A000984. (End)

L. W. Shapiro and C. J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 33-46.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Jean-Christophe Aval, Adrien Boussicault and Sandrine Dasse-Hartaut, The tree structure in staircase tableaux, arXiv:1109.4907 [math.CO], 2011-2013.
Cyril Banderier, Markus Kuba, and Michael Wallner, Analytic Combinatorics of Composition schemes and phase transitions with mixed Poisson distributions, arXiv:2103.03751 [math.PR], 2021.
Miklos Bona, The permutation classes equinumerous to the smooth class, Electron. J. Combin., 5 (1998), no. 1, Research Paper 31, 12 pp.
David Callan and Toufik Mansour, Five subsets of permutations enumerated as weak sorting permutations, arXiv:1602.05182 [math.CO], 2016.
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
Milan Janjić, Pascal Matrices and Restricted Words, J. Int. Seq., Vol. 21 (2018), Article 18.5.2.
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
Huyile Liang, Jeffrey Remmel and Sainan Zheng, Stieltjes moment sequences of polynomials, arXiv:1710.05795 [math.CO], 2017, see page 16.

a(n) = T(2n-1, n-1), T given by A026736.
a(n) = T(2n, n), T given by A026670.
a(n) = T(2n+1, n+1), T given by A026725.
Row sums of triangle A054335.
Cf. A026781, A001076, A176280.

a:=[3,11,43];; for n in [4..30] do a[n]:=(2*(4*n-3)*a[n-1] - 3*(5*n-8)*a[n-2] - 2*(2*n-3)*a[n-3])/n; od; Concatenation([1], a); # G. C. Greubel, Jul 16 2019

R:=PowerSeriesRing(Rationals(), 30); Coefficients(R!( 1/(Sqrt(1-4*x)-x) )); // G. C. Greubel, Jul 16 2019

Table[SeriesCoefficient[1/(Sqrt[1-4*x]-x),{x,0,n}],{n,0,30}] (* Vaclav Kotesovec, Oct 08 2012 *)

{a(n)= if(n<0, 0, polcoeff( 1/(sqrt(1 -4*x +x*O(x^n)) -x), n))} /* Michael Somos, Apr 20 2007 */

my(x='x+O('x^66)); Vec( 1/(sqrt(1-4*x)-x) ) \\ Joerg Arndt, May 04 2013

(1/(sqrt(1-4*x)-x)).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, Jul 16 2019

From Wolfdieter Lang, Mar 21 2000: (Start)
G.f.: 1/(sqrt(1-4*x)-x).
a(n) = Sum_{i=1..n} a(i-1)*binomial(2*(n-i), n-i) + binomial(2*n, n), n >= 1, a(0)=1. (End)
G.f.: 1/(1 -x -2*x*c(x)) where c(x) = g.f. for Catalan numbers A000108. - Michael Somos, Apr 20 2007
From Paul Barry, Jan 25 2009: (Start)
G.f.: 1/(1 - 3xc(x) + x^2*c(x)^2);
G.f.: 1/(1-3x-2x^2/(1-2x-x^2/(1-2x-x^2/(1-2x-x^2/(1-... (continued fraction).
a(0) = 1, a(n) = Sum_{k=0..n} (k/(2n-k))*C(2n-k,n-k)*F(2k+2). (End)
a(n) = Sum_{k=0..n} A039599(n,k) * A000045(k+2). - Philippe Deléham, Feb 11 2009
From Paul Barry, Feb 08 2009: (Start)
G.f.: 1/(1-x/(1-2x/(1-x/(1-x/(1-x/(1-x/(1-x/(1-... (continued fraction);
G.f. of 1,1,3,... is 1/(1-x-2x/(1-x/(1-x/(1-x/(1-... (continued fraction). (End)
From Gary W. Adamson, Jul 14 2011: (Start)
a(n) = the upper left term in M^n, M = the infinite square production matrix:
  3, 2, 0, 0, 0, 0, ...
  1, 1, 1, 0, 0, 0, ...
  1, 1, 1, 1, 0, 0, ...
  1, 1, 1, 1, 1, 0, ...
  1, 1, 1, 1, 1, 1, ...
  ... (End)
From Vaclav Kotesovec, Oct 08 2012: (Start)
D-finite with recurrence: n*a(n) = 2*(4*n-3)*a(n-1) - 3*(5*n-8)*a(n-2) - 2*(2*n-3)*a(n-3).
a(n) ~ (2+sqrt(5))^n/sqrt(5). (End)
a(n) = Sum_{k=0..n+1} 4^(n+1-k) * binomial(n-k/2,n+1-k). - Seiichi Manyama, Mar 30 2025
From Peter Luschny, Mar 30 2025: (Start)
a(n) = 4^n*(binomial(n-1/2, n)*hypergeom([1, (1-n)/2, -n/2], [1/2, 1/2-n], -1/4) + hypergeom([(1-n)/2, 1-n/2], [1-n], -1/4)/4) for n > 0.
a(n) = A001076(n) + A176280(n). (End)

A026674 a(n) = T(2n-1,n-1) = T(2n,n+1), T given by A026725.

Original entry on oeis.org

1, 4, 16, 65, 267, 1105, 4597, 19196, 80380, 337284, 1417582, 5965622, 25130844, 105954110, 447015744, 1886996681, 7969339643, 33670068133, 142301618265, 601586916703, 2543852427847, 10759094481491, 45513214057191, 192560373660245, 814807864164497

Offset: 1

Clark Kimberling

nonn

G. C. Greubel, Table of n, a(n) for n = 1..1000
Rob Arthan, Comments on A026674, A026725, A026670
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

Also a(n) = T(2n-1, n-1), T given by A026670.

List([1..30], n-> Sum([1..n], k-> Binomial(2*n, n+k)*Fibonacci(k+1) *(k/n) )); # G. C. Greubel, Jul 16 2019

R:=PowerSeriesRing(Rationals(), 30); Coefficients(R!( (-1+5*x +(1-x)*Sqrt(1-4*x))/(2*(1-4*x-x^2)) )); // G. C. Greubel, Jul 16 2019

a := n -> add(binomial(2*n,n+k)*combinat:-fibonacci(1+k)*(k/n), k=1..n):
seq(a(n), n=1..30); # Peter Luschny, Apr 28 2016

a[n_] := Sum[Binomial[2n, n+k] Fibonacci[k+1] k/n, {k, 1, n}];
Array[a, 30] (* Jean-François Alcover, Jun 21 2018, after Peter Luschny *)

a(n):=sum(k*binomial(2*n,n-k)*(sum(binomial(k-i,i),i,0,k/2)),k,1,n)/n; /* Vladimir Kruchinin, Apr 28 2016 */

a(n)=sum(k=1,n,k*binomial(2*n,n-k)*sum(i=0,k\2,binomial(k-i,i)))/n \\ Charles R Greathouse IV, Apr 28 2016

a=((-1+5*x +(1-x)*sqrt(1-4*x))/(2*(1-4*x-x^2))).series(x, 30).coefficients(x, sparse=False); a[1:] # G. C. Greubel, Jul 16 2019

G.f.: (1/2)*((1-x)/(sqrt(1-4*x)-x) - 1). - Ralf Stephan, Feb 05 2004
G.f.: x*c(x)^3/(1-x*c(x)^3) = (1-5*x -(1-x)*sqrt(1-4*x))/(2*(x^2+4*x-1)), c(x) the g.f. of A000108. - Paul Barry, Mar 19 2007
From Gary W. Adamson, Jul 11 2011: (Start)
a(n) is the upper left term in M^n, where M is the following infinite square production matrix:
   1, 1, 0, 0, 0, 0, 0, ...
   3, 1, 1, 0, 0, 0, 0, ...
   6, 1, 1, 1, 0, 0, 0, ...
  10, 1, 1, 1, 1, 0, 0, ...
  15, 1, 1, 1, 1, 1, 0, ...
  21, 1, 1, 1, 1, 1, 1, ...
  ... (End)
D-finite with recurrence n*a(n) +(-9*n+8)*a(n-1) +23*(n-2)*a(n-2) +(-11*n+48)*a(n-3) +2*(-2*n+7)*a(n-4)=0. - R. J. Mathar, Nov 26 2012
a(n) = (1/n)*Sum_{k=1..n} k*binomial(2*n,n-k)*Sum_{i=0..k/2} binomial(k-i,i). - Vladimir Kruchinin, Apr 28 2016
a(n) ~ (3 - sqrt(5)) * (2 + sqrt(5))^n / (2*sqrt(5)). - Vaclav Kotesovec, Jul 18 2019

cp's OEIS Frontend

A026983 a(n) = Sum_{k=0..n-2} T(n,k) * T(n,k+2), with T given by A026670.

Views

Author

Keywords

Extensions

A026984 a(n) = Sum_{k=0..n-3} T(n,k) * T(n,k+3), with T given by A026670.

Views

Author

Keywords

Extensions

A026985 a(n) = Sum_{k=0..n} (k+1) * A026670(n, k).

Views

Author

Keywords

A026725 Triangular array, T, read by rows: T(n,0) = T(n,n) = 1. For n >= 2 and 1<=k<=n-1, T(n,k) = T(n-1,k-1) + T(n-2,k-1) + T(n-1,k) if n is odd and k=n/2, otherwise T(n,k) = T(n-1,k-1) + T(n-1,k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

Sage

Formula

Extensions

A026671 Number of lattice paths from (0,0) to (n,n) with steps (0,1), (1,0) and, when on the diagonal, (1,1).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

PARI

Sage

Formula

A026674 a(n) = T(2n-1,n-1) = T(2n,n+1), T given by A026725.

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

Maxima

PARI

Sage

Formula