|
%I #17 Sep 08 2022 08:46:02
%S 3,3,1,1,8,10,5,1,1,6,23,32,21,7,1,1,8,28,72,102,80,36,9,1,1,10,45,
%T 120,242,332,290,160,55,11,1,1,12,66,220,495,856,1116,1032,655,280,78,
%U 13,1,1,14,91,364,1001,2002,3131,3880,3675,2562,1281,448,105,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 cycle graph C_3 with a vertex in common.
%C Row n contain 2n + 1 entries.
%C Sum of entries in row n = 3^n + 4^n = A074605(n).
%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 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.
%F Generating polynomial of row n is x*(1+x)^(2*n) + (2*x+x^2)^n; this is the domination polynomial of the graph G(n).
%F T(n,k) = 2^(2*n-k)*binomial(n,k-n) + binomial(2*n,k-1) (n >= 1; 1 <= k <= 2*n+1).
%e Row 1 is 3,3,1 because the graph G(1) is the triangle abc; there are 3 dominating subsets of size 1 ({a}, {b}, {c}), 3 dominating subsets of size 2 ({a,b}, {a,c}, {b,c}), and 1 dominating subset of size 3 ({a,b,c}).
%e T(n,1)=1 for n >= 2 because the common vertex of the triangles is the only dominating subset of size k=1.
%e Triangle starts:
%e 3, 3, 1;
%e 1, 8, 10, 5, 1;
%e 1, 6, 23, 32, 21, 7, 1;
%e 1, 8, 28, 72, 102, 80, 36, 9, 1;
%p T := proc (n, k) options operator, arrow: 2^(2*n-k)*binomial(n, k-n)+binomial(2*n, k-1) end proc: for n to 9 do seq(T(n, k), k = 1 .. 2*n+1) end do; # yields sequence in triangular form
%t T[n_, k_] := 2^(2n-k) Binomial[n, k-n] + Binomial[2n, k-1];
%t Table[T[n, k], {n, 1, 9}, {k, 1, 2n+1}] // Flatten (* _Jean-François Alcover_, Dec 06 2017 *)
%o (Magma) /* As triangle */ [[2^(2*n-k)*Binomial(n,k-n)+Binomial(2*n,k-1): k in [1..2*n+1]]: n in [1.. 10]]; // _Vincenzo Librandi_, Jul 20 2019
%Y Cf. A074605.
%K nonn,tabf
%O 1,1
%A _Emeric Deutsch_, Jun 29 2012
|
