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

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

Offset: 0

Author

Petros Hadjicostas, Jan 07 2019

Keywords

• nonn
• tabl

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(1-A(z^d,t^d)) while the g.f. of the numbers V(n,k) is K(z,t) = 1 - z*(d(1-A(z,t))/dz)/(1-A(z,t)), where A(z,t) = z*(t+1) + z^2*(1-t). (The latter g.f. was proved in Carlitz and Scoville (1977).)

We can also prove that T(n,k) = (1/n)*Sum_{d|gcd(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(n-1) = 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(2|n)*V(n/2,1)) for n >= 1, where I(2|n) = 1 if 2|n, and 0 otherwise. Also, V(n, k=2) = A006491(n-1) for n >= 1 (with A006491(0) := 0).

For k=3, we get T(n, k=3) = (1/n)*(V(n,3) + 2*I(3|n)*V(n/3, 1)) for n >= 1. Also,

V(n, k=3) = A006492(n-2) 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*(1-z^3)/(3*(1-z^3-z^6)) + z^3*(1-z)^3/(3*(1-z-z^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 m-th 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 i-th 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*(1-t) (see above), and this is no coincidence.

Examples

			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.
		

Links

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

Crossrefs

Cf. A000079, A000204, A000358, A006490, A006491, A006492, A057711, A105422, A119458, A212804.

Formula

T(n,k) = (1/n)*Sum_{d|gcd(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(1-A(z^d,t^d)), where A(z,t) = z*(t+1) + z^2*(1-t).