|
%I #24 Nov 24 2017 12:37:41
%S 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,
%T 8,1,1,8,36,94,118,84,36,9,1,1,9,39,120,207,201,120,45,10,1,1,10,45,
%U 145,312,402,320,165,55,11,1,1,11,55,176,429,693,715,484,220,66,12,1
%N 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).
%C The entries in row n are the coefficients of the domination polynomial of the wheel W_n (see the Alikhani and Peng arxiv reference).
%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 J. L. Arocha, B. Llano, <a href="https://arxiv.org/abs/1601.01268">The number of dominating k-sets of paths, cycles and wheels</a>, arXiv preprint arXiv:1601.01268 [math.CO], 2016.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DominationPolynomial.html">Domination Polynomial</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/WheelGraph.html">Wheel Graph</a>
%F 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.
%F 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).
%e 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).
%e 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}.
%e Irregular triangle starts:
%e 4, 6, 4, 1;
%e 1, 10, 10, 5, 1;
%e 1, 10, 20, 15, 6, 1;
%e 1, 9, 29, 35, 21, 7, 1;
%p 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
%t 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])]]];
%t p[n_] := Sort[Expand[x*(1 + x)^(n - 1) + pc[n - 1]]];
%t Table[Coefficient[p[n], x, k], {n, 4, 15}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Nov 24 2017, after _Emeric Deutsch_ *)
%Y Cf. A212634.
%K nonn,tabf
%O 4,1
%A _Emeric Deutsch_, Jun 17 2012
|
