A378413 Irregular triangle read by rows: T(n,k) is the coefficient of x^k in the domination polynomial of the n-prism graph (n>=1, A004524(n+2)<=k<=2*n).

2, 1, 6, 4, 1, 9, 20, 15, 6, 1, 4, 24, 62, 56, 28, 8, 1, 10, 85, 192, 200, 120, 45, 10, 1, 51, 288, 618, 696, 483, 220, 66, 12, 1, 14, 210, 966, 2018, 2408, 1862, 987, 364, 91, 14, 1, 4, 80, 824, 3248, 6646, 8304, 6992, 4176, 1804, 560, 120, 16, 1, 18, 405

Offset

1,1

Comments

Sequence extended to n=1 using the recurrence.

Sum_{k=A004524(n+2)..2*n} T(n,k) = A284702(n).

T(n,2*n) = 1.

Links

Eric W. Weisstein, Table of n, a(n) for n = 1..462

Stephan Mertens, Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph, arXiv:2408.08053 [math.CO], Aug 2024.

Eric Weisstein's World of Mathematics, Dominating Set.

Eric Weisstein's World of Mathematics, Domination Number.

Eric Weisstein's World of Mathematics, Domination Polynomial.

Eric Weisstein's World of Mathematics, Prism Graph.

Formula

D(n) = (2*x+x^2)*D(n-1) + x^2*D(n-2) + (3*x^2+2x^3)*D(n-3) + x^2*D(n-4) + x^4*D(n-5) - x^4*D(n-6) -x^4*D(n-7), where D(n) = sum(T(n,k)*x^k,k).

Example

D(1) = 2*x+x^2
D(2) = 6*x^2+4*x^3+x^4
D(3) = 9*x^2+20*x^3+15*x^4+6*x^5+x^6
D(4) = 4*x^2+24*x^3+62*x^4+56*x^5+28*x^6+8*x^7+x^8
D(5) = 10*x^3+85*x^4+192*x^5+200*x^6+120*x^7+45*x^8+10*x^9+x^10

Mathematica

DeleteCases[#, 0] & /@ CoefficientList[LinearRecurrence[{2 x + x^2, x^2, 3 x^2 + 2 x^3, x^2, x^4, -x^4, -x^4}, {2 x + x^2, 6 x^2 + 4 x^3 + x^4, 9 x^2 + 20 x^3 + 15 x^4 + 6 x^5 + x^6, 4 x^2 + 24 x^3 + 62 x^4 + 56 x^5 + 28 x^6 + 8 x^7 + x^8, 10 x^3 + 85 x^4 + 192 x^5 + 200 x^6 + 120 x^7 + 45 x^8 + 10 x^9 + x^10, 51 x^4 + 288 x^5 + 618 x^6 + 696 x^7 + 483 x^8 + 220 x^9 + 66 x^10 + 12 x^11 + x^12, 14 x^4 + 210 x^5 + 966 x^6 + 2018 x^7 + 2408 x^8 + 1862 x^9 + 987 x^10 + 364 x^11 + 91 x^12 + 14 x^13 + x^14}, 10], x] // Flatten

Crossrefs

Cf. A004524 (domination number of the (n-2)-prism graph).

Cf. A284702 (number of dominating sets in the n-prism graph).

Cf. A005843 (vertex count of the n-prism graph = 2*n).

Sequence in context: A293409 A051482 A349573 * A208923 A185045 A208913

Adjacent sequences: A378410 A378411 A378412 * A378414 A378415 A378416

Keyword

nonn,tabf

Author

Eric W. Weisstein, Nov 25 2024

Status

approved