cp's OEIS Frontend

Number of states in the planning domain FERRY, when n-3 cars are at one of two shores while the (n-2)nd car may be on the ferry or at one of the shores.

If the ferry could board any number of cars (instead of only one), the number of states would form the Pisot sequence P(2,6) (A008776). In addition, if k shores existed, the sequence would form the Pisot sequence P(k,k(k+1)). This corresponds to the BRIEFCASE planning domain.

a(i) is the number of occurrences of the number 1 in all palindromic compositions of n = 2*(i+1). - Silvia Heubach (sheubac(AT)calstatela.edu), Jan 10 2003. E.g., there are 5 palindromic compositions of 6, namely 111111 11211 2112 1221 141, containing a total of 16 1's.

Number of occurrences of 00's in all circular binary words of length n. Example: a(3)=6 because in the circular binary words 000, 001, 010, 011, 100, 101, 110 and 111 we have a total of 3+1+1+0+1+0+0+0=6 occurrences of 00. a(n) = Sum_{k=0..n} k*A119458(n,k). - Emeric Deutsch, May 20 2006

a(n) is the number of permutations on [n] for which the entries of each left factor form a circular subinterval of [n]. A subset I of [n] forms a circular subinterval of [n] if it is an ordinary interval [a,b] or has the form [1,a]-union-[b,n] for 1 <= a < b <= n. For example, (5,4,2) is a left factor of the permutation (5,4,2,1,3) which does not form a circular subinterval of [5] and a(4)=16 counts all 24 permutations of [4] except the eight whose first two entries are 1,3 (in either order) or 2,4. - David Callan, Mar 30 2007

a(n) is the total number of runs in all Boolean (n-1)-strings. For example, the 8 Boolean 3-strings, 000, 001, 010, 011, 100, 101, 110, 111 have 1, 2, 3, 2, 2, 3, 2, 1 runs respectively. - David Callan, Jul 22 2008

From Gary W. Adamson, Jul 31 2010: (Start)

Starting with "1" = (1, 2, 4, 8, ...) convolved with (1, 0, 2, 4, 8, ...).

Example: a(6) = 96 = (32, 16, 8, 4, 2, 1) dot (1, 0, 2, 4, 8, 16) = (32 + 0 + 16 + 16 + 16, + 16) = 32 + 4*16 (End)

An elephant sequence, see A175654. For the corner squares 24 A[5] vectors, with decimal values between 27 and 432, lead to this sequence (without the leading 0). For the central square these vectors lead to the companion sequence A087447 (without the first leading 1). - Johannes W. Meijer, Aug 15 2010

Starting with 1 = (1, 1, 2, 4, 8, 16, ...) convolved with (1, 1, 3, 7, 15, 31, ...). - Gary W. Adamson, Oct 26 2010

a(n) is the number of ways to draw simple polygonal chains for n vertices lying on a circle. - Anton Zakharov, Dec 31 2016

Also the number of edges, maximal cliques, and maximum cliques in the n-folded cube graph for n > 3. - Eric W. Weisstein, Dec 01 2017 and Mar 21 2018

Number of pairs of compositions of n corresponding to a seaweed algebra of index n-2 for n > 2. - Nick Mayers, Jun 25 2018

Starting with 1, 2, 6, 16, ..., 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

Number of circular binary words of length n having exactly one occurrence of 00. Example: a(5)=10 because we have 00111, 10011, 11001, 11100, 01110, 00101, 10010, 01001, 10100 and 01010. Column 1 of A119458. - Emeric Deutsch, May 20 2006

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.

T(i,n) is the number of necklace compositions with sum n and parts at most i. For example, the T(3,5) = 5 compositions up to cyclic equivalence are 11111, 1112, 113, 122, 23. - Andrew Howroyd, Jan 08 2024

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)