cp's OEIS Frontend

A213666 Irregular triangle read by rows: T(n,k) is the number of dominating subsets with k vertices of the graph G(n) obtained by taking n copies of the path P_3 and identifying one of their endpoints (a star with n branches of length 2).

%I A213666 #31 Feb 16 2025 08:33:17
%S A213666 1,3,1,0,3,8,5,1,0,0,7,20,18,7,1,0,0,0,15,48,56,32,9,1,0,0,0,0,31,112,
%T A213666 160,120,50,11,1,0,0,0,0,0,63,256,432,400,220,72,13,1,0,0,0,0,0,0,127,
%U A213666 576,1120,1232,840,364,98,15,1
%N A213666 Irregular triangle read by rows: T(n,k) is the number of dominating subsets with k vertices of the graph G(n) obtained by taking n copies of the path P_3 and identifying one of their endpoints (a star with n branches of length 2).
%C A213666 Rows also give the coefficients of the domination polynomial of the n-helm graph (divided by x, i.e., with initial 0 dropped from rows). - _Eric W. Weisstein_, May 28 2017
%C A213666 Row n contains 2n + 1 entries (first n-1 of which are 0).
%C A213666 Sum of entries in row n = 2*3^{n-1} - 1 = A048473(n).
%C A213666 Sum of entries in column k = A213667(k).
%H A213666 S. Alikhani and Y. H. Peng, <a href="http://arxiv.org/abs/0905.2251">Introduction to domination polynomial of a graph</a>, arXiv:0905.2251 [math.CO], 2009.
%H A213666 É. Czabarka, L. Székely, and S. Wagner, <a href="http://dx.doi.org/10.1016/j.dam.2009.07.004">The inverse problem for certain tree parameters</a>, Discrete Appl. Math., 157, 2009, 3314-3319.
%H A213666 T. Kotek, J. Preen, F. Simon, P. Tittmann, and M. Trinks, <a href="http://arxiv.org/abs/1206.5926">Recurrence relations and splitting formulas for the domination polynomial</a>, arXiv:1206.5926 [math.CO], 2012.
%H A213666 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DominationPolynomial.html">Domination Polynomial</a>.
%H A213666 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HelmGraph.html">Helm Graph</a>.
%F A213666 T(n,k) = 2^(2*n-k)*(2*binomial(n,k-n-1)+binomial(n,k-n)) if k > n; T(n,n)=2^n - 1.
%F A213666 The generating polynomial of row n is g[n] = g[n,x] = (1+x)(x*(2+x))^n - x^n (= domination polynomial of the graph G(n)).
%F A213666 Bivariate g.f.: G(x,z) = x*z*(1+x)*(2+x)/(1-2*x*z-x^2*z)-x*z/(1-xz).
%e A213666 Row 2 is 0,3,8,5,1 because G(2) is the path P_5 abcde; no domination subset of size 1, three of size 2 (ad, bd, be), all subsets of size 3 with the exception of abc and cde are dominating (binomial(5,3)-2=8), all binomial(5,4)=5 subsets of size 4 are dominating, and abcde is dominating.
%e A213666 Triangle starts:
%e A213666   1, 3, 1;
%e A213666   0, 3, 8,  5,  1;
%e A213666   0, 0, 7, 20, 18,  7,  1;
%e A213666   0, 0, 0, 15, 48, 56, 32, 9, 1;
%p A213666 T := proc (n, k) if k = n then 2^n-1 else 2^(2*n-k)*(2*binomial(n, k-n-1) + binomial(n, k-n)) end if end proc: for n to 10 do seq(T(n, k), k = 1 .. 2*n+1) end d; # yields sequence in triangular form
%t A213666 T[n_, n_] := 2^n - 1;
%t A213666 T[n_, k_] := 2^(2*n - k)*(2*Binomial[n, k - n - 1] + Binomial[n, k - n]);
%t A213666 Table[T[n, k], {n, 1, 10}, {k, 1, 2*n + 1}] // Flatten (* _Jean-François Alcover_, Dec 02 2017 *)
%Y A213666 Cf. A048473, A213667.
%K A213666 nonn,tabf
%O A213666 1,2
%A A213666 _Emeric Deutsch_, Jul 01 2012