A047081 -id:A047081 - 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

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

A047084 a(n) = Sum_{i=0..n} A047080(i,n-i).

Original entry on oeis.org

1, 1, 2, 2, 4, 6, 9, 14, 21, 33, 50, 77, 118, 181, 278, 426, 654, 1003, 1539, 2361, 3622, 5557, 8525, 13079, 20065, 30783, 47226, 72452, 111153, 170526, 261614, 401357, 615745, 944650, 1449242, 2223366, 3410994, 5233003, 8028252, 12316605, 18895615, 28988854

Offset: 0

Clark Kimberling

Sean A. Irvine, Table of n, a(n) for n = 0..1000

Cf. A047080, A047081, A047082, A047083, 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-2*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]}];
A047084[n_]:= A047084[n]= Sum[A[2*k-n, n-k], {k,0,n}];
Table[A047084[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-2*j,j) for j in range(1+(n//2))) for n in range(51)] # G. C. Greubel, Oct 31 2022

a(n) = Sum_{j=0..floor(n/2)} A(n-2*j, j), where A(n,k) = array of A048080(n,k). - G. C. Greubel, Oct 31 2022

Entry revised 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

A377069 Triangle read by rows: T(n,k) is the number of (k+1)-vertex dominating sets of the (n+1)-path graph that include the first vertex.

Original entry on oeis.org

1, 1, 1, 0, 2, 1, 0, 2, 3, 1, 0, 1, 5, 4, 1, 0, 0, 5, 9, 5, 1, 0, 0, 3, 13, 14, 6, 1, 0, 0, 1, 13, 26, 20, 7, 1, 0, 0, 0, 9, 35, 45, 27, 8, 1, 0, 0, 0, 4, 35, 75, 71, 35, 9, 1, 0, 0, 0, 1, 26, 96, 140, 105, 44, 10, 1, 0, 0, 0, 0, 14, 96, 216, 238, 148, 54, 11, 1

Offset: 0

Andrew Howroyd, Oct 21 2024

T(n,k) is also the number of (k+1)-vertex dominating sets of the (n+2)-path graph that do not include the first vertex.

			Triangle begins:
  1;
  1, 1;
  0, 2, 1;
  0, 2, 3,  1;
  0, 1, 5,  4,  1;
  0, 0, 5,  9,  5,  1;
  0, 0, 3, 13, 14,  6,   1;
  0, 0, 1, 13, 26, 20,   7,   1;
  0, 0, 0,  9, 35, 45,  27,   8,  1;
  0, 0, 0,  4, 35, 75,  71,  35,  9,  1;
  0, 0, 0,  1, 26, 96, 140, 105, 44, 10, 1;
  ...
Corresponding to T(4,2) = 5, a path graph with 5 vertices has the following 3-vertex dominating sets that include the first vertex (x marks a vertex in the set):
   x . . x x
   x . x . x
   x . x x .
   x x . . x
   x x . x .

Eric Weisstein's World of Mathematics, Domination Polynomial.
Eric Weisstein's World of Mathematics, Path Graph.

Row sums are A047081.
Column sums are A008776.
Diagonals include A000012, A000027, A000096, A008778, A095661.
Cf. A169623, A212633.

T(n)={[Vecrev(p) | p<-Vec((1 + x)/(1 - y*x - y*x^2 - y*x^3) + O(x*x^n))]}
{ my(A=T(10)); for(i=1, #A, print(A[i])) }

G.f.: (1 + x)/(1 - y*x - y*x^2 - y*x^3).

A212633(n,k) = T(n-1, k-1) + T(n-2, k-1).

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

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

A047084 a(n) = Sum_{i=0..n} A047080(i,n-i).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

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