A047084 -id:A047084 - cp's OEIS frontend

A047080 Triangular array T read by rows: T(h,k)=number of paths from (0,0) to (k,h-k) using step-vectors (0,1), (1,0), (1,1) with no right angles between pairs of consecutive steps.

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 3, 3, 3, 1, 1, 4, 5, 5, 4, 1, 1, 5, 8, 9, 8, 5, 1, 1, 6, 12, 15, 15, 12, 6, 1, 1, 7, 17, 24, 27, 24, 17, 7, 1, 1, 8, 23, 37, 46, 46, 37, 23, 8, 1, 1, 9, 30, 55, 75, 83, 75, 55, 30, 9, 1, 1, 10, 38, 79, 118, 143, 143, 118, 79, 38, 10, 1

Offset: 0

Clark Kimberling

T(n,k) equals the number of reduced alignments between a string of length n and a string of length k. See Andrade et. al. - Peter Bala, Feb 04 2018

			E.g., row 3 consists of T(3,0)=1; T(3,1)=2; T(3,2)=2; T(3,3)=1.
Triangle begins:
  1;
  1,  1;
  1,  1,  1;
  1,  2,  2,  1;
  1,  3,  3,  3,  1;
  1,  4,  5,  5,  4,  1;
  1,  5,  8,  9,  8,  5,  1;
  1,  6, 12, 15, 15, 12,  6,  1;

Muniru A Asiru, Table of n, a(n) for n = 0..1325
H. Andrade, I. Area, J. J. Nieto, and A. Torres, The number of reduced alignments between two DNA sequences, BMC Bioinformatics (2014) Vol. 15: 94.

Cf. A047081, A047082, A047083, A047084, A047085, A047086, A047087, A047088.

Cf. A001590, A022856, A028310, A078042, A089071, A091337, A171155.

F:=Factorial;
p:= func< n,k | (&+[ (-1)^j*F(n+k-3*j)/(F(j)*F(n-2*j)*F(k-2*j)): j in [0..Min(Floor(n/2), Floor(k/2))]]) >;
q:= func< n,k | n eq 0 or k eq 0 select 0 else (&+[ (-1)^j*F(n+k-3*j-2)/(F(j)*F(n-2*j-1)*F(k-2*j-1)) : j in [0..Min(Floor((n-1)/2), Floor((k-1)/2))]]) >;
A:= func< n,k | p(n,k) - q(n,k) >;
A047080:= func< n,k | n eq 0 select 1 else A(n-k, k) >;
[[A(n,k): k in [1..6]]: n in [1..6]];
[A047080(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Oct 30 2022

T := proc(n, k) option remember; if n < 0 or k > n then return 0 fi;
if n < 3 then return 1 fi; if k < iquo(n,2) then return T(n, n-k) fi;
T(n-1, k-1) + T(n-1, k) - T(n-4, k-2)  end:
seq(seq(T(n,k), k=0..n), n=0..11); # Peter Luschny, Feb 11 2018

T[n_, k_] := T[n, k] = Which[n<0 || k>n, 0, n<3, 1, kJean-François Alcover, Jul 30 2018 *)

f=factorial
def p(n,k): return sum( (-1)^j*f(n+k-3*j)/(f(j)*f(n-2*j)*f(k-2*j)) for j in range(1+min((n//2), (k//2))) )
def q(n,k): return sum( (-1)^j*f(n+k-3*j-2)/(f(j)*f(n-2*j-1)*f(k-2*j-1)) for j in range(1+min(((n-1)//2), ((k-1)//2))) )
def A(n,k): return p(n,k) - q(n,k)
def A047080(n,k): return A(n-k, k)
flatten([[A047080(n,k) for k in range(n+1)] for n in range(14)]) # G. C. Greubel, Oct 30 2022

T(h, k) = T(h-1, k-1) + T(h-1, k) - T(h-4, k-2);
Writing T(h, k) = F(h-k, k), generating function for F is (1-xy)/(1-x-y+x^2y^2).
From Peter Bala, Feb 04 2018: (Start)
T(n, k) = (Sum_{i = 0..A} (-1)^i*(n+k-3*i)!/(i!*(n-2*i)!*(k-2*i)!)) - (Sum_{i = 0..B} (-1)^i*(n+k-3*i-2)!/(i!*(n-2*i-1)!*(k-2*i-1)!)), where A = min{floor(n/2), floor(k/2)} and B = min{floor((n-1)/2), floor((k-1)/2)}.
T(2*n, n) = A171155(n). (End)
From G. C. Greubel, Oct 30 2022: (Start) (formulas for triangle T(n,k))
T(n, n-k) = T(n, k).
T(n, n) = A000012(n).
T(n, n-1) = A028310(n-1).
T(n, n-2) = A089071(n-1) = A022856(n+1).
T(2*n, n-1) = A047087(n).
T(2*n+1, n-1) = A047088(n).
Sum_{k=0..n} T(n, k) = (-1)^n*A078042(n) = A001590(n+3).
Sum_{k=0..n} (-1)^k*T(n, k) = A091337(n+1).
Sum_{k=0..floor(n/2)} T(n, k) = A047084(n). (End)

Sequence recomputed to correct terms from 23rd onward, and recurrence and generating function added by Michael L. Catalano-Johnson (mcj(AT)pa.wagner.com), Jan 14 2000

A047081 a(n) = Sum_{k=0..n} T(n, k), array T as in A047080.

Original entry on oeis.org

1, 2, 3, 6, 11, 20, 37, 68, 125, 230, 423, 778, 1431, 2632, 4841, 8904, 16377, 30122, 55403, 101902, 187427, 344732, 634061, 1166220, 2145013, 3945294, 7256527, 13346834, 24548655, 45152016, 83047505, 152748176, 280947697, 516743378, 950439251, 1748130326, 3215312955, 5913882532, 10877325813

Offset: 0

Clark Kimberling

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

Cf. A047080, A047082, A047083, A047084, A047085, A047086, A047087, A047088.

Cf. A000073, A254006.

[n le 3 select n else Self(n-1) +Self(n-2) +Self(n-3): n in [1..60]]; // G. C. Greubel, Oct 31 2022

LinearRecurrence[{1,1,1}, {1,2,3}, 61] (* G. C. Greubel, Oct 31 2022 *)

@CachedFunction
def a(n): return (n+1) if (n<3) else a(n-1) +a(n-2) +a(n-3) # a = A047081
[a(n) for n in (0..60)] # G. C. Greubel, Oct 31 2022

From G. C. Greubel, Oct 31 2022: (Start)
G.f.: (1 + x)/(1 - x - x^2 - x^3).
a(n) = A000073(n+1) + A000073(n+2). (End)
a(n) = Sum_{r root of x^3-x^2-x-1} r^n/(-3*r^2+5*r+2). - Fabian Pereyra, Nov 23 2024
a(n) = A001590(n+3). - R. J. Mathar, Mar 28 2025

Data corrected by G. C. Greubel, Oct 31 2022

A047085 a(n) = T(2*n, n), array T as in A047080.

Original entry on oeis.org

1, 1, 3, 9, 27, 83, 259, 817, 2599, 8323, 26797, 86659, 281287, 915907, 2990383, 9786369, 32092959, 105435607, 346950321, 1143342603, 3772698725, 12463525229, 41218894577, 136451431723, 452116980643, 1499282161375, 4975631425581, 16524213199923, 54913514061867

Offset: 0

Clark Kimberling

nonn

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A047080, A047081, A047082, A047083, A047084, A047086, A047087, A047088.

Cf. A171155.

R:=PowerSeriesRing(Rationals(), 50); Coefficients(R!( Sqrt((1-x)/(1 -3*x-x^2-x^3)) )); // G. C. Greubel, Oct 30 2022

CoefficientList[Series[Sqrt[(1-x)/(1-3*x-x^2-x^3)], {x, 0, 50}], x] (* G. C. Greubel, Oct 30 2022 *)

def A047085_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( sqrt((1-x)/(1-3*x-x^2-x^3)) ).list()
A047085_list(50) # G. C. Greubel, Oct 30 2022

From G. C. Greubel, Oct 30 2022: (Start)
a(n) = A171155(n).
G.f.: sqrt((1 - x)/(1 - 3*x - x^2 - x^3)). (End)

Data corrected by Sean A. Irvine, May 11 2021

A047082 a(n) = Sum_{i=0..floor(n/2)} A047080(n,i).

Original entry on oeis.org

1, 1, 2, 3, 7, 10, 23, 34, 76, 115, 253, 389, 845, 1316, 2829, 4452, 9488, 15061, 31863, 50951, 107112, 172366, 360360, 583110, 1213150, 1972647, 4086217, 6673417, 13769519, 22576008, 46416937, 76374088, 156520328, 258371689, 527937429, 874065163, 1781131638

Offset: 0

Clark Kimberling

nonn

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A047080, A047081, A047083, A047084, A047085, A047086, A047087, A047088.

F:=Factorial;
p:= func< n,k | (&+[ (-1)^j*F(n+k-3*j)/(F(j)*F(n-2*j)*F(k-2*j)): j in [0..Min(Floor(n/2), Floor(k/2))]]) >;
q:= func< n,k | n eq 0 or k eq 0 select 0 else (&+[ (-1)^j*F(n+k-3*j-2)/(F(j)*F(n-2*j-1)*F(k-2*j-1)) : j in [0..Min(Floor((n-1)/2), Floor((k-1)/2))]]) >;
A:= func< n,k | p(n,k) - q(n,k) >;
[(&+[A(n-j,j): j in [0..Floor(n/2)]]): n in [0..50]]; // G. C. Greubel, Oct 31 2022

A[n_, k_]:= Sum[(-1)^j*(n+k-3*j)!/(j!*(n-2*j)!*(k-2*j)!), {j,0,Floor[(n+k)/3]}] - Sum[(-1)^j*(n+k-3*j-2)!/(j!*(n-2*j-1)!*(k-2*j-1)!), {j,0,Floor[(n+k-2)/3]}];
A047082[n_]:= A047082[n]= Sum[A[n-k,k], {k,0,Floor[n/2]}];
Table[A047082[n], {n, 0, 50}] (* G. C. Greubel, Oct 31 2022 *)

f=factorial
def p(n,k): return sum( (-1)^j*f(n+k-3*j)/(f(j)*f(n-2*j)*f(k-2*j)) for j in range(1+min((n//2), (k//2))) )
def q(n,k): return sum( (-1)^j*f(n+k-3*j-2)/(f(j)*f(n-2*j-1)*f(k-2*j-1)) for j in range(1+min(((n-1)//2), ((k-1)//2))) )
def A(n,k): return p(n,k) - q(n,k)
[sum(A(n-j,j) for j in range(1+(n//2))) for n in range(51)] # G. C. Greubel, Oct 31 2022

Data corrected by Sean A. Irvine, May 11 2021

A047083 a(n) = Sum_{i=0..floor((n+1)/2)} A047080(n,i).

Original entry on oeis.org

1, 2, 2, 5, 7, 15, 23, 49, 76, 161, 253, 532, 845, 1766, 2829, 5881, 9488, 19631, 31863, 65649, 107112, 219857, 360360, 737152, 1213150, 2473930, 4086217, 8309252, 13769519, 27927146, 46416937, 93915759, 156520328, 315982677, 527937429, 1063586803, 1781131638

Offset: 0

Clark Kimberling

nonn

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A047080, A047081, A047082, A047084, A047085, A047086, A047087, A047088.

F:=Factorial;
p:= func< n,k | (&+[ (-1)^j*F(n+k-3*j)/(F(j)*F(n-2*j)*F(k-2*j)): j in [0..Min(Floor(n/2), Floor(k/2))]]) >;
q:= func< n,k | n eq 0 or k eq 0 select 0 else (&+[ (-1)^j*F(n+k-3*j-2)/(F(j)*F(n-2*j-1)*F(k-2*j-1)) : j in [0..Min(Floor((n-1)/2), Floor((k-1)/2))]]) >;
A:= func< n,k | p(n,k) - q(n,k) >;
[(&+[A(n-j,j): j in [0..Floor((n+1)/2)]]): n in [0..50]]; // G. C. Greubel, Oct 31 2022

A[n_, k_]:= Sum[(-1)^j*(n+k-3*j)!/(j!*(n-2*j)!*(k-2*j)!), {j,0,Floor[(n+k)/3]}] -
 Sum[(-1)^j*(n+k-3*j-2)!/(j!*(n-2*j-1)!*(k-2*j-1)!), {j,0,Floor[(n+k-2)/3]}];
A047083[n_]:= A047083[n]= Sum[A[n-k,k], {k,0,Floor[(n+1)/2]}];
Table[A047083[n], {n,0,50}] (* G. C. Greubel, Oct 31 2022 *)

f=factorial
def p(n,k): return sum( (-1)^j*f(n+k-3*j)/(f(j)*f(n-2*j)*f(k-2*j)) for j in range(1+min((n//2), (k//2))) )
def q(n,k): return sum( (-1)^j*f(n+k-3*j-2)/(f(j)*f(n-2*j-1)*f(k-2*j-1)) for j in range(1+min(((n-1)//2), ((k-1)//2))) )
def A(n,k): return p(n,k) - q(n,k)
[sum(A(n-j,j) for j in range(1+((n+1)//2))) for n in range(51)] # G. C. Greubel, Oct 31 2022

Data corrected by Sean A. Irvine, May 11 2021

A047086 a(n) = T(2*n+1, n), array T as in A047080.

Original entry on oeis.org

1, 2, 5, 15, 46, 143, 450, 1429, 4570, 14698, 47491, 154042, 501283, 1635835, 5351138, 17541671, 57610988, 189521640, 624389105, 2059824523, 6803433916, 22495796651, 74457478476, 246667937610, 817866796549, 2713874203112, 9011747680649, 29944572743724

Offset: 0

Clark Kimberling

nonn

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A047080, A047081, A047082, A047083, A047084, A047085, A047087, A047088.

F:=Factorial;
p:= func< n,k | (&+[ (-1)^j*F(n+k-3*j)/(F(j)*F(n-2*j)*F(k-2*j)): j in [0..Min(Floor(n/2), Floor(k/2))]]) >;
q:= func< n,k | n eq 0 or k eq 0 select 0 else (&+[ (-1)^j*F(n+k-3*j-2)/(F(j)*F(n-2*j-1)*F(k-2*j-1)) : j in [0..Min(Floor((n-1)/2), Floor((k-1)/2))]]) >;
A:= func< n,k | p(n,k) - q(n,k) >;
[A(n+1,n): n in [0..50]]; // G. C. Greubel, Oct 30 2022

A[n_, k_]:= Sum[(-1)^j*(n+k-3*j)!/(j!*(n-2*j)!*(k-2*j)!), {j, 0, Floor[(n+k)/3]}] - Sum[(-1)^j*(n+k-3*j-2)!/(j!*(n-2*j-1)!*(k-2*j-1)!), {j, 0, Floor[(n+k-2)/3]}];
T[n_, k_]:= A[n-k,k];
Table[T[2*n+1,n], {n,0,50}] (* G. C. Greubel, Oct 30 2022 *)

f=factorial
def p(n,k): return sum( (-1)^j*f(n+k-3*j)/(f(j)*f(n-2*j)*f(k-2*j)) for j in range(1+min((n//2), (k//2))) )
def q(n,k): return sum( (-1)^j*f(n+k-3*j-2)/(f(j)*f(n-2*j-1)*f(k-2*j-1)) for j in range(1+min(((n-1)//2), ((k-1)//2))) )
def A(n,k): return p(n,k) - q(n,k)
[A(n+1,n) for n in range(51)] # G. C. Greubel, Oct 30 2022

a(n+4) = ((16*n^3 + 100*n^2 + 188*n + 105)*a(n+3) - (8*n^3 + 36*n^2 + 46*n + 5)*a(n+2) + (4*n^2 + 16*n + 25)*a(n+1) - (n-1)*(2*n+5)^2*a(n))/((n+4)*(2*n+3)^2). - G. C. Greubel, Oct 30 2022

Corrected and extended by Sean A. Irvine, May 11 2021

A047087 a(n) = A047080(2*n, n+1).

Original entry on oeis.org

1, 3, 8, 24, 75, 237, 755, 2421, 7804, 25264, 82081, 267487, 873970, 2862038, 9391137, 30869167, 101627704, 335049772, 1106003560, 3655124296, 12092095945, 40042017815, 132712302538, 440207294382, 1461259979347, 4853983051617, 16134233746913, 53660996850207

Offset: 1

Clark Kimberling

nonn

G. C. Greubel, Table of n, a(n) for n = 1..1000

Cf. A047080, A047081, A047082, A047083, A047084, A047085, A047086, A047088.

F:=Factorial;
p:= func< n,k | (&+[ (-1)^j*F(n+k-3*j)/(F(j)*F(n-2*j)*F(k-2*j)): j in [0..Min(Floor(n/2), Floor(k/2))]]) >;
q:= func< n,k | n eq 0 or k eq 0 select 0 else (&+[ (-1)^j*F(n+k-3*j-2)/(F(j)*F(n-2*j-1)*F(k-2*j-1)) : j in [0..Min(Floor((n-1)/2), Floor((k-1)/2))]]) >;
A:= func< n,k | p(n,k) - q(n,k) >;
[A(n-1,n+1): n in [1..50]]; // G. C. Greubel, Oct 30 2022

A[n_, k_]:= Sum[(-1)^j*(n+k-3*j)!/(j!*(n-2*j)!*(k-2*j)!), {j,0,Floor[(n+k)/3]}] - Sum[(-1)^j*(n+k-3*j-2)!/(j!*(n-2*j-1)!*(k-2*j-1)!), {j, 0, Floor[(n+k- 2)/3]}];
Table[A[n-1, n+1], {n, 50}] (* G. C. Greubel, Oct 30 2022 *)

f=factorial
def p(n,k): return sum( (-1)^j*f(n+k-3*j)/(f(j)*f(n-2*j)*f(k-2*j)) for j in range(1+min((n//2), (k//2))) )
def q(n,k): return sum( (-1)^j*f(n+k-3*j-2)/(f(j)*f(n-2*j-1)*f(k-2*j-1)) for j in range(1+min(((n-1)//2), ((k-1)//2))) )
def A(n,k): return p(n,k) - q(n,k)
[A(n-1,n+1) for n in range(1,50)] # G. C. Greubel, Oct 30 2022

a(n+4) = ((4*n^5 + 61*n^4 + 374*n^3 + 1146*n^2 + 1743*n + 1046)*a(n+3) - (2*n^5 + 27*n^4 + 146*n^3 + 380*n^2 + 467*n + 220)*a(n+2) + (n+4)*(n^3 + 10*n^2 + 44*n + 53)*a(n+1) - (n-2)*(n+3)*(n+4)*(n^2 + 8*n + 18)*a(n))/((n+2)*(n+3)*(n+5)*(n^2 + 6*n + 11)). - G. C. Greubel, Oct 30 2022

Corrected and extended by Sean A. Irvine, May 11 2021

A047088 a(n) = A047080(2*n+1, n+2).

Original entry on oeis.org

1, 4, 12, 37, 118, 380, 1229, 3989, 12987, 42394, 138709, 454768, 1493690, 4913969, 16189534, 53407853, 176397299, 583242159, 1930349545, 6394665589, 21201345460, 70346920007, 233581374587, 776105485336, 2580316142887, 8583746045611, 28570407158100

Offset: 1

Clark Kimberling

nonn

G. C. Greubel, Table of n, a(n) for n = 1..1000

Cf. A047080, A047081, A047082, A047083, A047084, A047085, A047086, A047087.

F:=Factorial;
p:= func< n,k | (&+[ (-1)^j*F(n+k-3*j)/(F(j)*F(n-2*j)*F(k-2*j)): j in [0..Min(Floor(n/2), Floor(k/2))]]) >;
q:= func< n,k | n eq 0 or k eq 0 select 0 else (&+[ (-1)^j*F(n+k-3*j-2)/(F(j)*F(n-2*j-1)*F(k-2*j-1)) : j in [0..Min(Floor((n-1)/2), Floor((k-1)/2))]]) >;
A:= func< n,k | p(n,k) - q(n,k) >;
[A(n-1,n+2): n in [1..50]]; // G. C. Greubel, Oct 31 2022

A[n_, k_]:= Sum[(-1)^j*(n+k-3*j)!/(j!*(n-2*j)!*(k-2*j)!), {j,0,Floor[(n+k)/3]}] - Sum[(-1)^j*(n+k-3*j-2)!/(j!*(n-2*j-1)!*(k-2*j-1)!), {j,0,Floor[(n+k-2)/3]}];
Table[A[n-1, n+2], {n, 50}] (* G. C. Greubel, Oct 31 2022 *)

f=factorial
def p(n,k): return sum( (-1)^j*f(n+k-3*j)/(f(j)*f(n-2*j)*f(k-2*j)) for j in range(1+min((n//2), (k//2))) )
def q(n,k): return sum( (-1)^j*f(n+k-3*j-2)/(f(j)*f(n-2*j-1)*f(k-2*j-1)) for j in range(1+min(((n-1)//2), ((k-1)//2))) )
def A(n,k): return p(n,k) - q(n,k)
[A(n-1,n+2) for n in range(1,50)] # G. C. Greubel, Oct 31 2022

a(n+4) = ((16*n^5 + 324*n^4 + 2624*n^3 + 10509*n^2 + 20655*n + 15930)*a(n+3) - (8*n^5 + 148*n^4 + 1090*n^3 + 3953*n^2 + 7365*n + 5994)*a(n+2) + (4*n^4 + 84*n^3 + 701*n^2 + 2451*n + 2646)*a(n+1) - (n-3)*(n+6)*(2*n+7)*(2*n^2 + 23*n + 72)*a(n) )/((n+3)*(n+6)*(2*n+5)*(2*n^2 + 19*n + 51)). - G. C. Greubel, Oct 31 2022

Corrected and extended by Sean A. Irvine, May 11 2021

cp's OEIS Frontend

A047080 Triangular array T read by rows: T(h,k)=number of paths from (0,0) to (k,h-k) using step-vectors (0,1), (1,0), (1,1) with no right angles between pairs of consecutive steps.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

Extensions

A047081 a(n) = Sum_{k=0..n} T(n, k), array T as in A047080.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

Extensions

A047085 a(n) = T(2*n, n), array T as in A047080.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

Extensions

A047082 a(n) = Sum_{i=0..floor(n/2)} A047080(n,i).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Extensions

A047083 a(n) = Sum_{i=0..floor((n+1)/2)} A047080(n,i).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Extensions

A047086 a(n) = T(2*n+1, n), array T as in A047080.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

Extensions

A047087 a(n) = A047080(2*n, n+1).

Views

Author

Keywords

Links

Crossrefs