A345123 -id:A345123 - cp's OEIS frontend

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

1, 3, 7, 17, 43, 106, 273, 678, 1759, 4389, 11430, 28614, 74685, 187433, 489926, 1231957, 3223387, 8118434, 21256897, 53609282, 140442534, 354595210, 929326086, 2348710733, 6157476873, 15575365846, 40843347873, 103392210473, 271181242774, 686944588009

Offset: 0

Alois P. Heinz, Jun 10 2021

nonn

			a(3) = 17: [1,2,3], [1,2,5], [1,4,5], [2,3,4], [2,3,6], [2,5,6], [3,4,5], [4,5,6], [1,2,3,4], [1,2,3,6], [1,2,5,6], [1,4,5,6], [2,3,4,5], [3,4,5,6], [1,2,3,4,5], [2,3,4,5,6], [1,2,3,4,5,6].

Alois P. Heinz, Table of n, a(n) for n = 0..2413

Cf. A345123.

g:= proc(n, k) option remember; `if`(k>n, 0,
     `if`(k in [0, 1], n^k, g(n-1, k-1)+g(n-2, k)))
    end:
b:= proc(n, k) option remember;
     `if`(k>n, 0, g(n, k)+b(n, k+1))
    end:
a:= n-> b(2*n, n):
seq(a(n), n=0..30);

g[n_, k_] := g[n, k] = Which[k > n, 0, k == 0, 1, k == 1, n,
     True, g[n - 1, k - 1] + g[n - 2, k]];
b[n_, k_] := b[n, k] = If[k > n, 0, g[n, k] + b[n, k + 1]];
a[n_] := b[2*n, n];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, May 29 2022, after Alois P. Heinz *)

a(n) = A345123(2n,n).

a(n) ~ c * (27/4)^(n/2) / sqrt(3*Pi*n/2), where c = 14 if n is even and c = 8*sqrt(3) if n is odd. Equivalently, c = 7 + 4*sqrt(3) + (7 - 4*sqrt(3))*(-1)^n. - Vaclav Kotesovec, Jun 19 2021

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

Original entry on oeis.org

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

N. J. A. Sloane, Jun 02 2021

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

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

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

Cf. A000045, A052952, A129696.

Column k=3 of A345123.

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

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 *)

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

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

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula