cp's OEIS Frontend

A variant of the Fibonacci number A000045.

Number of compositions of n into parts >= 2. - Joerg Arndt, Aug 13 2012

From Petros Hadjicostas, Jan 08 2019: (Start)

For n >= 0, a(n) is the number of unmarked circular binary words (necklaces) of length n+1 with exactly one occurrence of the pattern 00 (provided we allow the strings of length 1, i.e., 0 and 1, to wrap around themselves on a circle to form strings of length 2). See the comments for array A320341.

Using MacMahon's bijection between necklaces and cyclic compositions, we conclude that a(n) is also the number of (unmarked) cyclic compositions of n+1 with exactly one 1.

Removing the single 1 from each cyclic composition of n+1, we get all linear compositions of n with each part >= 2, which is what is stated above by Joerg Arndt. (End)

a(n) is also the number of inequivalent compositions of n into parts 1 and 2 where two compositions are considered to be equivalent if one is a cyclic rotation of the other. a(6)=5 because we have: 2+2+2, 2+2+1+1, 2+1+2+1, 2+1+1+1+1, 1+1+1+1+1+1. - Geoffrey Critzer, Feb 01 2014

Moebius transform is A006206. - Michael Somos, Jun 02 2019

T(n,k) is also the number of length n bit strings beginning with 0 having k singletons. Example: T(4,2)=3 because we have 0010, 0100 and 0110. - Emeric Deutsch, Sep 21 2008

The cyclic version of this array is A320341(n,k), which counts the (unmarked) cyclic compositions of n with exactly k parts equal to 1, with a minor exception for k=0. The sequence (A320341(n, k=0) - 1: n >= 1) counts the (unmarked) cyclic compositions of n with no parts equal to 1. - Petros Hadjicostas, Jan 08 2019

Also the convolution triangle of Fibonacci(n-2). # Peter Luschny, Oct 07 2022

T(n,k) is the number of length n+1 bit strings beginning and ending with 0 having k length 2 substrings 00. This is equivalent to the compositions interpretation because each m part corresponds to a length m+1 bit string beginning with 0 and ending with the next 0 bit. Thus a substring 00 corresponds to a 1 part. Example: T(4,2)=3 because we have 00010 for 112, 00100 for 121 and 01000 for 211. - Michael Somos, Sep 24 2024

In the Baccherini et al. 2008 link on page 81: "Bloom[3] studies the number of singles in all the 2^n n-length bit strings, where a single is any isolated 1 or 0, i.e., any run of length 1. Let R_{n,k} be the number of n-length bit strings beginning with 0 and having k singles." Here T(n,k) = R_{n,k}. This combinatorial interpretation is equivalent to my previous comment since a part of size k corresponds to run of k identical bits and also to a length k+1 bit string with 0s only at the beginning and end. - Michael Somos, Sep 25 2024

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)

For n>2 note that (n+1)|a(n) unless n is prime, in which case (n+1)|2*a(n). This sequence is not the better-known generalized Lucas numbers V(n,a,b) defined for fixed integers a and b such that D = a^2 + 4*b is nonnegative, V(0) = 2, V(1) = a and for n>1 the recurrence V(n) = V(n-1) + V(n-2). The a = b = 1 case gives the Lucas Numbers. - Jonathan Vos Post, Mar 16 2005

Number of circular binary words of length n+1 having exactly two occurrences of 00. Example: a(4) = 5 because we have 00011, 10001, 11000, 00110 and 01100. Column 2 of A119458. - Emeric Deutsch, May 20 2006

From Petros Hadjicostas, Jan 10 2019: (Start)

In view of the comment by Emeric Deutsch above, we clarify the previous comment by Jonathan Vos Post. We have that 25 + 1 = 26 does not divide a(25) = 2964325 even though n = 25 is not a prime. What he probably meant is that, for n >= 1, we have (n+1) | a(n) unless n is odd, in which case (n+1)|2*a(n). (Of course, for some odd numbers n, we do have (n+1)|a(n), but not for all of them.)

From Emeric Deutsch's comment above, we have a(n) = A119458(n+1, k=2), while from the theory of marked and unmarked circular words, we have A320341(n+1, k=2) = (1/(n+1))*Sum_{d|gcd(n+1, 2)} phi(d)*A119458((n+1)/d, 2/d).

If n is even, then n+1 is odd, and hence A320341(n+1, k=2) = (1/(n+1)) * A119458(n+1, 2) = a(n)/(n+1), i.e., (n+1)|a(n).

If n=1, then (1+1)|2*a(1). Let n be odd >= 3, in which case n+1 is even and 2*A320341(n+1, k=2) = (1/(n+1))*(2*A119458(n+1, k=2) + 2*A119458((n+1)/2, k=1)). Thus, 2*A320341(n+1, k=2) = (1/(n+1))*(2*a(n) + 2*A006490((n+1)/2)) = (1/(n+1))*(2*a(n) + 2*((n+1)/2)*Fibonacci((n-3)/2)). It follows that 2*A320341(n+1, k=2) = 2*a(n)/(n+1) + Fibonacci((n-3)/2). Thus, 2*a(n)/(n+1) = 2*A320341(n+1, k=2) - Fibonacci((n-3)/2), and thus, (n+1)|2*a(n). (End)