login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A212634 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). 4
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, 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, 0, 11, 99, 231, 253, 154, 55, 11, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

Sum of entries in row n = A001644(n) (number of dominating subsets; tribonacci numbers with initial values 1,3,7).

From Petros Hadjicostas, Jan 26 2019: (Start)

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

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.

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.

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.

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

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

(End)

LINKS

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

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

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

S. Alikhani and Y. H. Peng, Dominating sets and domination polynomials of certain graphs, II, Opuscula Math., 30, No. 1, 2010, 37-51.

J. L. Arocha, B. Llano, The number of dominating k-sets of paths, cycles and wheels, arXiv preprint arXiv:1601.01268 [math.CO], 2016.

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, Domination Polynomial

FORMULA

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

From Petros Hadjicostas, Jan 26 2019: (Start)

T(n, k) = binomial(n, k) for 1 <= k <= n and n = 1, 2.

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

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

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

(End)

EXAMPLE

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.

Triangle starts:

1;

2, 1;

3, 3,  1;

0, 6,  4,  1;

0, 5, 10,  5, 1;

0, 3, 14, 15, 6, 1;

...

From Petros Hadjicostas, Jan 27 2019: (Start)

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.

For each k below we give the corresponding (n-k)-combinations and the equivalent marked sequences of 0's and 1's.

k=1, n-k = 5: none; T(n=6, k=1) = 0.

k=2, n-k = 4: 1245 <-> 110110, 2356 <-> 011011, 1346 <-> 101101; T(n=6, k=2) = 3.

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.

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.

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.

k=6, n-k=0: empty combination <-> 000000; T(n=6, k=6) = 1.

(End)

MAPLE

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

MATHEMATICA

CoefficientList[LinearRecurrence[{x, x, x}, {1, 2 + x, 3 + 3 x + x^2}, 10], x] // Flatten (* Eric W. Weisstein, Apr 06 2017 *)

CROSSREFS

Cf. A001644, A125127, A284966, A322057.

Cf. A212635 (corresponding sequence for wheel graphs). - Eric W. Weisstein, Apr 06 2017

Sequence in context: A144243 A125210 A098434 * A162883 A081446 A274309

Adjacent sequences:  A212631 A212632 A212633 * A212635 A212636 A212637

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Jun 14 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 21 14:18 EST 2019. Contains 329371 sequences. (Running on oeis4.)