|
%I #73 Dec 18 2020 08:36:25
%S 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,
%T 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,
%U 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
%N 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).
%C 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).
%C 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.
%C 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).)
%C 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.
%C 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).)
%C 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.
%C 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).
%C 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,
%C 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 + ...
%C 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).)
%C 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.
%C 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.
%H L. Carlitz and R. Scoville, <a href="http://www.fq.math.ca/Scanned/15-3/carlitz1.pdf">Zero-one sequences and Fibonacci numbers</a>, Fibonacci Quarterly, 15 (1977), 246-254.
%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009.
%H P. Flajolet and M. Soria, <a href="https://doi.org/10.1137/0404006">The Cycle Construction</a>, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
%H P. Flajolet and M. Soria, <a href="/A320341/a320341.pdf">The Cycle Construction</a>, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
%H P. Hadjicostas and L. Zhang, <a href="https://doi.org/10.1016/j.disc.2018.03.007">On cyclic strings avoiding a pattern</a>, Discrete Mathematics, 341 (2018), 1662-1674.
%H L. Zhang and P. Hadjicostas, <a href="http://www.appliedprobability.org/data/files/TMS%20articles/40_2_3.pdf">On sequences of independent Bernoulli trials avoiding the pattern '11..1'</a>, Math. Scientist, 40 (2015), 89-96.
%F T(n,k) = (1/n)*Sum_{d|gcd(n,k)} phi(d)*A119458(n/d, k/d) for n>=1 and 0 <= k <= n.
%F 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).
%e Triangle for T(n,k) begins:
%e n=0: 1;
%e n=1: 1, 1;
%e n=2: 2, 0, 1;
%e n=3: 2, 1, 0, 1;
%e n=4: 3, 1, 1, 0, 1;
%e n=5: 3, 2, 1, 1, 0, 1;
%e n=6: 5, 3, 3, 1, 1, 0, 1;
%e n=7: 5, 5, 4, 3, 1, 1, 0, 1;
%e n=8: 8, 8, 8, 5, 4, 1, 1, 0, 1;
%e n=9: 10, 13, 13, 11, 6, 4, 1, 1, 0, 1;
%e n=10: 15, 21, 24, 19, 14, 7, 5, 1, 1, 0, 1;
%e ...
%e 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 + ...
%e For example, for n=4, we have the following marked and unmarked circular binary words (the square brackets denote equivalence classes):
%e k=0: [1111], [1110,1101,1011,0111], [1010,0101], V(4,0) = 7 and T(4,0) = 3;
%e k=1: [1100,1001,0011,0110], V(4,1) = 4 and T(4,1) = 1;
%e k=2: [0001,0010,0100,1000], V(4,2) = 4 and T(4,2) = 1;
%e k=3: none, V(4,3) = 0 = T(4,3);
%e k=4: [0000], V(4,4) = 1 = T(4,4).
%e The corresponding cyclic compositions of n=4 under MacMahon's bijection are the following:
%e k=0 (no 1's): [none], [4], [2+2], T(4,1) - 1 = 3 - 1 = 2;
%e k=1 (one 1): [1+3], T(4,1) = 1;
%e k=2 (two 1's): [1+1+2], T(4,2) = 1;
%e k=3 (three 1's): none, T(4,3) = 0;
%e k=4 (four 1's): [1+1+1+1], T(4,4) = 1.
%Y Cf. A000079, A000204, A000358, A006490, A006491, A006492, A057711, A105422, A119458, A212804.
%K nonn,tabl
%O 0,4
%A _Petros Hadjicostas_, Jan 07 2019
|
