A344004 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,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).

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

EXAMPLE

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}.

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

CROSSREFS

Cf. A000045, A052952, A129696.

Column k=3 of A345123.

Sequence in context: A002626 A339011 A029859 * A305105 A163312 A131253