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,5

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.

Links

Table of n, a(n) for n=0..77.

Eric Weisstein's World of Mathematics, Domination Polynomial.

Eric Weisstein's World of Mathematics, Path Graph.

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

Example

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 .

Prog

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

Crossrefs

Row sums are A047081.

Column sums are A008776.

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

Cf. A169623, A212633.

Sequence in context: A051070 A104041 A104402 * A261897 A131084 A143067

Adjacent sequences: A377066 A377067 A377068 * A377070 A377071 A377072

Keyword

nonn,tabl

Author

Andrew Howroyd, Oct 21 2024

Status

approved