A213660 - OEIS

%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