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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A119458 Triangle read by rows: T(n,k) is the number of (marked) circular binary words of length n having k occurrences of 00 (0 <= k <= n). 6
1, 1, 1, 3, 0, 1, 4, 3, 0, 1, 7, 4, 4, 0, 1, 11, 10, 5, 5, 0, 1, 18, 18, 15, 6, 6, 0, 1, 29, 35, 28, 21, 7, 7, 0, 1, 47, 64, 60, 40, 28, 8, 8, 0, 1, 76, 117, 117, 93, 54, 36, 9, 9, 0, 1, 123, 210, 230, 190, 135, 70, 45, 10, 10, 0, 1, 199, 374, 440, 396, 286, 187, 88, 55, 11, 11, 0, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

Sum of entries in row n is 2^n (A000079).

In Carlitz and Scoville (p. 252) the first term is 2.

From Petros Hadjicostas, Jan 05 2019: (Start)

Note that T(n,k) is the number of marked circular binary words of length n having k occurrences of 00 (0 <= k <= n). Let W(n,k) be the number of binary necklaces (= unmarked circular binary words) of length n with exactly k occurrences of the pattern 00 provided wrapping around the circle is allowed when n=1. More precisely, when n=1, we allow the string to wrap around itself on the circle to form a circular string of length 2. We have W(n, k) = A320341(n, k) for 0 <= k <= n.

Fortunately, since T(n=1, k=0) = 1 = T(n=1, k=1), the author of the sequence (indirectly) assumes that the string 0 has one occurrence of the pattern 00 (if allowed to wrap around itself on the circle only once), while the string 1 has zero occurrences of the pattern 00.

It makes sense to define T(n,k) = 0 when k > n. Note that G(z,t) = Sum_{n,k >=0} T(n,k)*z^n*t^k = 1 - z*(d(1-A(z,t))/dz)/(1-A(z,t)), where A(z,t) = z*(t+1) + z^2*(1-t) is the "Flajolet-Soria polynomial (g.f.)" in z of some (difficult to find) linear combinatorial structure that is defined very abstractly at the beginning of their paper and in the book by Flajolet and Sedgewick (2009). (Since the series here converge for z and t close to 0, we have that 1-t is positive for all t in a "small" interval around 0.)

Using the theory in Flajolet and Soria (1991) and the one in Hadjicostas and Zhang (2018), we can prove that the g.f. of the numbers W(n,k) is F(z,t) = Sum_{n >= 1, k >= 0} W(n,k)*z^n*t^k = -Sum_{d>=1} (phi(d)/d)*log(1-A(z^d,t^d)). We can also prove that W(n,k) = (1/n)*Sum_{d|gcd(n,k)} phi(d)*T(n/d, k/d) for n>=1 and 0 <= k <= n. (We omit the details.)

For  k=0, we get that T(n, k=0) = A000204(n) and W(n, k=0) = A000358(n) for n >= 1, and the Flajolet-Soria polynomial is A(z,t=0) = z + z^2 (which was discovered by Joerg Arndt).

To get univariate g.f.'s of the sequences (T(n,k): n >= 1) and (W(n, k): n >= 1) when k >= 1, we have to differentiate the previous two g.f.'s k times with respect to t, set t=0, and divide by k!. (Obviously, the log now disappears.)

For k=1, we get T(n, k=1) = A006490(n) and W(n, k=1) = A212804(n-1) = A006490(n)/n for n >= 1.

For k=2, we get T(n, k=2) = A006491(n-1) for n >= 1 (with A006491(0) := 0) and W(n, k=2) = (1/n)*(T(n,2) + I(2|n)*T(n/2,1)) for n >= 1, where I(2|n) = 1 if 2|n, and 0 otherwise.

For k=3, we get T(n, k=3) = A006492(n-2) for n >=1 (with A006492(m) = 0 for m = 1,2) and W(n, k=3) = (1/n)*(T(n,3) + 2*I(3|n)*T(n/3, 1)) for n >= 1.

This theory can be generalized for any pattern P of 0's and 1's provided one discovers the correct "Flajolet-Soria" polynomial A_P(z,t). In other words, if P is a finite pattern of zeros and ones of length L, and we let T_P(n,k) be the number of (marked) circular binary words of length n having k occurrences of P (0 <= k <= n) and we allow strings of length n, with 1 <= n < L, to wrap around themselves on the circle to form a string of length n*ceiling(L/n), then (most probably) we can express the g.f. of T_p(n,k), say G_p(z,t), in the form 1-z*(d(1-A_P(z,t))/dz)/(1-A_P(z,t)). In such a case, if W_P(n,k) is the number of binary necklaces (= unmarked circular binary words) of length n with exactly k occurrences of the pattern P, we have that its generating function is Sum_{n >= 1, k >= 0} W_P(n,k)*z^n*t^k = -Sum_{d>=1} (phi(d)/d)*log(1-A_P(z^d,t^d)). We can also prove that W_P(n,k) = (1/n)*Sum_{d|gcd(n,k)} phi(d)*T_P(n/d, k/d) for n>=1 and 0 <= k <= n.

One final note: it seems that the theory of Flajolet and Soria (1991) applies only to the case k=0 and to the case we consider all k simultaneously. (For fixed k >= 2, W_P(n,k) depends not only on T_P(n,k), but also on all T(n/d, k/d) where d ranges over the common divisors of n and k. Thus, for fixed k >= 2, it seems there is no linear combinatorial structure whose list of cycles of elements corresponds to the collection of necklaces we want.) See also Flajolet and Sedgewick (2009), pp. 84-85 and 729-730.

(End)

LINKS

Table of n, a(n) for n=0..77.

L. Carlitz and R. Scoville, Zero-one sequences and Fibonacci numbers, Fibonacci Quarterly, 15 (1977), 246-254.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009.

P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.

P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.

P. Hadjicostas and L. Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 1662-1674.

L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96.

FORMULA

T(n,k) = T(n-1,k) + T(n-2,k) + T(n-1,k-1) - T(n-2,k-1) for n >= 3 and k >= 1.

G.f.: G(z,t) = Sum_{n,k >=0} T(n,k)*z^n*t^k = (1 + z^2 - t*z^2)/(1 - z - z^2 - t*z + t*z^2). [edited by Petros Hadjicostas, Jan 05 2019]

T(n,0) = A000204(n) for n >= 1 (Lucas numbers).

T(n,1) = A006490(n) for n >= 1.

T(n,2) = A006491(n-1) for n >= 1 (with A006491(0):=0).

Sum_{k=0..n} k*T(n,k) = A057711(n).

EXAMPLE

T(5,3) = 5 because we have 10000, 01000, 00100, 00010 and 00001.

Triangle for T(n,k) begins:

n=0:    1;

n=1:    1,   1;

n=2:    3,   0,   1;

n=3:    4,   3,   0,   1;

n=4:    7,   4,   4,   0,   1;

n=5:   11,  10,   5,   5,   0,  1

n=6:   18,  18,  15,   6,   6,  0,  1;

n=7:   29,  35,  28,  21,   7,  7,  0,  1;

n=8:   47,  64,  60,  40,  28,  8,  8,  0,  1;

n=9:   76, 117, 117,  93,  54, 36,  9,  9,  0, 1;

n=10: 123, 210, 230, 190, 135, 70, 45, 10, 10, 0, 1;

  ...

From Petros Hadjicostas, Jan 06 2019: (Start)

If we take the Taylor expansion of g.f. G(z,t) of T(n,k) around z=0, we get G(z,t) = 1 + (1+t)*z + (3+0*t+t^2)*z^2 + (4+3*t+0*t^2+t^3)*z^3 + (7+4*t+4*t^2+0*t^3+t^4)*z^4 +(11+10*t+5*t^2+5*t^3+0*t^4+t^5)*z^5 + ...

One the other hand, if we take the Taylor expansion of the g.f. F(z,t) of W(n,k) = A320341(n, k) around z=0, we get F(z,t) = (1+t)*z + (2+0*t+t^2)*z^2 + (2+t+0*t^2+t^3)*z^3 + (3+t+t^2+0*t^3+t^4)*z^4 + (3+2*t+t^2+t^3+0*t^4+t^5)*z^5 + ...

Triangle for W(n,k) begins:

n=1:    1,  1;

n=2:    2,  0,  1;

n=3:    2,  1,  0,  1;

n=4:    3,  1,  1,  0,  1;

n=5:    3,  2,  1,  1,  0,  1;

n=6:    5,  3,  3,  1,  1,  0,  1;

n=7:    5,  5,  4,  3,  1,  1,  0,  1;

n=8:    8,  8,  8,  5,  4,  1,  1,  0,  1;

n=9:   10, 13, 13, 11,  6,  4,  1,  1,  0, 1;

n=10:  15, 21, 24, 19, 14,  7,  5,  1,  1, 0, 1;

...

For example, for n=4, we have the following marked and unmarked circular binary words (the square brackets denote equivalence classes):

k=0: [1111], [1110,1101,1011,0111], [1010,0101], T(4,0) = 7 and W(4,0) = 3;

k=1: [1100,1001,0011,0110], T(4,1) = 4 and W(4,1) = 1;

k=2: [0001,0010,0100,1000], T(4,2) = 4 and W(4,2) = 1;

k=3: none, T(4,3) = 0 = W(4,3);

k=4: [0000], T(4,4) = 1 = W(4,4).

(End)

MAPLE

T:=proc(n, k): if k>n or k<0 then 0 elif n=0 and k=0 then 1 elif n=1 then 1 elif n=2 and k=0 then 3 elif n=2 and k=1 then 0 else T(n-1, k)+T(n-2, k)+T(n-1, k-1)-T(n-2, k-1) fi end: for n from 0 to 12 do seq(T(n, k), k=0..n) od; # yields sequence in triangular form

MATHEMATICA

T[n_, k_] := T[n, k] = Which[k > n || k < 0, 0, n == 0 && k == 0, 1, n == 1, 1, n == 2 && k == 0, 3, n == 2 && k == 1, 0, True, T[n-1, k] + T[n-2, k] + T[n-1, k-1] - T[n-2, k-1]];

Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-Fran├žois Alcover, Jan 11 2019 *)

CROSSREFS

Cf. A000079, A000204, A000358, A006490, A006491, A006492, A057711, A212804, A320341.

Sequence in context: A197126 A256987 A048963 * A106356 A091613 A039727

Adjacent sequences:  A119455 A119456 A119457 * A119459 A119460 A119461

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, May 20 2006

EXTENSIONS

Name was edited by Petros Hadjicostas, Jan 06 2019

Values of T(9,5) and T(9,6) were corrected in the example by Petros Hadjicostas, Jan 06 2019

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 June 15 22:19 EDT 2019. Contains 324145 sequences. (Running on oeis4.)