login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A213660 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. 0
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, 120, 242, 332, 290, 160, 55, 11, 1, 1, 12, 66, 220, 495, 856, 1116, 1032, 655, 280, 78, 13, 1, 1, 14, 91, 364, 1001, 2002, 3131, 3880, 3675, 2562, 1281, 448, 105, 15, 1 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

Row n contain 2n + 1 entries.

Sum of entries in row n = 3^n + 4^n = A074605(n).

LINKS

Table of n, a(n) for n=1..63.

S. Alikhani and Y. H. Peng, Introduction to domination polynomial of a graph, arXiv:0905.2251 [math.CO], 2009.

T. Kotek, J. Preen, F. Simon, P. Tittmann, and M. Trinks, Recurrence relations and splitting formulas for the domination polynomial, arXiv:1206.5926 [math.CO], 2012.

FORMULA

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

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

EXAMPLE

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}).

T(n,1)=1 for n >= 2 because the common vertex of the triangles is the only dominating subset of size k=1.

Triangle starts:

  3, 3,  1;

  1, 8, 10,  5,   1;

  1, 6, 23, 32,  21,  7,  1;

  1, 8, 28, 72, 102, 80, 36, 9, 1;

MAPLE

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

MATHEMATICA

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

Table[T[n, k], {n, 1, 9}, {k, 1, 2n+1}] // Flatten (* Jean-Fran├žois Alcover, Dec 06 2017 *)

PROG

(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

CROSSREFS

Cf. A074605.

Sequence in context: A165795 A287290 A287981 * A099037 A340934 A271706

Adjacent sequences:  A213657 A213658 A213659 * A213661 A213662 A213663

KEYWORD

nonn,tabf

AUTHOR

Emeric Deutsch, Jun 29 2012

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 28 07:52 EST 2021. Contains 349401 sequences. (Running on oeis4.)