A001333 -id:A001333 - cp's OEIS frontend

A113413 A Riordan array of coordination sequences.

1, 2, 1, 2, 4, 1, 2, 8, 6, 1, 2, 12, 18, 8, 1, 2, 16, 38, 32, 10, 1, 2, 20, 66, 88, 50, 12, 1, 2, 24, 102, 192, 170, 72, 14, 1, 2, 28, 146, 360, 450, 292, 98, 16, 1, 2, 32, 198, 608, 1002, 912, 462, 128, 18, 1, 2, 36, 258, 952, 1970, 2364, 1666, 688, 162, 20, 1, 2, 40, 326

Offset: 0

Paul Barry, Oct 29 2005

Columns include A040000, A008574, A005899, A008412, A008413, A008414. Row sums are A078057(n)=A001333(n+1). Diagonal sums are A001590(n+3). Reverse of A035607. Signed version is A080246. Inverse is A080245.
For another version see A122542. - Philippe Deléham, Oct 15 2006
T(n,k) is the number of length n words on alphabet {0,1,2} with no two consecutive 1's and no two consecutive 2's and having exactly k 0's. - Geoffrey Critzer, Jun 11 2015
From Eric W. Weisstein, Feb 17 2016: (Start)
Triangle of coefficients (from low to high degree) of x^-n * vertex cover polynomial of the n-ladder graph P_2 \square p_n:
  Psi_{L_1}: x*(2 + x) -> {2, 1}
  Psi_{L_2}: x^2*(2 + 4 x + x^2) -> {2, 4, 1}
  Psi_{L_3}: x^3*(2 + 8 x + 6 x^2 + x^3) -> {2, 8, 6, 1}
(End)
Let c(n, k), n > 0, be multiplicative sequences for some fixed integer k >= 0 with c(p^e, k) = T(e+k, k) for prime p and e >= 0. Then we have Dirichlet g.f.: Sum_{n>0} c(n, k) / n^s = zeta(s)^(2*k+2) / zeta(2*s)^(k+1). Examples: For k = 0 see A034444 and for k = 1 see A322328. Dirichlet convolution of c(n, k) and lambda(n) is Dirichlet inverse of c(n, k). - Werner Schulte, Oct 31 2022

			Triangle begins
  1;
  2,  1;
  2,  4,  1;
  2,  8,  6,  1;
  2, 12, 18,  8,  1;
  2, 16, 38, 32, 10,  1;
  2, 20, 66, 88, 50, 12,  1;

G. C. Greubel, Table of n, a(n) for the first 50 rows
Bela Bajnok, Additive Combinatorics: A Menu of Research Problems, arXiv:1705.07444 [math.NT], May 2017. See Sect. 2.3.
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
P. Holub, M. Miller, H. Perez-Roses, and J. Ryan, Degree diameter problem on honeycomb networks, Disc. Appl. Math. 179 (2014) 139-151.
Milan Janjić, Words and Linear Recurrences, J. Int. Seq. 21 (2018), #18.1.4.
Huyile Liang, Yanni Pei, and Yi Wang, Analytic combinatorics of coordination numbers of cubic lattices, arXiv:2302.11856 [math.CO], 2023. See p. 2.
Mirka Miller, Hebert Perez-Roses, and Joe Ryan, The Maximum Degree-and-Diameter-Bounded Subgraph in the Mesh, arXiv preprint arXiv:1203.4069 [math.CO], 2012.

Other versions: A035607, A119800, A122542, A266213.

nn = 10; Map[Select[#, # > 0 &] &, CoefficientList[Series[1/(1 - 2 x/(1 + x) - y x), {x, 0, nn}], {x, y}]] // Grid (* Geoffrey Critzer, Jun 11 2015 *)
CoefficientList[CoefficientList[Series[1/(1 - 2 x/(1 + x) - y x), {x, 0, 10}, {y, 0, 10}], x], y] (* Eric W. Weisstein, Feb 17 2016 *)

T = lambda n,k : binomial(n, k)*hypergeometric([-k-1, k-n], [-n], -1).simplify_hypergeometric()
A113413 = lambda n,k : 1 if n==0 and k==0 else T(n, k)
for n in (0..12): print([A113413(n,k) for k in (0..n)]) # Peter Luschny, Sep 17 2014 and Mar 16 2016

# Alternatively:
def A113413_row(n):
    @cached_function
    def prec(n, k):
        if k==n: return 1
        if k==0: return 0
        return prec(n-1,k-1)+2*sum(prec(n-i,k-1) for i in (2..n-k+1))
    return [prec(n, k) for k in (1..n)]
for n in (1..10): print(A113413_row(n)) # Peter Luschny, Mar 16 2016

From Paul Barry, Nov 13 2005: (Start)
Riordan array ((1+x)/(1-x), x(1+x)/(1-x)).
T(n, k) = Sum_{i=0..n-k} C(k+1, i)*C(n-i, k).
T(n, k) = Sum_{j=0..n-k} C(k+j, j)*C(k+1, n-k-j).
T(n, k) = D(n, k) + D(n-1, k) where D(n, k) = Sum_{j=0..n-k} C(n-k, j)*C(k, j)*2^j = A008288(n, k).
T(n, k) = T(n-1, k) + T(n-1, k-1) + T(n-2, k-1).
T(n, k) = Sum_{j=0..n} C(floor((n+j)/2), k)*C(k, floor((n-j)/2)). (End)
T(n, k) = C(n, k)*hypergeometric([-k-1, k-n], [-n], -1). - Peter Luschny, Sep 17 2014
T(n, k) = (Sum_{i=2..k+2} A137513(k+2, i) * (n-k)^(i-2)) / (k!) for 0 <= k < n (conjectured). - Werner Schulte, Oct 31 2022

A089934 Table T(n,k) of the number of n X k matrices on {0,1} without adjacent 0's in any row or column.

Original entry on oeis.org

2, 3, 3, 5, 7, 5, 8, 17, 17, 8, 13, 41, 63, 41, 13, 21, 99, 227, 227, 99, 21, 34, 239, 827, 1234, 827, 239, 34, 55, 577, 2999, 6743, 6743, 2999, 577, 55, 89, 1393, 10897, 36787, 55447, 36787, 10897, 1393, 89, 144, 3363, 39561, 200798, 454385, 454385, 200798

Offset: 1

Marc LeBrun, Nov 15 2003

Recurrence orders are A089935. n X 1/1 X n patterns interpreted as binary values is A003714.
Number of independent vertex sets in the P_n X P_k grid graph. - Andrew Howroyd, Jun 06 2017
All columns (or rows) are linear recurrences with constant coefficients and order of the recurrence <= A001224(k+1). - Andrew Howroyd, Dec 24 2019
The enumeration of tiling "W-shaped" polyominoes in a (n+1) X (k+1) rectangle, whose shapes are (no flipping or rotating allowed):
   .. .._.   ...     ...
   || ||_| .||_|   .||_|
       ||   ||_|   .||_|
             ||     ||_|
                     ||       ... - _Liang Kai, Apr 19 2025

			Table starts:
  ========================================================
  n\k|  1   2     3      4       5        6          7
  ---|----------------------------------------------------
  1  |  2   3     5      8      13       21         34 ...
  2  |  3   7    17     41      99      239        577 ...
  3  |  5  17    63    227     827     2999      10897 ...
  4  |  8  41   227   1234    6743    36787     200798 ...
  5  | 13  99   827   6743   55447   454385    3729091 ...
  6  | 21 239  2999  36787  454385  5598861   69050253 ...
  7  | 34 577 10897 200798 3729091 69050253 1280128950 ...
  ... - _Andrew Howroyd_, Jun 06 2017
a(2,2)=7:
  11 11 11 10 10 01 01
  11 10 01 11 01 11 10

Liang Kai, Antidiagonals n = 1..77, flattened (antidiagonals n = 1..49 from Alois P. Heinz)
Kai Liang, Independent Set Enumeration and Estimation of Related Constants of Grid Graphs, arXiv:2507.04007 [math.CO], 2025. See p. 4.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Independent Vertex Set

T(n, 0) = T(0, m) = 1. Zero based table is A089980.
Rows 1-7 are A000045, A001333, A051736, A051737, A089936, A089937, A089938.
Main diagonal is A006506.
Cf. A089935, A001224, A197054 (maximal independent sets), A218354, A003714.

step(v, S)={vector(#v, i, sum(j=1, #v, v[j]*!bitand(S[i], S[j])))}
mkS(k)={select(b->!bitand(b,b>>1), [0..2^k-1])}
T(n,k)={my(S=mkS(k), v=vector(#S, i, i==1)); for(n=1, n, v=step(v,S)); vecsum(v)} \\ Andrew Howroyd, Dec 24 2019

A041006 Numerators of continued fraction convergents to sqrt(6).

Original entry on oeis.org

2, 5, 22, 49, 218, 485, 2158, 4801, 21362, 47525, 211462, 470449, 2093258, 4656965, 20721118, 46099201, 205117922, 456335045, 2030458102, 4517251249, 20099463098, 44716177445, 198964172878, 442644523201, 1969542265682, 4381729054565, 19496458483942

Offset: 0

N. J. A. Sloane

Interspersion of 2 sequences, 2*A054320 and A001079. - Gerry Martens, Jun 10 2015

Hugo Pfoertner, Table of n, a(n) for n = 0..100
Index entries for linear recurrences with constant coefficients, signature (0,10,0,-1).

Cf. A041007 (denominators).
Cf. A054320, A001079.
Analog for other sqrt(m): A001333 (m=2), A002531 (m=3), A001077 (m=5), A041008 (m=7), A041010 (m=8), A005667 (m=10), A041014 (m=11), ..., A042936 (m=1000).

I:=[2, 5, 22, 49]; [n le 4 select I[n] else 10*Self(n-2)-Self(n-4): n in [1..30]]; // Vincenzo Librandi, Jun 10 2015

Table[Numerator[FromContinuedFraction[ContinuedFraction[Sqrt[6],n]]],{n,1,50}] (* Vladimir Joseph Stephan Orlovsky, Mar 16 2011 *)
LinearRecurrence[{0, 10, 0, -1}, {2, 5, 22, 49}, 50] (* Vincenzo Librandi, Jun 10 2015 *)

A41006=contfracpnqn(c=contfrac(sqrt(6)), #c)[1, ][^-1] \\ Discard possibly incorrect last element. NB: a(n)=A41006[n+1]! M. F. Hasler, Nov 01 2019

\\ For correct index & more terms:
A041006(n)={n<#A041006|| A041006=extend(A041006, [2, 10; 4, -1], n\.8); A041006[n+1]}
extend(A, c, N)={for(n=#A+1, #A=Vec(A, N), A[n]=[A[n-i]|i<-c[, 1]]*c[, 2]); A} \\ M. F. Hasler, Nov 01 2019

From M. F. Hasler, Feb 13 2009: (Start)
a(2n) = 2*A142238(2n) = A041038(2n)/2;
a(2n-1) = A142238(2n-1) = A041038(2n-1) = A001079(n). (End)
G.f.: (2 + 5*x + 2*x^2 - x^3)/(1 - 10*x^2 + x^4).
a(n) = ((2 + sqrt(6))^(n+1) + (2 - sqrt(6))^(n+1))/2^(ceiling(n/2) + 1). - Robert FERREOL, Oct 13 2024
E.g.f.: sqrt(2)*sinh(sqrt(2)*x)*(cosh(sqrt(3)*x) + sqrt(3)*sinh(sqrt(3)*x)) + cosh(sqrt(2)*x)*(2*cosh(sqrt(3)*x) + sqrt(3)*sinh(sqrt(3)*x)). - Stefano Spezia, Oct 14 2024

More terms from Vincenzo Librandi, Jun 10 2015

A046729 Expansion of 4x/((1+x)(1-6*x+x^2)).

Original entry on oeis.org

0, 4, 20, 120, 696, 4060, 23660, 137904, 803760, 4684660, 27304196, 159140520, 927538920, 5406093004, 31509019100, 183648021600, 1070379110496, 6238626641380, 36361380737780, 211929657785304, 1235216565974040, 7199369738058940, 41961001862379596, 244566641436218640

Offset: 0

N. J. A. Sloane

Related to Pythagorean triples: alternate terms of A001652 and A046090.
Even-valued legs of nearly isosceles right triangles: legs differ by 1. 0 is smaller leg of degenerate triangle with legs 0 and 1 and hypotenuse 1. - Charlie Marion, Nov 11 2003
The complete (nearly isosceles) primitive Pythagorean triple is given by {a(n), a(n)+(-1)^n, A001653(n)}. - Lekraj Beedassy, Feb 19 2004
Note also that A046092 is the even leg of this other class of nearly isosceles Pythagorean triangles {A005408(n), A046092(n), A001844(n)}, i.e., {2n+1, 2n(n+1), 2n(n+1)+1} where longer sides (viz. even leg and hypotenuse) are consecutive. - Lekraj Beedassy, Apr 22 2004
Union of even terms of A001652 and A046090. Sum of legs of primitive Pythagorean triangles is A002315(n) = 2*a(n) + (-1)^n. - Lekraj Beedassy, Apr 30 2004

			[1,0,1]*[1,2,2; 2,1,2; 2,2,3]^0 gives (degenerate) primitive Pythagorean triple [1, 0, 1], so a(0) = 0. [1,0,1]*[1,2,2; 2,1,2; 2,2,3]^7 gives primitive Pythagorean triple [137903, 137904, 195025] so a(7) = 137904.
G.f. = 4*x + 20*x^2 + 120*x^3 + 696*x^4 + 4060*x^5 + 23660*x^6 + ...

A. H. Beiler, Recreations in the Theory of Numbers. New York: Dover, pp. 122-125, 1964.
W. Sierpiński, Pythagorean triangles, Dover Publications, Inc., Mineola, NY, 2003, p. 17. MR2002669.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5,5,-1).
Index entries for two-way infinite sequences

Cf. A000129, A001109, A001333, A001652, A002315, A029549, A046090.

Cf. A046727, A047235, A084158, A084159, A089499, A114336.

[4*Floor(((Sqrt(2)+1)^(2*n+1)-(Sqrt(2)-1)^(2*n+1)-2*(-1)^n) / 16): n in [0..30]]; // Vincenzo Librandi, Jul 29 2019

LinearRecurrence[{5,5,-1}, {0,4,20}, 25] (* Vincenzo Librandi, Jul 29 2019 *)

a(n)=n%2+(real((1+quadgen(8))^(2*n+1))-1)/2

a(n)=if(n<0,-a(-1-n),polcoeff(4*x/(1+x)/(1-6*x+x^2)+x*O(x^n),n))

[(lucas_number2(2*n+1,2,-1) -2*(-1)^n)/4 for n in range(41)] # G. C. Greubel, Feb 11 2023

a(n) = ((1+sqrt(2))^(2n+1) + (1-sqrt(2))^(2n+1) + 2*(-1)^(n+1))/4.
a(n) = A089499(n)*A089499(n+1).
a(n) = 4*A084158(n). - Lekraj Beedassy, Jul 16 2004
a(n) = ceiling((sqrt(2)+1)^(2*n+1) - (sqrt(2)-1)^(2*n+1) - 2*(-1)^n)/4. - Lambert Klasen (Lambert.Klasen(AT)gmx.net), Nov 12 2004
a(n) is the k-th entry among the complete near-isosceles primitive Pythagorean triple A114336(n), where k = (3*(2n-1) - (-1)^n)/2, i.e., a(n) = A114336(A047235(n)), for positive n. - Lekraj Beedassy, Jun 04 2006
a(n) = A046727(n) - (-1)^n = 2*A114620(n). - Lekraj Beedassy, Aug 14 2006
From George F. Johnson, Aug 29 2012: (Start)
2*a(n)*(a(n) + (-1)^n) + 1 = (A000129(2*n+1))^2;
n > 0, 2*a(n)*(a(n) + (-1)^n) + 1 = ((a(n+1) - a(n-1))/4)^2, a perfect square.
a(n+1) = (3*a(n) + 2*(-1)^n) + 2*sqrt(2*a(n)*(a(n) + (-1)^n)+ 1).
a(n-1) = (3*a(n) + 2*(-1)^n) - 2*sqrt(2*a(n)*(a(n) + (-1)^n)+ 1).
a(n+1) = 6*a(n) - a(n-1) + 4*(-1)^n.
a(n+1) = 5*a(n) + 5*a(n-1) - a(n-2).
a(n+1) *a(n-1) = a(n)*(a(n) + 4*(-1)^n).
a(n) = (sqrt(1 + 8*A029549(n)) - (-1)^n)/2.
a(n) = A002315(n) - A084159(n) = A084159(n) - (-1)^n.
a(n)  = A001652(n) + (1 - (-1)^n)/2 = A046090(n) - (1 + (-1)^n)/2.
Limit_{n->oo} a(n)/a(n-1) =  3 + 2*sqrt(2).
Limit_{n->oo} a(n)/a(n-2) = 17 + 12*sqrt(2).
Limit_{n->oo} a(n)/a(n-r) = (3 + 2*sqrt(2))^r.
Limit_{n->oo} a(n-r)/a(n) = (3 - 2*sqrt(2))^r. (End)
From G. C. Greubel, Feb 11 2023: (Start)
a(n) = (A001333(2*n+1) - 2*(-1)^n)/4.
a(n) = (1/2)*(A001109(n+1) + A001109(n) - (-1)^n). (End)
E.g.f.: exp(-x)*(exp(4*x)*(cosh(2*sqrt(2)*x) + sqrt(2)*sinh(2*sqrt(2)*x)) - 1)/2. - Stefano Spezia, Aug 03 2024

A084128 a(n) = 4a(n-1) + 4a(n-2), a(0)=1, a(1)=2.

Original entry on oeis.org

1, 2, 12, 56, 272, 1312, 6336, 30592, 147712, 713216, 3443712, 16627712, 80285696, 387653632, 1871757312, 9037643776, 43637604352, 210700992512, 1017354387456, 4912221519872, 23718303629312, 114522100596736, 552961616904192, 2669934870003712

Offset: 0

Paul Barry, May 16 2003

Original name was: Generalized Fibonacci sequence.

Binomial transform of A084058.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
Tanya Khovanova, Recursive Sequences
Index entries for linear recurrences with constant coefficients, signature (4,4).

Cf. A001333 A001541, A002203, A057087, A084058, A084128, A201730.

Appears in A086346, A086347 and A086348. - Johannes W. Meijer, Aug 01 2010

[2^(n-1)*Evaluate(DicksonFirst(n,-1), 2): n in [0..40]]; // G. C. Greubel, Oct 13 2022

a:=proc(n) option remember; if n=0 then 1 elif n=1 then 2 else
4*a(n-1)+4*a(n-2); fi; end: seq(a(n), n=0..40); # Wesley Ivan Hurt, Jan 31 2017
a := n -> (2*I)^n*ChebyshevT(n, -I):
seq(simplify(a(n)), n = 0..23); # Peter Luschny, Dec 03 2023

CoefficientList[Series[(2 z - 1)/(4 z^2 + 4 z - 1), {z, 0, 100}], z] (* Vladimir Joseph Stephan Orlovsky, Jul 01 2011 *)
Table[2^(n-1) LucasL[n, 2], {n, 0, 20}] (* Vladimir Reshetnikov, Oct 07 2016 *)
LinearRecurrence[{4,4},{1,2},30] (* Harvey P. Dale, Mar 01 2018 *)

a(n)=if(n<0,0,polsym(4+4*x-x^2,n)[n+1]/2)

[lucas_number2(n,4,-4)/2 for n in range(0, 23)] # Zerinvary Lajos, May 14 2009

a(n) = 2^n * A001333(n).
G.f.: (1-2*x)/(1-4*x-4*x^2).
a(n) = 4*a(n-1) + 4*a(n-2), a(0)=1, a(1)=2.
a(n) = (2 + 2*sqrt(2))^n/2 + (2 - 2*sqrt(2))^n/2.
E.g.f.: exp(2*x)*cosh(2*x*sqrt(2)).
From Johannes W. Meijer, Aug 01 2010: (Start)
Lim_{k->infinity} a(n+k)/a(k) = A084128(n) + 2*A057087(n-1)*sqrt(2).
Lim_{n->infinity} A084128(n)/A057087(n-1) = sqrt(2). (End)
a(n) = Sum_{k=0..n} A201730(n,k)*7^k. - Philippe Deléham, Dec 06 2011
G.f.: G(0)/2, where G(k)= 1 + 1/(1 - x*(4*k-2)/(x*(4*k+2) - 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 27 2013
a(n) = 2^(n-1)*A002203(n). - Vladimir Reshetnikov, Oct 07 2016

A084159 Pell oblongs.

Original entry on oeis.org

1, 3, 21, 119, 697, 4059, 23661, 137903, 803761, 4684659, 27304197, 159140519, 927538921, 5406093003, 31509019101, 183648021599, 1070379110497, 6238626641379, 36361380737781, 211929657785303, 1235216565974041, 7199369738058939, 41961001862379597, 244566641436218639

Offset: 0

Paul Barry, May 18 2003

Essentially the same as A046727.

Albert H. Beiler, Recreations in the theory of numbers, New York, Dover, (2nd ed.) 1966. See Table 60 at p. 123.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
P. E. Trier, "Almost Isosceles" Right-Angled Triangles, Eureka, No. 4, May 1940, pp. 9 - 11.
Index entries for linear recurrences with constant coefficients, signature (5,5,-1).

Cf. A046727 (same sequence except for first term).

Cf. A001333, A001654, A078057, A084158, A084175, A090390, A182432, A211955.

[Floor(((Sqrt(2)+1)^(2*n+1)-(Sqrt(2)-1)^(2*n+1)+2*(-1)^n)/4): n in [0..30]]; // Vincenzo Librandi, Aug 13 2011

b[n_]:= Numerator[FromContinuedFraction[ContinuedFraction[Sqrt[2], n]]];
Join[{1}, Table[b[n+1], {n,50}]*Table[b[n], {n,50}]] (* Vladimir Joseph Stephan Orlovsky, Jan 15 2011 *)
LinearRecurrence[{5,5,-1},{1,3,21},30] (* Harvey P. Dale, Aug 04 2019 *)

[(lucas_number2(2*n+1, 2, -1) + 2*(-1)^n)/4 for n in range(31)] # G. C. Greubel, Oct 11 2022

a(n) = ((sqrt(2)+1)^(2*n+1) - (sqrt(2)-1)^(2*n+1) + 2*(-1)^n)/4.
a(n) = 5*a(n-1) + 5*a(n-2) - a(n-3). - Paul Curtz, May 17 2008
G.f.: (1-x)^2/((1+x)*(1-6*x+x^2)). - R. J. Mathar, Sep 17 2008
a(n) = A078057(n)*A001333(n). - R. J. Mathar, Jul 08 2009
a(n) = A001333(n)*A001333(n+1).
From Peter Bala, May 01 2012: (Start)
a(n) = (-1)^n*R(n,-4), where R(n,x) is the n-th row polynomial of A211955.
a(n) = (-1)^n*1/u*T(n,u)*T(n+1,u) with u = sqrt(-1) and T(n,x) the Chebyshev polynomial of the first kind.
a(n) = (-1)^n + 4*Sum_{k = 1..n} (-1)^(n-k)*8^(k-1)*binomial(n+k,2*k).
Recurrence equations: a(n) = 6*a(n-1) - a(n-2) + 4*(-1)^n, with a(0) = 1 and a(1) = 3; a(n)*a(n-2) = a(n-1)*(a(n-1)+4*(-1)^n).
Sum_{k >= 0} (-1)^k/a(k) = 1/sqrt(2).
1 - 2*(Sum_{k = 0..n} (-1)^k/a(k))^2 = (-1)^(n+1)/A090390(n+1). (End)
a(n) = (A001333(2*n+1) + (-1)^n)/2. - G. C. Greubel, Oct 11 2022
E.g.f.: exp(-x)*(1 + exp(4*x)*(cosh(2*sqrt(2)*x) + sqrt(2)*sinh(2*sqrt(2)*x)))/2. - Stefano Spezia, Aug 03 2024

A097076 Expansion of g.f. x/(1 - x - 3*x^2 - x^3).

Original entry on oeis.org

0, 1, 1, 4, 8, 21, 49, 120, 288, 697, 1681, 4060, 9800, 23661, 57121, 137904, 332928, 803761, 1940449, 4684660, 11309768, 27304197, 65918161, 159140520, 384199200, 927538921, 2239277041, 5406093004, 13051463048, 31509019101, 76069501249, 183648021600

Offset: 0

Paul Barry, Jul 22 2004

Counts walks of length n between two vertices of a triangle, when a loop has been added at the third vertex.
a(n) is the center term of the 3 X 3 matrix [0,1,0; 0,0,1; 1,3,1]^n. - Gary W. Adamson, May 30 2008
Starting (1, 1, 4, 8, 21, ...) = row sums of triangle A157898. - Gary W. Adamson, Mar 08 2009
Convolution of Pell(n) = A000129(n) and (-1)^n. - Paul Barry, Oct 22 2009
a(n+1) is the number of ways to choose points on a 2 X n lattice eliminating the upper left and lower right corners such that the points are not adjacent to each other. (See A375726 for proof) - Yifan Xie, Aug 25 2024
a(n+1) is the number of compositions (ordered partitions) of n into parts 1, 2, and 3 where there are three kinds of part 2. - Joerg Arndt, Aug 27 2024

G. C. Greubel, Table of n, a(n) for n = 0..1000
J. Bodeen, S. Butler, T. Kim, X. Sun and S. Wang, Tiling a strip with triangles, El. J. Combinat. 21 (1) (2014) P1.7.
Mark Shattuck, Combinatorial Proofs of Some Formulas for Triangular Tilings, Journal of Integer Sequences, 17 (2014), #14.5.5.
Index entries for linear recurrences with constant coefficients, signature (1,3,1).

Cf. A000129, A001333, A051927, A097075, A110048, A157898, A375726.

[(Evaluate(DicksonFirst(n,-1), 2) -2*(-1)^n)/4: n in [0..40]]; // G. C. Greubel, Aug 18 2022

CoefficientList[Series[x/(1-x-3x^2-x^3),{x,0,40}],x] (* or *) LinearRecurrence[{1,3,1},{0,1,1},40]  (* Vladimir Joseph Stephan Orlovsky, Jan 30 2012 *)

[(lucas_number2(n,2,-1) -2*(-1)^n)/4 for n in (0..40)] # G. C. Greubel, Aug 18 2022

a(n) = ( (1+sqrt(2))^n + (1-sqrt(2))^n - 2*(-1)^n )/4.
a(n) = a(n-1) + 3*a(n-2) + a(n-3). [corrected by Paul Curtz, Mar 04 2008]
a(n) = (Sum_{k=0..floor(n/2)} binomial(n, 2*k)*2^k)/2 - (-1)^n/2.
a(n) = (A001333(n) - (-1)^n)/2.
a(n) = Sum_{k=0..n} (-1)^k*Pell(n-k). - Paul Barry, Oct 22 2009
From R. J. Mathar, Jul 06 2011: (Start)
G.f.: x / ( (1+x)*(1-2*x-x^2) ).
a(n) + a(n+1) = A000129(n+1). (End)
E.g.f.: (exp(x)*cosh(sqrt(2)*x) - cosh(x) + sinh(x))/2. - Stefano Spezia, Mar 31 2024

A359576 Array read by antidiagonals: T(m,n) is the number of m X n binary arrays with a path of adjacent 1's from top row to bottom row.

Original entry on oeis.org

1, 3, 1, 7, 7, 1, 15, 37, 17, 1, 31, 175, 197, 41, 1, 63, 781, 1985, 1041, 99, 1, 127, 3367, 18621, 22193, 5503, 239, 1, 255, 14197, 167337, 433809, 247759, 29089, 577, 1, 511, 58975, 1461797, 8057905, 10056959, 2764991, 153769, 1393, 1, 1023, 242461, 12519345, 144769425, 384479935, 232824241, 30856705, 812849, 3363, 1

Offset: 1

Andrew Howroyd, Jan 06 2023

The grid has m rows and n columns.
"Path" refers to a sequence of L(eft), R(ight), U(p), D(own) steps (edge connectivity like in fixed polyominoes), self-avoiding, starting anywhere in the first row and ending anywhere in the last row. The path does not need to step on all 1's of the array. The path has obviously at least m-1 steps. - R. J. Mathar, Jun 21 2023
Note that the total would be smaller if Up steps were disallowed (as in the original comment above); the smallest grid size for which this phenomenon occurs is 4 X 5. The total number of 4 X 5 and 5 X 5 grids would be 433801 instead of 433809 and 10056087 instead of 10056959, respectively, without Up steps. - Caleb Stanford, Feb 01 2024
Each row and each column satisfies a linear recurrence with constant coefficients. - Pontus von Brömssen, Feb 05 2025

			Array begins:
====================================================================
m\n| 1   2      3        4          5            6             7
---+----------------------------------------------------------------
1  | 1   3      7       15         31           63           127 ...
2  | 1   7     37      175        781         3367         14197 ...
3  | 1  17    197     1985      18621       167337       1461797 ...
4  | 1  41   1041    22193     433809      8057905     144769425 ...
5  | 1  99   5503   247759   10056959    384479935   14142942975 ...
6  | 1 239  29089  2764991  232824241  18287614751 1374273318721 ...
7  | 1 577 153769 30856705 5388274121 868972410929 ...
  ...
All the 37 2 X 3 binary arrays:
001 001 001 001
001 011 101 111 plus 4 copies left-right flipped
.
010 010 010 010
010 011 110 111
.
011 011 011 011 011 011
001 010 011 101 110 111 plus 6 copies left-right flipped
.
101 101 101 101 101 101
001 011 100 101 110 111
.
111 111 111 111 111 111 111
001 010 011 100 101 110 111 - _R. J. Mathar_, Jun 21 2023

Samuel Dittmer, Hiram Golze, Grant Molnar, and Caleb Stanford, Puzzle and Proof: A Decade of Problems from the Utah Math Olympiad, CRC Press, 2025, p. 51.

Caleb Stanford, Rust program to compute the sequence.
Utah Math Olympiad 2022, Problem 6.

Main diagonal is A365988.
Rows 1..19 are A000225, A005061, A069361, A069362, A069363-A069377.
Columns 1..20 are A000012, A001333(n+1), A069378, A069379, A069380-A069395.
Cf. A359574, A359575.

One additional diagonal of terms added by Caleb Stanford, Feb 05 2024

A069362 Number of 4 X n binary arrays with a path of adjacent 1's from top row to bottom row.

Original entry on oeis.org

1, 41, 1041, 22193, 433809, 8057905, 144769425, 2541013617, 43843180113, 746691527217, 12588144461329, 210502738714097, 3497001564166609, 57781030561348017, 950437243856526737, 15574913193760097649, 254416775893204873553, 4144677558181255455025

Offset: 1

R. H. Hardin, Mar 22 2002

Colin Barker, Table of n, a(n) for n = 1..800
Index entries for linear recurrences with constant coefficients, signature (35,-378,1264,-1272,-128).

Row 4 of A359576.

Cf. 1 X n A000225, 2 X n A005061, n X 2 A001333, vertical path of 1 A069361-A069395, vertical paths of 0+1 A069396-A069416, vertical path of 1 not 0 A069417-A069428, no vertical paths A069429-A069447, no horizontal or vertical paths A069448-A069452.

m:=25; R:=PowerSeriesRing(Integers(), m); Coefficients(R!(x*(1+6*x-16*x^2-8*x^3)/((1-16*x)*(1-19*x+ 74*x^2 -80*x^3-8*x^4)))); // G. C. Greubel, Apr 22 2018

Rest[CoefficientList[Series[x*(1+6*x-16*x^2-8*x^3)/((1-16*x)*(1-19*x+ 74*x^2 -80*x^3-8*x^4)), {x,0,50}],x]] (* G. C. Greubel, Apr 22 2018 *)
LinearRecurrence[{35,-378,1264,-1272,-128},{1,41,1041,22193,433809},20] (* Harvey P. Dale, Jan 01 2019 *)

Vec(x*(1 + 6*x - 16*x^2 - 8*x^3) / ((1 - 16*x)*(1 - 19*x + 74*x^2 - 80*x^3 - 8*x^4)) + O(x^30)) \\ Colin Barker, Oct 12 2017

G.f.: x*(1 +6*x -16*x^2 -8*x^3)/((1 -16*x)*(1 -19*x +74*x^2 -80*x^3 - 8*x^4)).

A188866 T(n,k) is the number of n X k binary arrays without the pattern 0 1 diagonally, vertically or antidiagonally.

Original entry on oeis.org

2, 4, 3, 8, 7, 4, 16, 17, 10, 5, 32, 41, 26, 13, 6, 64, 99, 68, 35, 16, 7, 128, 239, 178, 95, 44, 19, 8, 256, 577, 466, 259, 122, 53, 22, 9, 512, 1393, 1220, 707, 340, 149, 62, 25, 10, 1024, 3363, 3194, 1931, 950, 421, 176, 71, 28, 11, 2048, 8119, 8362, 5275, 2658, 1193, 502, 203, 80, 31, 12

Offset: 1

R. H. Hardin, Apr 12 2011

Number of 0..n strings of length k and adjacent elements differing by one or less. (See link for bijection.) Equivalently, number of base (n+1) k digit numbers with adjacent digits differing by one or less. - Andrew Howroyd, Mar 30 2017
All rows are linear recurrences with constant coefficients. See PARI script to obtain generating functions. - Andrew Howroyd, Apr 15 2017
Equivalently, the number of walks of length k-1 on the path graph P_{n+1} with a loop added at each vertex. - Pontus von Brömssen, Sep 08 2021

			Table starts:
   2  4  8  16  32   64  128   256   512   1024   2048    4096    8192    16384
   3  7 17  41  99  239  577  1393  3363   8119  19601   47321  114243   275807
   4 10 26  68 178  466 1220  3194  8362  21892  57314  150050  392836  1028458
   5 13 35  95 259  707 1931  5275 14411  39371 107563  293867  802859  2193451
   6 16 44 122 340  950 2658  7442 20844  58392 163594  458356 1284250  3598338
   7 19 53 149 421 1193 3387  9627 27383  77923 221805  631469 1797957  5119593
   8 22 62 176 502 1436 4116 11814 33942  97582 280676  807574 2324116  6689624
   9 25 71 203 583 1679 4845 14001 40503 117263 339699  984515 2854281  8277153
  10 28 80 230 664 1922 5574 16188 47064 136946 398746 1161634 3385486  9869934
  11 31 89 257 745 2165 6303 18375 53625 156629 457795 1338779 3916897 11463989
Some solutions for 5 X 3:
  1 1 1   1 1 1   1 1 1   1 1 1   0 0 0   1 1 1   1 1 1
  1 1 1   0 0 1   0 1 1   1 1 1   0 0 0   1 0 0   1 0 1
  0 0 0   0 0 0   0 0 1   1 1 1   0 0 0   0 0 0   0 0 0
  0 0 0   0 0 0   0 0 0   1 1 0   0 0 0   0 0 0   0 0 0
  0 0 0   0 0 0   0 0 0   0 0 0   0 0 0   0 0 0   0 0 0

R. H. Hardin, Table of n, a(n) for n = 1..1741
Andrew Howroyd, Bijection with 0..n strings of length k.
Arnold Knopfmacher, Toufik Mansour, Augustine Munagi and Helmut Prodinger, Smooth words and Chebyshev polynomials, arXiv:0809.0551v1 [math.CO], 2008.

Columns 2..8 are A016777, A017257(n-1), A188861-A188865.
Rows 2..31 are A001333(n+1), A126358, A057960(n+1), A126360, A002714, A126362-A126386.
Main diagonal is A188860.
Cf. A276562, A220062.

rows = 11; rowGf[n_, x_] = 1 + (x*(n - (3*n + 2)*x) + (2*x^2)*(1 + ChebyshevU[n-1, (1-x)/(2*x)])/ChebyshevU[n, (1-x)/(2*x)])/(1-3*x)^2;
row[n_] := rowGf[n+1, x] + O[x]^(rows+1) // CoefficientList[#, x]& // Rest; T = Array[row, rows]; Table[T[[n-k+1, k]], {n, 1, rows}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Oct 07 2017, after Andrew Howroyd *)

\\ from Knopfmacher et al.
RowGf(k, x='x) = my(z=(1-x)/(2*x)); 1 + (x*(k-(3*k+2)*x) + (2*x^2)*(1+polchebyshev(k-1, 2, z))/polchebyshev(k, 2, z))/(1-3*x)^2;
T(n,k) = {polcoef(RowGf(n+1) + O(x*x^k),k)}
for(n=1, 10, print(Vec(RowGf(n+1) + O(x^11)))) \\ Andrew Howroyd, Apr 15 2017 [updated Mar 13 2021]

Empirical: T(n,1) = n + 1.
Empirical: T(n,2) = 3*n + 1.
Empirical: T(n,3) = 9*n - 1.
Empirical: T(n,4) = 27*n - 13 for n > 1.
Empirical: T(n,5) = 81*n - 65 for n > 2.
Empirical: T(n,6) = 243*n - 265 for n > 3.
Empirical: T(n,7) = 729*n - 987 for n > 4.
Empirical: T(n,8) = 2187*n - 3495 for n > 5.
Empirical: T(1,k) = 2*T(1,k-1).
Empirical: T(2,k) = 2*T(2,k-1) + T(2,k-2).
Empirical: T(3,k) = 3*T(3,k-1) - T(3,k-2).
Empirical: T(4,k) = 3*T(4,k-1) - 2*T(4,k-3).
Empirical: T(5,k) = 4*T(5,k-1) - 3*T(5,k-2) -   T(5,k-3).
Empirical: T(6,k) = 4*T(6,k-1) - 2*T(6,k-2) - 4*T(6,k-3) +   T(6,k-4).
Empirical: T(7,k) = 5*T(7,k-1) - 6*T(7,k-2) -   T(7,k-3) + 2*T(7,k-4).
Empirical: T(8,k) = 5*T(8,k-1) - 5*T(8,k-2) - 5*T(8,k-3) + 5*T(8,k-4) + T(8,k-5).

cp's OEIS Frontend

A113413 A Riordan array of coordination sequences.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Sage

Formula

A089934 Table T(n,k) of the number of n X k matrices on {0,1} without adjacent 0's in any row or column.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A041006 Numerators of continued fraction convergents to sqrt(6).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

Extensions

A046729 Expansion of 4*x/((1+x)*(1-6*x+x^2)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

SageMath

Formula

A084128 a(n) = 4*a(n-1) + 4*a(n-2), a(0)=1, a(1)=2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A084159 Pell oblongs.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

A046729 Expansion of 4x/((1+x)(1-6*x+x^2)).

A084128 a(n) = 4a(n-1) + 4a(n-2), a(0)=1, a(1)=2.