A052952 -id:A052952 - 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.

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

A131256 A000012(signed) * A052509.

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 0, 2, 1, 1, 1, 2, 3, 1, 1, 0, 3, 4, 3, 1, 1, 1, 3, 7, 5, 3, 1, 1, 0, 4, 9, 10, 5, 3, 1, 11, 4, 13, 16, 11, 5, 3, 1, 1, 0, 5, 16, 26, 20, 11, 5, 3, 1, 1

Offset: 0

Gary W. Adamson, Jun 23 2007

Row sums = A052952: (1, 1, 3, 4, 8, 12, 21, 33, ...). A131257 = A052509 * A000012(signed).

			First few rows of the triangle:
  1;
  0, 1;
  1, 1, 1;
  0, 2, 1, 1;
  1, 2, 3, 1, 1;
  0, 3, 4, 3, 1, 1;
  1, 3, 7, 5, 3, 1, 1;
  ...

Cf. A052509, A000012, A131257.

A000012(signed) * A052509, where the signed version of A000012 = (1; -1,1; 1,-1,1; ...).

A372242 a(n) = 10*Fibonacci(n) + (-1)^n.

Original entry on oeis.org

1, 9, 11, 19, 31, 49, 81, 129, 211, 339, 551, 889, 1441, 2329, 3771, 6099, 9871, 15969, 25841, 41809, 67651, 109459, 177111, 286569, 463681, 750249, 1213931, 1964179, 3178111, 5142289, 8320401, 13462689, 21783091, 35245779, 57028871, 92274649, 149303521, 241578169

Offset: 0

Paul Curtz, Apr 23 2024

			a(0) = 10*0 + 1 =  1,
a(1) = 10*1 - 1 =  9,
a(2) = 10*1 + 1 = 11,
a(3) = 10*2 - 1 = 19.

Paolo Xausa, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (0,2,1).

Cf. A000045, A022093, A153382, A052952, A371843.

Cf. A000032, A022112, A280154.

LinearRecurrence[{0, 2, 1}, {1, 9, 11}, 50] (* Paolo Xausa, May 20 2024 *)

Floor(a(n+2)/10) = A052952(n).
a(n) = 1 + A153382(n).
a(n) = 2*A371843(n) - (-1)^n.
a(n) = A022093(n) + (-1)^n.
G.f.: -(9*x^2+9*x+1)/((x+1)*(x^2+x-1)).
a(0) = 1. a(n) = -a(n-1) + 10*A000045(n+1) for n >= 1.
a(n) = a(n-4) + (2*A280154(n-2) = 5*A022112(n-3) = 10*A000032(n-2)) for n >= 4.

A129712 Triangle read by rows: T(n,k) is the number of Fibonacci binary words of length n and starting with exactly k 10's (0<=k<=floor(n/2)). A Fibonacci binary word is a binary word having no 00 subword.

Original entry on oeis.org

1, 2, 2, 1, 4, 1, 6, 1, 1, 10, 2, 1, 16, 3, 1, 1, 26, 5, 2, 1, 42, 8, 3, 1, 1, 68, 13, 5, 2, 1, 110, 21, 8, 3, 1, 1, 178, 34, 13, 5, 2, 1, 288, 55, 21, 8, 3, 1, 1, 466, 89, 34, 13, 5, 2, 1, 754, 144, 55, 21, 8, 3, 1, 1, 1220, 233, 89, 34, 13, 5, 2, 1, 1974, 377, 144, 55, 21, 8, 3, 1, 1

Offset: 0

Emeric Deutsch, May 12 2007

Row n has 1+floor(n/2) terms. Row sums are the Fibonacci numbers (A000045). Sum(k*T(n,k), k>=0)=A052952(n-2) (n>=2).

			T(7,2)=2 because we have 1010110 and 1010111.
Triangle starts:
1;
2;
2,1;
4,1;
6,1,1;
10,2,1;
16,3,1,1;
26,5,2,1;

Cf. A000045, A052952.

with(combinat): T:=proc(n,k) if k=0 and n=0 then 1 elif k=0 then 2*fibonacci(n) elif n=2*k or n=2*k+1 then 1 elif n>2*k+1 then fibonacci(n-2*k) else 0 fi end: for n from 0 to 18 do seq(T(n,k),k=0..floor(n/2)) od;

T(0,0)=1, T(n,0)=2F(n) for n>=1, T(2k,k)=T(2k+1,k)=1 for k>=1, T(n,k)=F(n-2k) for 1<=k<(n-1)/2. G.f.=G(t,z)=(1+z-z^2-t*z^3)/[(1-z-z^2)(1-t*z^2)].

A177040 Irregular triangle t(n,m) = binomial(m+1,n-m) read by rows floor((n+1)/2) <= m <= n.

Original entry on oeis.org

1, 1, 2, 1, 3, 1, 3, 4, 1, 6, 5, 1, 4, 10, 6, 1, 10, 15, 7, 1, 5, 20, 21, 8, 1, 15, 35, 28, 9, 1, 6, 35, 56, 36, 10, 1, 21, 70, 84, 45, 11, 1, 7, 56, 126, 120, 55, 12, 1, 28, 126, 210, 165, 66, 13, 1, 8, 84, 252, 330, 220, 78, 14, 1, 36, 210, 462, 495, 286, 91, 15, 1

Offset: 0

Roger L. Bagula, May 01 2010

Row sums are in A052952.

Contains the right half of each row of A030528. - R. J. Mathar, May 19 2013

			1;
1;
2, 1;
3, 1;
3, 4, 1;
6, 5, 1;
4, 10, 6, 1;
10, 15, 7, 1;
5, 20, 21, 8, 1;
15, 35, 28, 9, 1;
6, 35, 56, 36, 10, 1;
21, 70, 84, 45, 11, 1;
7, 56, 126, 120, 55, 12, 1;
28, 126, 210, 165, 66, 13, 1;
8, 84, 252, 330, 220, 78, 14, 1;
36, 210, 462, 495, 286, 91, 15, 1;

Cf. A180987 (read diagonally downwards), A098925, A026729, A085478, A165253

t[n_, m_] := Binomial[m + 1, n - m];
Table[Table[t[n, m], {m, Floor[(n + 1)/2], n}], {n, 0, 15}];
Flatten[%]

T(m,n)=binomial(n+1,m-n) \\ Charles R Greathouse IV, May 19 2013

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.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A131256 A000012(signed) * A052509.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A372242 a(n) = 10*Fibonacci(n) + (-1)^n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A129712 Triangle read by rows: T(n,k) is the number of Fibonacci binary words of length n and starting with exactly k 10's (0<=k<=floor(n/2)). A Fibonacci binary word is a binary word having no 00 subword.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

A177040 Irregular triangle t(n,m) = binomial(m+1,n-m) read by rows floor((n+1)/2) <= m <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI