cp's OEIS Frontend

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

%I A344004 #40 Mar 28 2025 16:12:49
%S A344004 0,0,1,3,8,17,34,63,113,196,334,560,930,1532,2511,4099,6674,10845,
%T A344004 17600,28535,46235,74880,121236,196248,317628,514032,831829,1346043,
%U A344004 2178068,3524321,5702614,9227175,14930045,24157492,39087826,63245624,102333774,165579740
%N A344004 Number of ordered subsequences of {1,...,n} containing at least three elements and such that the first differences contain only odd numbers.
%D A344004 Chu, Hung Viet. "Various Sequences from Counting Subsets." Fib. Quart., 59:2 (May 2021), 150-157.
%H A344004 Alois P. Heinz, <a href="/A344004/b344004.txt">Table of n, a(n) for n = 1..2000</a>
%H A344004 Hung Viet Chu, <a href="https://arxiv.org/abs/2005.10081">Various sequences from counting subsets</a>, arXiv:2005.10081 [math.CO], 2020-2021.
%H A344004 <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1,-4,3,1,-1).
%F A344004 G.f.: x^3/((x-1)^3*(x+1)*(x^2+x-1)). - _Alois P. Heinz_, Jun 02 2021
%F A344004 Comment from _N. J. A. Sloane_, Jun 03 2021. (Start)
%F A344004 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).
%F A344004 Proof: We will not give a complete proof, but we will do enough, we hope, to convince the reader.
%F A344004 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.
%F A344004 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).
%F A344004 We obtain a recurrence for b(n) as follows.
%F A344004 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.
%F A344004 So, setting r = 2*i+1, we have shown that b(n) satisfies the recurrence
%F A344004 b(n) = Sum_{i = 0..(floor(n/2)-1)} (b(n-(2*i+1)) + floor((n-(2*i+1))/2)),
%F A344004 with initial conditions b(1)=b(2)=0, b(3)=1.
%F A344004 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)
%F A344004 a(n) = Fibonacci(n+3) - (1/8)(15 + 8*n + 2*n^2 + (-1)^n). - _Greg Dresden_, Jun 20 2021
%e A344004 For n = 3 there is just one subset, {1,2,3}, whose first differences, {1,1}, contain only odd numbers.
%e A344004 a(4) = 3 from {1,2,3}, {2,3,4}, {1,2,3,4}.
%p A344004 a:= n-> (<<0|1|0|0|0|0>, <0|0|1|0|0|0>, <0|0|0|1|0|0>,
%p A344004           <0|0|0|0|1|0>, <0|0|0|0|0|1>, <-1|1|3|-4|-1|3>>^n)[3, 6]:
%p A344004 seq(a(n), n=1..38);  # _Alois P. Heinz_, Jun 02 2021
%t A344004 A344004[n_] := Fibonacci[n+3] - (2*n*(n+4) + (-1)^n + 15)/8; Array[A344004, 50] (* or *)
%t A344004 LinearRecurrence[{3, -1, -4, 3, 1, -1}, {0, 0, 1, 3, 8, 17}, 50] (* _Paolo Xausa_, Mar 28 2025 *)
%Y A344004 Cf. A000045, A052952, A129696.
%Y A344004 Column k=3 of A345123.
%K A344004 nonn,easy
%O A344004 1,4
%A A344004 _N. J. A. Sloane_, Jun 02 2021
%E A344004 a(13)-a(38) from _Alois P. Heinz_, Jun 02 2021