A344004 Number of ordered subsequences of {1,...,n} containing at least three elements and such that the first differences contain only odd numbers.

0, 0, 1, 3, 8, 17, 34, 63, 113, 196, 334, 560, 930, 1532, 2511, 4099, 6674, 10845, 17600, 28535, 46235, 74880, 121236, 196248, 317628, 514032, 831829, 1346043, 2178068, 3524321, 5702614, 9227175, 14930045, 24157492, 39087826, 63245624, 102333774, 165579740

Offset: 1

Author

N. J. A. Sloane, Jun 02 2021

Keywords

• nonn
• easy

Examples

			For n = 3 there is just one subset, {1,2,3}, whose first differences, {1,1}, contain only odd numbers.
a(4) = 3 from {1,2,3}, {2,3,4}, {1,2,3,4}.
		

References

• Chu, Hung Viet. "Various Sequences from Counting Subsets." Fib. Quart., 59:2 (May 2021), 150-157.

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..2000
• Hung Viet Chu, Various sequences from counting subsets, arXiv:2005.10081 [math.CO], 2020-2021.
• Index entries for linear recurrences with constant coefficients, signature (3,-1,-4,3,1,-1).

Crossrefs

Cf. A000045, A052952, A129696.

Column k=3 of A345123.

Programs

Maple

a:= n-> (<<0|1|0|0|0|0>, <0|0|1|0|0|0>, <0|0|0|1|0|0>,
          <0|0|0|0|1|0>, <0|0|0|0|0|1>, <-1|1|3|-4|-1|3>>^n)[3, 6]:
seq(a(n), n=1..38);  # Alois P. Heinz, Jun 02 2021

Mathematica

A344004[n_] := Fibonacci[n+3] - (2*n*(n+4) + (-1)^n + 15)/8; Array[A344004, 50] (* or *)
LinearRecurrence[{3, -1, -4, 3, 1, -1}, {0, 0, 1, 3, 8, 17}, 50] (* Paolo Xausa, Mar 28 2025 *)

Formula

G.f.: x^3/((x-1)^3*(x+1)*(x^2+x-1)). - Alois P. Heinz, Jun 02 2021

Comment from N. J. A. Sloane, Jun 03 2021. (Start)

Theorem: This sequence has g.f. G_1(x) = x^3/((1-x)^3*(1+x)*(1-x-x^2)) = x^3/(1-2*x-x^2+3*x^3-x^5), which implies a linear recurrence with constant coefficients and signature (3,-1,-4,3,1,-1).

Proof: We will not give a complete proof, but we will do enough, we hope, to convince the reader.

Let b(n) be the number of ordered subsequences S of {1,...,n} containing at least three elements, such that the first differences contain only odd numbers, and in which the largest term is n.

Then the a(n) are the partial sums of the b(n), and we claim that b(n) has generating function (1-x)*G_1(x).

We obtain a recurrence for b(n) as follows.

If we remove n from the subsequence S, there are two possibilities. Either we obtain a subsequence of {1,...,n-i} with largest term n-r (r odd) containing at least three elements, or we obtain a pair j, n-r with r and n-r-j odd. In this case j can be chosen in floor((n-r)/2) ways.

So, setting r = 2*i+1, we have shown that b(n) satisfies the recurrence

b(n) = Sum_{i = 0..(floor(n/2)-1)} (b(n-(2*i+1)) + floor((n-(2*i+1))/2)),

with initial conditions b(1)=b(2)=0, b(3)=1.

It turns out that b(n) is a fairly well-known sequence, A129696, whose generating function is known to equal (1-x)*G_1(x), and whose first differences (A052952) are essentially the Fibonacci numbers F_k with 1 subtracted if k is even. (End)

a(n) = Fibonacci(n+3) - (1/8)(15 + 8*n + 2*n^2 + (-1)^n). - Greg Dresden, Jun 20 2021

Extensions

a(13)-a(38) from Alois P. Heinz, Jun 02 2021