A212634 -id:A212634 - cp's OEIS frontend

A212635 Irregular triangle read by rows: T(n,k) is the number of dominating subsets with cardinality k of the wheel W_n (n >= 4, 1 <= k <= n).

4, 6, 4, 1, 1, 10, 10, 5, 1, 1, 10, 20, 15, 6, 1, 1, 9, 29, 35, 21, 7, 1, 1, 7, 35, 63, 56, 28, 8, 1, 1, 8, 36, 94, 118, 84, 36, 9, 1, 1, 9, 39, 120, 207, 201, 120, 45, 10, 1, 1, 10, 45, 145, 312, 402, 320, 165, 55, 11, 1, 1, 11, 55, 176, 429, 693, 715, 484, 220, 66, 12, 1

Offset: 4

Emeric Deutsch, Jun 17 2012

The entries in row n are the coefficients of the domination polynomial of the wheel W_n (see the Alikhani and Peng arxiv reference).

			Row 4 is [4,6,4,1] because all nonempty subsets of the wheel W_4 are dominating: binomial(4,j) of size j (j=1,2,3,4).
T(7,2)=9 because in the wheel W_7 with vertices A (center), B, C, D, E, F, G the dominating subsets of size 2 are {B,E}, {C,F}, {D,G}, {A, B}, {A,C}, {A,D}, {A,E}, {A,F}, and {A, G}.
Irregular triangle starts:
  4,  6,  4,  1;
  1, 10, 10,  5,  1;
  1, 10, 20, 15,  6,  1;
  1,  9, 29, 35, 21,  7,  1;

S. Alikhani and Y. H. Peng, Introduction to domination polynomial of a graph, arXiv:0905.2251 [math.CO], 2009.
J. L. Arocha, B. Llano, The number of dominating k-sets of paths, cycles and wheels, arXiv preprint arXiv:1601.01268 [math.CO], 2016.
Eric Weisstein's World of Mathematics, Domination Polynomial
Eric Weisstein's World of Mathematics, Wheel Graph

Cf. A212634.

pc := proc (n) if n = 1 then x elif n = 2 then x^2+2*x elif n = 3 then x^3+3*x^2+3*x else sort(expand(x*(pc(n-1)+pc(n-2)+pc(n-3)))) end if end proc: p := proc (n) options operator, arrow: sort(expand(x*(1+x)^(n-1)+pc(n-1))) end proc: for n from 4 to 15 do seq(coeff(p(n), x, k), k = 1 .. n) end do; # yields sequence in triangular form

pc[n_] := pc[n] = Which[n == 1, x, n == 2, x^2 + 2*x, n == 3, x^3 + 3*x^2 + 3*x, True, Sort[Expand[x*(pc[n - 1] + pc[n - 2] + pc[n - 3])]]];
p[n_] := Sort[Expand[x*(1 + x)^(n - 1) + pc[n - 1]]];
Table[Coefficient[p[n], x, k], {n, 4, 15}, {k, 1, n}] // Flatten (* Jean-François Alcover, Nov 24 2017, after Emeric Deutsch *)

Denoting by pw(n,x) the domination polynomial of the wheel W_n, we have the recurrence relation pw(n,x) = x(pw(n-1,x) + pw(n-2,x) + pw(n-3,x)) + x(1+x)^{n-4}; pw(4,x) = 4x + 6x^2 + 4x^3 + x^4, pw(5,x) = x + 10x^2 + 10x^3 + 5x^4 + x^5, pw(6,x) = x + 10x^2 + 20x^3 + 15x^4 + 6x^5 + x^6.

If pc(n,x) is the domination polynomial of the cycle C_n (see A212634), then the domination polynomial of the wheel W_n is x*(1 + x)^(n-1) + pc(n,x) (see Corollary 2 in the Alikhani & Peng reference).

A212633 Triangle read by rows: T(n,k) is the number of dominating subsets with cardinality k of the path tree P_n (n>=1, 1<=k<=n).

Original entry on oeis.org

1, 2, 1, 1, 3, 1, 0, 4, 4, 1, 0, 3, 8, 5, 1, 0, 1, 10, 13, 6, 1, 0, 0, 8, 22, 19, 7, 1, 0, 0, 4, 26, 40, 26, 8, 1, 0, 0, 1, 22, 61, 65, 34, 9, 1, 0, 0, 0, 13, 70, 120, 98, 43, 10, 1, 0, 0, 0, 5, 61, 171, 211, 140, 53, 11, 1, 0, 0, 0, 1, 40, 192, 356, 343, 192, 64, 12, 1

Offset: 1

Emeric Deutsch, Jun 14 2012

The entries in row n are the coefficients of the domination polynomial of the path P_n (see the Alikhani and Peng reference).

Sum of entries in row n = A000213(n+1) (number of dominating subsets; tribonacci numbers).

			Row 3 is [1,3,1] because the path tree A-B-C has dominating subsets B, AB, BC, AC, and ABC.
Triangle starts:
1;
2,1;
1,3,1;
0,4,4,1;
0,3,8,5,1;

S. Alikhani and Y. H. Peng, Dominating sets and domination polynomials of paths, International J. Math. and Math. Sci., Vol. 2009, Article ID542040.

Alois P. Heinz, Rows n = 1..141, flattened
S. Alikhani and Y. H. Peng, Introduction to domination polynomial of a graph, arXiv:0905.2251.
JL Arocha, B Llano, The number of dominating k-sets of paths, cycles and wheels, arXiv preprint arXiv:1601.01268, 2016
Eric Weisstein's World of Mathematics, Domination Polynomial
Eric Weisstein's World of Mathematics, Path Graph

Cf. A000213, A212634, A212635.

p := proc (n) option remember; if n = 1 then x elif n = 2 then x^2+2*x elif n = 3 then x^3+3*x^2+x else sort(expand(x*(p(n-1)+p(n-2)+p(n-3)))) end if end proc: for n to 15 do seq(coeff(p(n), x, k), k = 1 .. n) end do; # yields sequence in triangular form

p[1] = x; p[2] = 2*x + x^2; p[3] = x + 3*x^2 + x^3; p[n_] := p[n] = x*(p[n - 1] + p[n - 2] + p[n - 3]); row[n_] := CoefficientList[p[n], x] // Rest;
Array[row, 15] // Flatten (* Jean-François Alcover, Feb 24 2016 *)
CoefficientList[LinearRecurrence[{x, x, x}, {1, 2 + x, 1 + 3 x + x^2}, 10], x] // Flatten (* Eric W. Weisstein, Apr 07 2017 *)

If p(n)=p(n,x) denotes the generating polynomial of row n (called the domination polynomial of the path tree P_n), then p(1)=x, p(2) = 2x + x^2, p(3) = x + 3x^2 + x^3 and p(n) = x*[p(n-1) + p(n-2) + p(n-3)] for n>=4 (see Eq. (3.2) in the Alikhani & Peng journal reference).

A284966 Triangle read by rows: coefficients of the scaled Lucas polynomials x^(n/2)*L(n, sqrt(x)) for n >= 0, sorted by descending powers of x.

Original entry on oeis.org

2, 1, 0, 2, 1, 0, 0, 3, 1, 0, 0, 2, 4, 1, 0, 0, 0, 5, 5, 1, 0, 0, 0, 2, 9, 6, 1, 0, 0, 0, 0, 7, 14, 7, 1, 0, 0, 0, 0, 2, 16, 20, 8, 1, 0, 0, 0, 0, 0, 9, 30, 27, 9, 1, 0, 0, 0, 0, 0, 2, 25, 50, 35, 10, 1, 0, 0, 0, 0, 0, 0, 11, 55, 77, 44, 11, 1, 0, 0, 0, 0, 0, 0, 2, 36, 105, 112, 54, 12, 1

Offset: 0

Eric W. Weisstein, Apr 06 2017

For n >= 3, also the coefficients of the edge and vertex cover polynomials for the n-cycle graph C_n.

For more information on how this triangular array is related to the work of Charalambides (1991) and Moser and Abramson (1969), see the comments for triangular array A212634 (which contains additional formulas). The coefficients of these polynomials are given by formula (2.1), p. 291, in Charalambides (1991), where an obvious typo in the index of the summation must be corrected (floor(n/K) -> floor(n/K) - 1). - Petros Hadjicostas, Jan 27 2019

			First few polynomials are
  2;
  x;
  2*x + x^2;
  3*x^2 + x^3;
  2*x^2 + 4*x^3 + x^4;
  5*x^3 + 5*x^4 + x^5;
  ...
giving
  2;
  0, 1;
  0, 2, 1;
  0, 0, 3, 1;
  0, 0, 2, 4, 1;
  0, 0, 0, 5, 5, 1;
  ...

C. A. Charalambides, Lucas numbers and polynomials of order k and the length of the longest circular success run, The Fibonacci Quarterly, 29 (1991), 290-297.
W. O. J. Moser and M. Abramson, Enumeration of combinations with restricted differences and cospan, J. Combin. Theory, 7 (1969), 162-170.
Eric Weisstein's World of Mathematics, Cycle Graph
Eric Weisstein's World of Mathematics, Edge Cover Polynomial
Eric Weisstein's World of Mathematics, Lucas Polynomial
Eric Weisstein's World of Mathematics, Vertex Cover Polynomial

Cf. A034807 (Lucas polynomials x^(n/2)*L(n, 1/sqrt(x))).

Cf. A111125, A127677, A136481, A212634.

L := proc (n, K, x) -1 + sum((-1)^j*n*binomial(n - j*K, j)*x^j*(x+1)^(n - j*(K+1))/(n - j*K), j = 0 .. floor(n/(K + 1))) end proc; for i to 30 do expand(L(i, 2, x)) end do; # gives the g.f. of row n for 1 <= n <= 30. - Petros Hadjicostas, Jan 27 2019

CoefficientList[Table[x^(n/2) LucasL[n, Sqrt[x]], {n, 12}], x] // Flatten (* Eric W. Weisstein, Apr 06 2017 *)
CoefficientList[Table[2 x^n (-1/x)^(n/2) ChebyshevT[n, 1/(2 Sqrt[-1/x])], {n, 12}], x] // Flatten (* Eric W. Weisstein, Apr 06 2017 *)
CoefficientList[Table[FunctionExpand[2 (-(1/x))^(n/2) x^n Cos[n ArcSec[2 Sqrt[-(1/x)]]]], {n, 15}], x] // Flatten (* Eric W. Weisstein, Apr 06 2017 *)
CoefficientList[LinearRecurrence[{x, x}, {x, x (2 + x)}, 15], x] // Flatten (* Eric W. Weisstein, Apr 06 2017 *)

First element T(n=0, k=0) and the example corrected by Petros Hadjicostas, Jan 27 2019

Name edited by Petros Hadjicostas, Jan 27 2019 and by Stefano Spezia, Mar 09 2025

A213668 Irregular triangle read by rows: T(n,k) is the number of dominating subsets with k vertices of the graph G(n) consisting of a pair of endvertices joined by n internally disjoint paths of length 2 (the n-ary generalized theta graph THETA_{2,2,...2}; n>=1, 1<=k<=n+2).

Original entry on oeis.org

1, 3, 1, 0, 6, 4, 1, 0, 7, 10, 5, 1, 0, 9, 16, 15, 6, 1, 0, 11, 25, 30, 21, 7, 1, 0, 13, 36, 55, 50, 28, 8, 1, 0, 15, 49, 91, 105, 77, 36, 9, 1, 0, 17, 64, 140, 196, 182, 112, 45, 10, 1, 0, 19, 81, 204, 336, 378, 294, 156, 55, 11, 1

Offset: 1

Emeric Deutsch, Jul 06 2012

Row n>=2 contains n+1 entries.
Sum of entries in row n=3*2^n-1 = A052940(n) = A153893(n) = A055010(n+1) = A083329(n+1).
The graph G(n) is the join of the graph consisting of 2 isolated vertices and the graph consisting of n isolated vertices. Then the expression of the domination polynomial follows from Theorem 12 of the Akbari et al. reference.

			Row 1 is 1,3,1 because the graph G(1) is the path abc; there are 1 dominating subset of size 1 ({b}), 3 dominating subsets of size 2 ({a,b}, {a,c}, {b,c}), and 1 dominating subset of size 3 ({a,b,c}).
Row 2 is 0,6,4,1 because the graph G(2) is the cycle a-b-c-d-a and has dominating subsets ab, ac, ad, bc, bd, cd, abc, abd, acd, bcd, and abcd (see A212634).
Triangle starts:
1,3,1;
0,6,4,1;
0,7,10,5,1;
0,9,16,15,6,1;

S. Akbari, S. Alikhani, and Y. H. Peng, Characterization of graphs using domination polynomials, European J. Comb., 31, 2010, 1714-1724.

S. Alikhani and Y. H. Peng, Introduction to domination polynomial of a graph, arXiv:0905.2251.
T. Kotek, J. Preen, F. Simon, P. Tittmann, and M. Trinks, Recurrence relations and splitting formulas for the domination polynomial, arXiv:1206.5926.

Cf. A052940, A153893, A055010, A083329, A212634

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

T[n_, k_] := SeriesCoefficient[((1+x)^n-1) ((1+x)^2-1)+x^n+x^2, {x, 0, k}];
Table[T[n, k], {n, 1, 9}, {k, 1, n+2}] // Flatten (* Jean-François Alcover, Dec 06 2017 *)

The generating polynomial of row n is p(n)=((1+x)^n-1)*((1+x)^2-1)+x^n+x^2; by definition, p(n) is the domination polynomial of the graph G(n).
Bivariate g.f.: x*z/(1-x*z)-2*x*z/(1-z)+x*z*(1+x)*(2+x)/(1-z-x*z).
T(n,3)=n^2 for n!=3.

cp's OEIS Frontend

A212635 Irregular triangle read by rows: T(n,k) is the number of dominating subsets with cardinality k of the wheel W_n (n >= 4, 1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A212633 Triangle read by rows: T(n,k) is the number of dominating subsets with cardinality k of the path tree P_n (n>=1, 1<=k<=n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A284966 Triangle read by rows: coefficients of the scaled Lucas polynomials x^(n/2)*L(n, sqrt(x)) for n >= 0, sorted by descending powers of x.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A213668 Irregular triangle read by rows: T(n,k) is the number of dominating subsets with k vertices of the graph G(n) consisting of a pair of endvertices joined by n internally disjoint paths of length 2 (the n-ary generalized theta graph THETA_{2,2,...2}; n>=1, 1<=k<=n+2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula