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

%I #32 Jun 21 2021 06:04:06

%S 0,0,1,3,8,17,34,63,113,196,334,560,930,1532,2511,4099,6674,10845,

%T 17600,28535,46235,74880,121236,196248,317628,514032,831829,1346043,

%U 2178068,3524321,5702614,9227175,14930045,24157492,39087826,63245624,102333774,165579740

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

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

%H Alois P. Heinz, <a href="/A344004/b344004.txt">Table of n, a(n) for n = 1..2000</a>

%H 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 <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1,-4,3,1,-1).

%F G.f.: x^3/((x-1)^3*(x+1)*(x^2+x-1)). - _Alois P. Heinz_, Jun 02 2021

%F Comment from _N. J. A. Sloane_, Jun 03 2021. (Start)

%F 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 Proof: We will not give a complete proof, but we will do enough, we hope, to convince the reader.

%F 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 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 We obtain a recurrence for b(n) as follows.

%F 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 So, setting r = 2*i+1, we have shown that b(n) satisfies the recurrence

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

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

%F 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 a(n) = Fibonacci(n+3) - (1/8)(15 + 8*n + 2*n^2 + (-1)^n). - _Greg Dresden_, Jun 20 2021

%e For n = 3 there is just one subset, {1,2,3}, whose first differences, {1,1}, contain only odd numbers.

%e a(4) = 3 from {1,2,3}, {2,3,4}, {1,2,3,4}.

%p a:= n-> (<<0|1|0|0|0|0>, <0|0|1|0|0|0>, <0|0|0|1|0|0>,

%p <0|0|0|0|1|0>, <0|0|0|0|0|1>, <-1|1|3|-4|-1|3>>^n)[3, 6]:

%p seq(a(n), n=1..38); # _Alois P. Heinz_, Jun 02 2021

%Y Cf. A000045, A052952, A129696.

%Y Column k=3 of A345123.

%K nonn,easy

%O 1,4

%A _N. J. A. Sloane_, Jun 02 2021

%E a(13)-a(38) from _Alois P. Heinz_, Jun 02 2021