cp's OEIS Frontend

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.

%I A377069 #7 Oct 21 2024 20:24:00
%S A377069 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 A377069 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 A377069 140,105,44,10,1,0,0,0,0,14,96,216,238,148,54,11,1
%N 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.
%C A377069 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 A377069 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DominationPolynomial.html">Domination Polynomial</a>.
%H A377069 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PathGraph.html">Path Graph</a>.
%F A377069 G.f.: (1 + x)/(1 - y*x - y*x^2 - y*x^3).
%F A377069 A212633(n,k) = T(n-1, k-1) + T(n-2, k-1).
%e A377069 Triangle begins:
%e A377069   1;
%e A377069   1, 1;
%e A377069   0, 2, 1;
%e A377069   0, 2, 3,  1;
%e A377069   0, 1, 5,  4,  1;
%e A377069   0, 0, 5,  9,  5,  1;
%e A377069   0, 0, 3, 13, 14,  6,   1;
%e A377069   0, 0, 1, 13, 26, 20,   7,   1;
%e A377069   0, 0, 0,  9, 35, 45,  27,   8,  1;
%e A377069   0, 0, 0,  4, 35, 75,  71,  35,  9,  1;
%e A377069   0, 0, 0,  1, 26, 96, 140, 105, 44, 10, 1;
%e A377069   ...
%e A377069 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 A377069    x . . x x
%e A377069    x . x . x
%e A377069    x . x x .
%e A377069    x x . . x
%e A377069    x x . x .
%o A377069 (PARI) T(n)={[Vecrev(p) | p<-Vec((1 + x)/(1 - y*x - y*x^2 - y*x^3) + O(x*x^n))]}
%o A377069 { my(A=T(10)); for(i=1, #A, print(A[i])) }
%Y A377069 Row sums are A047081.
%Y A377069 Column sums are A008776.
%Y A377069 Diagonals include A000012, A000027, A000096, A008778, A095661.
%Y A377069 Cf. A169623, A212633.
%K A377069 nonn,tabl
%O A377069 0,5
%A A377069 _Andrew Howroyd_, Oct 21 2024