cp's OEIS Frontend

This sequence is part of a family of sequences, namely R(n,k), the number of ks in palindromic compositions of n. See also A057711, A001792, A078836, A079861, A079862. General formula: R(n,k)=2^(floor(n/2) - k) * (2 + floor(n/2) - k) if n and k have different parity and R(n,k)=2^(floor(n/2) - k) * (2 + floor(n/2) - k + 2^(floor((k+1)/2 - 1)) otherwise, for n >= 2k.

Essentially the same as A057711: a(n) = A057711(n) for n >= 1.

Number of permutations of length n>=0 avoiding the partially ordered pattern (POP) {1>2, 1>3} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first element is larger than the second and third elements. - Sergey Kitaev, Dec 08 2020

Table starts

...0.....1......2........6.........16..........40............96.............224

...1.....4.....20.......84........324........1188..........4212...........14580

...2....20....140......863.......4962.......27313........145932..........763031

...6....84....863.....7940......68790......573342.......4651079........36985536

..16...324...4962....68790.....903332....11451686.....141595454......1718447506

..40..1188..27313...573342...11451686...221410052....4182294415.....77626332302

..96..4212.145932..4651079..141595454..4182294415..120864516084...3435347473308

.224.14580.763031.36985536.1718447506.77626332302.3435347473308.149656305350148

This sequence is part of a family of sequences, namely R(n,k), the number of ks in palindromic compositions of n. See also A057711, A001792, A078836, A079861, A079862. General formula: R(n,k)=2^(floor(n/2) - k) * (2 + floor(n/2) - k) if n and k have different parity and R(n,k)=2^(floor(n/2) - k) * (2 + floor(n/2) - k + 2^(floor((k+1)/2 - 1)) otherwise, for n >= 2k.

Conjecture: column k > 0 is asymptotic to n * 2^(n-2*k) * k^(n-1). - Vaclav Kotesovec, Oct 26 2015

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)

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.

Pascal-like triangle: start with 1 at top; every subsequent entry is the sum of everything above you, plus 1.

Binomial transform of A057711. 2nd binomial transform of (0,1,0,3,0,5,0,7,...).