login
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.
0

%I #7 Oct 21 2024 20:24:00

%S 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,

%T 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,

%U 140,105,44,10,1,0,0,0,0,14,96,216,238,148,54,11,1

%N 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.

%C 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.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DominationPolynomial.html">Domination Polynomial</a>.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PathGraph.html">Path Graph</a>.

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

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

%e Triangle begins:

%e 1;

%e 1, 1;

%e 0, 2, 1;

%e 0, 2, 3, 1;

%e 0, 1, 5, 4, 1;

%e 0, 0, 5, 9, 5, 1;

%e 0, 0, 3, 13, 14, 6, 1;

%e 0, 0, 1, 13, 26, 20, 7, 1;

%e 0, 0, 0, 9, 35, 45, 27, 8, 1;

%e 0, 0, 0, 4, 35, 75, 71, 35, 9, 1;

%e 0, 0, 0, 1, 26, 96, 140, 105, 44, 10, 1;

%e ...

%e 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):

%e x . . x x

%e x . x . x

%e x . x x .

%e x x . . x

%e x x . x .

%o (PARI) T(n)={[Vecrev(p) | p<-Vec((1 + x)/(1 - y*x - y*x^2 - y*x^3) + O(x*x^n))]}

%o { my(A=T(10)); for(i=1, #A, print(A[i])) }

%Y Row sums are A047081.

%Y Column sums are A008776.

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

%Y Cf. A169623, A212633.

%K nonn,tabl

%O 0,5

%A _Andrew Howroyd_, Oct 21 2024