cp's OEIS Frontend

Number of no-leaf edge-subgraphs in Moebius ladder M_n.

Number of (s(0), s(1), ..., s(2n)) such that 0 < s(i) < 10 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n, s(0) = 3, s(2n) = 5.

With offset 0 = INVERT transform of A001792: (1, 3, 8, 20, 48, 112, ...). - Gary W. Adamson, Oct 26 2010

From Tom Copeland, Nov 09 2014: (Start)

The array belongs to a family of arrays associated to the Catalan A000108 (t=1), and Riordan, or Motzkin sums A005043 (t=0), with the o.g.f. (1-sqrt(1-4x/(1+(1-t)x)))/2 and inverse x*(1-x)/(1 + (t-1)*x*(1-x)). See A091867 for more info on this family. Here t = -4 (mod signs in the results).

Let C(x) = (1 - sqrt(1-4x))/2, an o.g.f. for the Catalan numbers A000108, with inverse Cinv(x) = x*(1-x) and P(x,t) = x/(1+t*x) with inverse P(x,-t).

O.g.f.: G(x) = x*(1-x)/(1 - 5x*(1-x)) = P(Cinv(x),-5).

Inverse O.g.f.: Ginv(x) = (1 - sqrt(1 - 4*x/(1+5x)))/2 = C(P(x,5)) (signed A026378). Cf. A030528. (End)

p-INVERT of (2^n), where p(s) = 1 - s - s^2; see A289780. - Clark Kimberling, Aug 10 2017

Define {x(k)} to be an integer sequence satisfying all the following conditions:

(i) {x(k)} satisfies second-order linear recursion, that is, there exists two integers P, Q such that x(k+2) = P*x(k+1) + Q*x(k) holds for all k >= 0.

(ii) {x(k)} is (not necessarily strictly) increasing. ({A000035(k)} satisfies condition (i), but it doesn't satisfy this.)

(iii) All terms in {x(k)} do not share a common factor. ({A024023(k)} satisfies both conditions (i) and (ii), but all terms share a common factor 2.)

(iv) {x(k)} satisfies strong divisibility, that is, gcd(x(m),x(n)) = x(gcd(m,n)) holds for all m, n >= 0. ({A093131(k)} satisfies all conditions (i) to (iii), but 5 = gcd(A093131(2),A093131(3)) != A093131(gcd(2,3)) = 1.)

(v) For all positive integers n, there eventually exists some m > 0 such that n divides x(m). ({A002275(k)} satisfies all conditions (i) to (iv), but 2, 5 and 10 never divide any term.)

Then it's easy to show that the only solutions to {x(k)} are x(k) = A172236(n,k) or x(k) = T(n,k), i.e., x(0) = 0, x(1) = 1, P >= 1, Q = 1 or P >= 2, Q = -1.

The case n = 0 is not included since it gives the period-4 signed sequence 0, 1, 0, -1, 0, 1, 0, -1, ..., the g.f. of which is the inverse of the 4th cyclotomic polynomial.

The case n = 1 is not included since it gives the period-6 signed sequence 0, 1, 1, 0, -1, -1, ..., the g.f. of which is the inverse of the 6th cyclotomic polynomial.

The congruence property: let p be an odd prime which is not divisible by n^2 - 4, then T(n,(p-1)/2) == 1/2(((n-2)/p) - ((n+2)/p)) (mod p), T(n,(p+1)/2) == 1/2(((n-2)/p) + ((n+2)/p)) (mod p). Here ((n-2)/p) is the Legendre symbol. Or equivalently:

((n-2)/p)...((n+2)/p)...T(n,(p-1)/2) mod p...T(n,(p+1)/2) mod p

.....1...........1...............0....................1

....-1..........-1...............0...................-1

.....1..........-1...............1....................0

....-1...........1..............-1....................0

To prove this, rewrite (n +- sqrt(n^2-4))/2 as ((sqrt(n+2) +- sqrt(n-2))/2)^2.

Let E(n,m) be the smallest number l such that m divides T(n,l), we have: E(n,p) divides (p - ((n^2-4)/p))/2 for odd primes p that are not divisible by n^2 - 4. E(n,p) = p for odd primes p that are divisible by n^2 - 4. E(n,2) = 2 for even n and 3 for odd n.

E(n,p^e) <= p^(e-1)*E(n,p) for all primes p. If p^2 does not divide T(n,E(n,p)), then E(n,p^e) = p^(e-1)*E(n,p) for all exponent e. Specially, for primes p >= 5 that are divisible by n^2 - 4, p^2 is never divisible by T(n,p), so E(n,p^e) = p^e as described above. E(n,m_1*m_2) = lcm(E(n,m_1),E(n,m_2)) if gcd(m_1,m_2) = 1.

Given n, the largest possible value of E(n,m)/m is 1 for even n and 3/2 for odd n. It can be obtained by the value of E(n,2) described above.

Let pi(n,m) be the Pisano period of T(n,k) modulo m, i.e, the smallest number l such that T(n,k+1) == T(n,k) (mod m) holds for all k >= 0, we have: for odd primes p that are not divisible by n^2 - 4, pi(n,p) divides p + ((n-2)/p) if ((n+2)/p) = -1 and (p - ((n-2)/p))/2 if ((n+2)/p) = 1. pi(n,p) = p for odd primes p that are divisible by n - 2 and 2p for odd primes p that are divisible by n + 2. pi(n,2) = 2 even n and 3 for odd n.

pi(n,p^e) <= p^(e-1)*pi(n,p) for all primes p. If p^2 does not divide T(n,E(n,p)), then pi(n,p^e) = p^(e-1)*pi(n,p) for all exponent e. Specially, for primes p >= 5 that are divisible by n^2 - 4, p^2 is never divisible by T(n,p), so pi(n,p^e) = p^e or 2p^e as described above. pi(n,m_1*m_2) = lcm(pi(n,m_1),pi(n,m_2)) if gcd(m_1,m_2) = 1.

Given n, the largest possible value of pi(n,m)/m is:

Parity of n...n + 2 is a power of 2 or 3...max{pi(n,m)/m}.....obtained by

....even..........yes (even exponent)............1...........pi(n,2^e) = 2^e

....even...........yes (odd exponent)...........4/3............pi(n,3) = 4

....even...................no....................2.............pi(n,p) = 2p (p >= 3 is any prime factor of n + 2)

.....odd..................yes....................2..........pi(n,3^e) = 2*3^e

.....odd...................no....................3..........pi(n,2p^e) = 6p^e (p >= 5 is any prime factor of n + 2)

The largest possible value of pi(n,m)/m is obtained by infinitely many m except for the case n = 10, in which we have pi(10,3) = 6, pi(10,7) = 8, pi(10,21) = 24 and pi(10,m)/m <= 14/13 for all other m. [Corrected by Jianing Song, Nov 04 2018]

Let z(n,m) be the number of zeros in a period of T(n,k) modulo m, i.e., z(n,m) = pi(n,m)/E(n,m), then we have: for odd primes p that are not divisible by n^2 - 4, z(n,p) = 2 if ((n+2)/p) = -1; 1 or 2 if ((n+2)/p) = 1. z(n,p) = 1 for odd primes p that are divisible by n - 2 and 2 for odd primes p that are divisible by n + 2. z(n,2) = 1.

For all odd primes p, z(n,p) = 2 if and only if pi(n,p) is even, z(n,p) = 1 if and only if pi(n,p) is odd. For all odd primes p, if E(n,p) is even then z(n,p) = 2 (the converse is not necessarily true). [Comment revised by Jianing Song, Jul 06 2019]

z(n,p^e) = z(n,p) for all odd primes p. z(n,4) = 1 if n == 2, 3 (mod 4) and 2 if n == 0, 1 (mod 4). z(n,2^e) = 1 for even n and 2 for odd n, e >= 3.

By induction it is easy to show that T(n,k) = T(n,m+1)*T(n,k-m) - T(n,m)*T(k-m-1). Let k = 2m we have T(n,2m) = T(n,m)*(T(n,m+1)-T(m-1)); let k = 2m+1 we have T(n,2m+1) = T(n,m+1)^2 - T(n,m)^2 = (T(n,m+1)+T(n,m))*(T(n,m+1)-T(n,m)). So T(n,k) is composite if n >= 3, k >= 3. - Jianing Song, Jul 06 2019

Row n >= 0 of the array gives the solution to the recurrence b(k) = 5*b(k-1) + (n - 6)*b(k-2) for k >= 2 with b(0) = 0 and b(1) = 1. The rows are the binomial transforms of the rows of array A083857. The rows are the second binomial transforms of the generalized Fibonacci numbers in array A083856.

Diagonal sums : A112576.

Essentially the same as A094440. - Peter Bala, Jan 06 2015