login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A213658 Irregular triangle read by rows: T(n,k) is the number of dominating subsets with k vertices of the graph G(n) consisting of an edge ab and n triangles, each having one vertex identified with the vertex b. 1

%I #23 Sep 08 2022 08:46:02

%S 1,5,4,1,1,5,14,14,6,1,1,7,21,43,47,27,8,1,1,9,36,84,142,158,108,44,

%T 10,1,1,11,55,165,330,494,542,410,205,65,12,1,1,13,78,286,715,1287,

%U 1780,1908,1527,875,346,90,14,1,1,15,105,455,1365,3003,5005

%N Irregular triangle read by rows: T(n,k) is the number of dominating subsets with k vertices of the graph G(n) consisting of an edge ab and n triangles, each having one vertex identified with the vertex b.

%C Row n contains 2n + 2 entries.

%C Sum of entries in row n = 3^n + 2^{2n+1} = A213659(n).

%H S. Alikhani and E. Deutsch, <a href="http://arxiv.org/abs/1305.3734">Graphs with domination roots in the right half-plane</a>, arXiv preprint arXiv:1305.3734 [math.CO], 2013-2014.

%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^(n+1)*(2+x)^n + x*(1+x)^(2*n+1); this is the domination polynomial of the graph G(n).

%F T(n,k) = 2^(2*n+1-k)*binomial(n,k-n-1) + binomial(2*n+1,k-1) (n >= 1; 1 <= k <= 2*n+2).

%e Row 1 is 1,5,4,1 because the graph G(1) is abcd with edges ab, bc, bd, and cd; there is 1 dominating subset of size 1 ({b}); all binomial(4,2)=6 subsets of size 2 of {a,b,c,d} with the exception of {c,d} are dominating; all binomial(4,3)=4 subsets of size 3 of {a,b,c,d} are dominating; obviously, {a,b,c,d} is dominating.

%e Triangle starts:

%e 1, 5, 4, 1;

%e 1, 5, 14, 14, 6, 1;

%e 1, 7, 21, 43, 47, 27, 8, 1;

%p T := proc (n, k) options operator, arrow: 2^(2*n+1-k)*binomial(n, k-n-1)+binomial(2*n+1, k-1) end proc: for n to 8 do seq(T(n, k), k = 1 .. 2*n+2) end do; # yields sequence in triangular form

%t row[n_] := CoefficientList[x^(n + 1)*(2 + x)^n + x*(1 + x)^(2*n + 1), x] // Rest;

%t Table[row[n], {n, 1, 7}] // Flatten (* _Jean-François Alcover_, Dec 02 2017 *)

%o (Magma) /* As triangle */ [[2^(2*n+1-k)*Binomial(n,k-n-1) + Binomial(2*n+1,k-1): k in [1..2*n+2]]: n in [1.. 15]]; // _Vincenzo Librandi_, Jul 21 2019

%Y Cf. A213659.

%K nonn,tabf

%O 1,2

%A _Emeric Deutsch_, Jun 29 2012

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 09:04 EDT 2024. Contains 371240 sequences. (Running on oeis4.)