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.

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

Author

Andrew Howroyd, Oct 21 2024

Keywords

• nonn
• tabl

Comments

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.

Examples

			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 .
		

Links

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

Crossrefs

Row sums are A047081.

Column sums are A008776.

Diagonals include A000012, A000027, A000096, A008778, A095661.

Cf. A169623, A212633.

Programs

PARI

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])) }

Formula

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).