

A320341


Triangle read by rows: T(n,k) is the number of unmarked circular binary words (necklaces) of length n having k occurrences of the pattern 00 (n >= 0 and 0 <= k <= n).


6



1, 1, 1, 2, 0, 1, 2, 1, 0, 1, 3, 1, 1, 0, 1, 3, 2, 1, 1, 0, 1, 5, 3, 3, 1, 1, 0, 1, 5, 5, 4, 3, 1, 1, 0, 1, 8, 8, 8, 5, 4, 1, 1, 0, 1, 10, 13, 13, 11, 6, 4, 1, 1, 0, 1, 15, 21, 24, 19, 14, 7, 5, 1, 1, 0, 1, 19, 34, 40, 36, 26, 17, 8, 5, 1, 1, 0, 1, 31, 55, 71, 67, 54, 34, 22, 9, 6, 1, 1, 0, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

The array T(n,k) is the number of unmarked circular binary words (necklaces) of length n having exactly k occurrences of 00 (n >= 0 and 0 <= k <= n). Let V(n,k) be the number of marked 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. It turns out that V(n,k) = A119458(n,k). The properties of the array V(n,k) were studied by Carlitz and Scoville (1977).
Both for this array and for array V(n,k) = A119458(n,k) we have T(n=1, k=0) = T(n=1, k=1) = V(n=1, k=0) = V(n=1, k=1) = 1, which means in both arrays we (indirectly) assume 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 = V(n,k) when k > n. Using the theory in Flajolet and Soria (1991), Flajolet and Sedgewick (2009), and Hadjicostas and Zhang (2018), we can prove that the g.f. of the numbers T(n,k) is F(z,t) = Sum_{n >= 0, k >= 0} T(n,k)*z^n*t^k = 1  Sum_{d>=1} (phi(d)/d)*log(1A(z^d,t^d)) while the g.f. of the numbers V(n,k) is K(z,t) = 1  z*(d(1A(z,t))/dz)/(1A(z,t)), where A(z,t) = z*(t+1) + z^2*(1t). (The latter g.f. was proved in Carlitz and Scoville (1977).)
We can also prove that T(n,k) = (1/n)*Sum_{dgcd(n,k)} phi(d)*V(n/d, k/d) for n>=1 and 0 <= k <= n.
For k=0, we get that T(n, k=0) = A000358(n) and V(n, k=0) = A000204(n) and for n >= 1. To get univariate g.f.'s of the sequences (T(n,k): n >= 1) and (V(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 from the g.f. of T(n,k).)
For k=1, we get T(n, k=1) = A212804(n1) = A006490(n)/n and V(n, k=1) = A006490(n) for n >= 1.
For k=2, we get T(n, k=2) = (1/n)*(V(n,2) + I(2n)*V(n/2,1)) for n >= 1, where I(2n) = 1 if 2n, and 0 otherwise. Also, V(n, k=2) = A006491(n1) for n >= 1 (with A006491(0) := 0).
For k=3, we get T(n, k=3) = (1/n)*(V(n,3) + 2*I(3n)*V(n/3, 1)) for n >= 1. Also,
V(n, k=3) = A006492(n2) for n >=1 (with A006492(m) = 0 for m = 1, 2). To get the g.f. for (T(n,k=3): n >= 0), we differentiate F(z,t) three times w.r.t. t, set t=0, and divide by 3! = 6. We get: 2*z^3*(1z^3)/(3*(1z^3z^6)) + z^3*(1z)^3/(3*(1zz^2)^3) = z^3 + 0*z^4 + z^5 + z^6 + 3*z^7 + 5*z^8 + 11*z^9 + 19*z^10 + 36*z^11 + 67*z^12 + 122*z^13 + 222*z^14 + ...
For 0 <= k <= n, T(n,k)  I(k=0) is the number of cyclic compositions of n with exactly k ones, where I(k=0) is 1 if k=0, and 0 otherwise. This can be proved using MacMahon's bijection between binary necklaces of length n and (unmarked) cyclic compositions of n. (We exclude the binary necklace consisting only of 1's, and that is why we need the term I(k=0).)
Given a binary necklace of 0's and 1's with length n (with at least one 0), starting with a 0 and going clockwise, let b_1 be the number of 1's until before the next zero plus one (for the initial 0); starting with the next zero, let b_2 be the number of 1's plus one (for the 2nd 0); continue this process until you reach the last 0 (say the mth 0), and denote by b_m the number of 1's plus one before the first 0. Then b_1 + b_2 + ... + b_m is a cyclic composition of n. The process can be reversed (since b_1, b_2, ..., b_m >= 1). The only necklace that cannot be obtained from a cyclic composition is the one having all 1's, which we exclude. In the above process, b_i = 1 if and only if the ith 0 in the above process is followed by 0 (to the right of it on the circle). Hence, for 0 <= k <= n, T(n,k)  I(k=0) is the number of cyclic compositions of n with exactly k ones.
Note that array A105422(n,k) is the linear version of this array: A105422(n,k) is the number of (linear) compositions of n having exactly k parts equal to 1. The denominator of the bivariate g.f. of array A105422(n,k) is indeed 1  A(z,t), where A(z,t) = z*(t+1) + z^2*(1t) (see above), and this is no coincidence.


LINKS

Table of n, a(n) for n=0..90.
L. Carlitz and R. Scoville, Zeroone sequences and Fibonacci numbers, Fibonacci Quarterly, 15 (1977), 246254.
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. 5860.
P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 5860.
P. Hadjicostas and L. Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 16621674.
L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 8996.


FORMULA

T(n,k) = (1/n)*Sum_{dgcd(n,k)} phi(d)*A119458(n/d, k/d) for n>=1 and 0 <= k <= n.
G.f.: F(z,t) = Sum_{n >= 0, k >= 0} T(n,k)*z^n*t^k = 1  Sum_{d>=1} (phi(d)/d)*log(1A(z^d,t^d)), where A(z,t) = z*(t+1) + z^2*(1t).


EXAMPLE

Triangle for T(n,k) begins:
n=0: 1;
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;
...
If we take the Taylor expansion of g.f. F(z,t) of T(n,k) around z=0, we get F(z,t) = 1 + (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 + ...
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], V(4,0) = 7 and T(4,0) = 3;
k=1: [1100,1001,0011,0110], V(4,1) = 4 and T(4,1) = 1;
k=2: [0001,0010,0100,1000], V(4,2) = 4 and T(4,2) = 1;
k=3: none, V(4,3) = 0 = T(4,3);
k=4: [0000], V(4,4) = 1 = T(4,4).
The corresponding cyclic compositions of n=4 under MacMahon's bijection are the following:
k=0 (no 1's): [none], [4], [2+2], T(4,1)  1 = 3  1 = 2;
k=1 (one 1): [1+3], T(4,1) = 1;
k=2 (two 1's): [1+1+2], T(4,2) = 1;
k=3 (three 1's): none, T(4,3) = 0;
k=4 (four 1's): [1+1+1+1], T(4,4) = 1.


CROSSREFS

Cf. A000079, A000204, A000358, A006490, A006491, A006492, A057711, A105422, A119458, A212804.
Sequence in context: A136266 A292047 A292049 * A054523 A161363 A293136
Adjacent sequences: A320338 A320339 A320340 * A320342 A320343 A320344


KEYWORD

nonn,tabl


AUTHOR

Petros Hadjicostas, Jan 07 2019


STATUS

approved



