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

%I #31 Feb 16 2025 08:33:17

%S 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 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 576,1120,1232,840,364,98,15,1

%N 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 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 Row n contains 2n + 1 entries (first n-1 of which are 0).

%C Sum of entries in row n = 2*3^{n-1} - 1 = A048473(n).

%C Sum of entries in column k = A213667(k).

%H 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 É. 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 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 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/HelmGraph.html">Helm Graph</a>.

%F 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 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 Bivariate g.f.: G(x,z) = x*z*(1+x)*(2+x)/(1-2*x*z-x^2*z)-x*z/(1-xz).

%e 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 Triangle starts:

%e 1, 3, 1;

%e 0, 3, 8, 5, 1;

%e 0, 0, 7, 20, 18, 7, 1;

%e 0, 0, 0, 15, 48, 56, 32, 9, 1;

%p 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 T[n_, n_] := 2^n - 1;

%t T[n_, k_] := 2^(2*n - k)*(2*Binomial[n, k - n - 1] + Binomial[n, k - n]);

%t Table[T[n, k], {n, 1, 10}, {k, 1, 2*n + 1}] // Flatten (* _Jean-François Alcover_, Dec 02 2017 *)

%Y Cf. A048473, A213667.

%K nonn,tabf,changed

%O 1,2

%A _Emeric Deutsch_, Jul 01 2012