|
%I #72 Jan 29 2019 05:05:14
%S 1,2,1,3,3,1,0,6,4,1,0,5,10,5,1,0,3,14,15,6,1,0,0,14,28,21,7,1,0,0,8,
%T 38,48,28,8,1,0,0,3,36,81,75,36,9,1,0,0,0,25,102,150,110,45,10,1,0,0,
%U 0,11,99,231,253,154,55,11,1
%N Triangle read by rows: T(n,k) is the number of dominating subsets with cardinality k of the cycle C_n (n >= 1, 1 <= k <= n).
%C The entries in row n are the coefficients of the domination polynomial of the cycle C_n (see the Alikhani and Peng reference in Opuscula Math).
%C Sum of entries in row n = A001644(n) (number of dominating subsets; tribonacci numbers with initial values 1,3,7).
%C From _Petros Hadjicostas_, Jan 26 2019: (Start)
%C Let L(n, r, K) be the number of r-combinations of the n consecutive integers 1, 2, ..., n displaced on a circle, with no K integers consecutive (assuming that n and 1 are consecutive integers).
%C If on the circle where the n integers 1, 2, ..., n are displaced we put 1 for any integer that is included in the r-combination and 0 otherwise, we get a marked cyclic sequence of r ones and n-r zeros with no K consecutive ones.
%C Let L_{n,K}(x) = Sum_{r=0..floor(n-(n/K))} L(n, r, K)*x^(n-r) for n, K >= 1. Charalambides (1991) proved that L_{n,K}(x) = x*(n + Sum_{j=1..n-1} L_{n-j, K}(x)) for K >= 1 and 1 <= n <= K, and L_{n,K}(x) = x*Sum_{j=1..K} L_{n-j, K}(x) for K >= 1 and n >= K + 1. See Theorem 2.1 (p. 291) in his paper.
%C He also proved that L_{n,K}(x) = -1 + Sum_{j=0..floor(n/(K + 1))} (-1)^j*(n/(n-j*K))*binomial(n - j*K, j)*x^j*(1+x)^(n-j*(K+1)). See Theorem 2.3 (p. 293) in his paper.
%C He also produced other formulas for L(n, r, K) and L_{n,K}(x) including the explicit formulas of Moser and Abramson (1969) (regarding L(n, r, K)).
%C For the current sequence, we have T(n, k) = L(n, r = n-k, K = 3) for 1 <= n <= k. In other words, T(n, n-k) is the number of k-combinations of the n consecutive integers 1, 2, ..., n displaced on a circle, with no K = 3 consecutive integers (assuming n and 1 are consecutive).
%C (End)
%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 S. Alikhani and Y. H. Peng, <a href="http://dx.doi.org/10.1155/2009/542040">Dominating sets and domination polynomials of paths</a>, International J. Math. and Math. Sci., Vol. 2009, Article ID542040.
%H S. Alikhani and Y. H. Peng, <a href="http://dx.doi.org/10.7494/OpMath.2010.30.1.37">Dominating sets and domination polynomials of certain graphs, II</a>, Opuscula Math., 30, No. 1, 2010, 37-51.
%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 C. A. Charalambides, <a href="http://www.fq.math.ca/Scanned/29-4/charalambides.pdf">Lucas numbers and polynomials of order k and the length of the longest circular success run</a>, The Fibonacci Quarterly, 29 (1991), 290-297.
%H W. O. J. Moser and M. Abramson, <a href="https://doi.org/10.1016/S0021-9800(69)80051-7">Enumeration of combinations with restricted differences and cospan</a>, J. Combin. Theory, 7 (1969), 162-170.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CycleGraph.html">Cycle Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DominationPolynomial.html">Domination Polynomial</a>
%F If p(n)=p(n,x) denotes the generating polynomial of row n (called the domination polynomial of the cycle C_n), then p(1)=x, p(2) = 2x + x^2 , p(3) = 3x + 3x^2 + x^3 and p(n) = x*[p(n-1) + p(n-2) + p(n-3)] for n >= 4 (see Theorem 4.5 in the Alikhani & Peng reference in Opuscula Math.).
%F From _Petros Hadjicostas_, Jan 26 2019: (Start)
%F T(n, k) = binomial(n, k) for 1 <= k <= n and n = 1, 2.
%F T(n, k) = Sum_{j=0..floor(n/3)-1} (-1)^j*binomial(k, j)*(n/(n - 3*j))*binomial(n - 3*j, k) for n - floor(2*n/3) <= k <= n and n >= 3. (This is a special case of a corrected version of formula (2.1) in Charalambides (1991) and equation (14) in Moser and Abramson (1969).)
%F T(n, k) = 0 for 1 <= k < n - floor(2*n/3) and n >= 4. (Thus, the number of initial zeros in row n is n - floor(2*n/3) - 1.)
%F G.f. for row n: p(n, x) = -1 + Sum_{j=0..floor(n/4)} (-1)^j*(n/(n-3*j))*binomial(n - 3*j, j)*x^j*(1+x)^(n-4*j). It satisfies the recurrence given above (found in Alikhani and Peng (2010) and Charalambides (1991)).
%F (End)
%e Row 4 is [0,6,4,1] because the cycle A-B-C-D-A has dominating subsets AB, AC, AD, BC, BD, CD, ABC, ABD, ACD, BCD, and ABCD.
%e Triangle starts:
%e 1;
%e 2, 1;
%e 3, 3, 1;
%e 0, 6, 4, 1;
%e 0, 5, 10, 5, 1;
%e 0, 3, 14, 15, 6, 1;
%e ...
%e From _Petros Hadjicostas_, Jan 27 2019: (Start)
%e Let n=6 and 1 <= k <= 6. Then T(n, k) is the number of (n-k)-combinations of the integers 1, 2, 3, 4, 5, 6 displaced on a circle with no K=3 consecutive integers (assuming 6 and 1 are consecutive). Equivalently, T(n, k) is the number of marked cyclic sequences consisting of n-k ones and k zeros with no K=3 consecutive ones.
%e For each k below we give the corresponding (n-k)-combinations and the equivalent marked sequences of 0's and 1's.
%e k=1, n-k = 5: none; T(n=6, k=1) = 0.
%e k=2, n-k = 4: 1245 <-> 110110, 2356 <-> 011011, 1346 <-> 101101; T(n=6, k=2) = 3.
%e k=3, n-k = 3: 124 <-> 110100, 125 <-> 110010, 134 <-> 101100, 135 <-> 101010, 136 <-> 101001, 145 <-> 100110, 146 <-> 100101, 235 <-> 011010, 236 <-> 011001, 245 <-> 010110, 246 <-> 010101, 256 <-> 010011, 346 <-> 001101, 356 <-> 001011; T(n=6, k=3) = 14.
%e k=4, n-k=2: all 2-combinations of the integers 1,2,3,4,5,6 and all marked cyclic sequences with exactly 2 ones and 4 zeros; hence, T(n=6, k=4) = binomial(6, 2) = 15.
%e k=5, n-k=1: all 1-combinations of the integers 1,2,3,4,5,6 and all marked cyclic sequences with exactly 1 one and 5 zeros; hence, T(n=6, k=5) = binomial(6, 1) = 6.
%e k=6, n-k=0: empty combination <-> 000000; T(n=6, k=6) = 1.
%e (End)
%p p := 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*(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
%t CoefficientList[LinearRecurrence[{x, x, x}, {1, 2 + x, 3 + 3 x + x^2}, 10], x] // Flatten (* _Eric W. Weisstein_, Apr 06 2017 *)
%Y Cf. A001644, A125127, A284966, A322057.
%Y Cf. A212635 (corresponding sequence for wheel graphs). - _Eric W. Weisstein_, Apr 06 2017
%K nonn,tabl
%O 1,2
%A _Emeric Deutsch_, Jun 14 2012
|
