A050228 a(n) is the number of subsequences {s(k)} of {1,2,3,...n} such that s(k+1)-s(k) is 1 or 3.

1, 3, 6, 11, 19, 31, 49, 76, 116, 175, 262, 390, 578, 854, 1259, 1853, 2724, 4001, 5873, 8617, 12639, 18534, 27174, 39837, 58396, 85596, 125460, 183884, 269509, 394999, 578914, 848455, 1243487, 1822435, 2670925, 3914448, 5736920, 8407883

Offset

1,2

Comments

The second differences c(n) of {a(n)} satisfy c(n)=c(n-1)+c(n-3) and give A000930 with the first 5 terms deleted.

Partial sums of A077868. - Paul Barry, Sep 16 2004

References

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

Links

G. C. Greubel, Table of n, a(n) for n = 1..1000

Hung Viet Chu, Various sequences from counting subsets, arXiv:2005.10081 [math.CO], 2020-2021.

Z. Kasa, On scattered subword complexity, arXiv preprint arXiv:1104.4425 [cs.DM], 2011.

Index entries for linear recurrences with constant coefficients, signature (3,-3,2,-2,1).

Formula

From Paul Barry, Sep 16 2004: (Start)

G.f.: x/((1-x)^3 - x^3(1-x)^2).

a(n) = 3*a(n-1) - 3*a(n-2) + 2*a(n-3) - 2*a(n-4) + a(n-5).

a(n-1) = Sum_{k=0..floor(n/3)} binomial(n-2*k, k+2). (End)

G.f. = 1/((1-x)^2*(1-x-x^3)). - N. J. A. Sloane, Jun 02 2021

a(n) = A000930(n+5) - n - 4. - Greg Dresden, Jun 20 2021

From G. C. Greubel, Jul 27 2022: (Start)

a(n) = Sum_{j=0..floor((n+1)/3)} binomial(n-2*j+1, j+2).

a(n) = A099567(n+1, 2). (End)

Maple

with(combstruct): SubSetSeqU := [T, {T=Subst(U, U), S=Set(U, card>=3), U=Sequence(Z, card>=3)}, unlabeled]: seq(count(SubSetSeqU, size=n), n=9..46); # Zerinvary Lajos, Mar 18 2008

Mathematica

Rest[CoefficientList[Series[1/((1-x)^2*(1-x-x^3)), {x, 0, 50}], x]] (* G. C. Greubel, Apr 27 2017 *)
LinearRecurrence[{3, -3, 2, -2, 1}, {1, 3, 6, 11, 19}, 50] (* Harvey P. Dale, Apr 21 2020 *)

Prog

(PARI) my(x='x+O('x^50)); Vec(x/((1-x)^3-x^3*(1-x)^2)) \\ G. C. Greubel, Apr 27 2017
(Magma)
A050228:= func< n | n eq 0 select 0 else (&+[Binomial(n-2*j+1, j+2): j in [0..Floor((n+1)/3)]]) >;
[A050228(n): n in [1..40]]; // G. C. Greubel, Jul 27 2022
(SageMath)
def A050228(n): return sum(binomial(n-2*j+1, j+2) for j in (0..((n+1)//3)))
[A050228(n) for n in (1..40)] # G. C. Greubel, Jul 27 2022

Crossrefs

Cf. A000930, A077868, A144898, A144899, A144900, A144901, A144902, A144903, A144904, A226405.

Cf. A078012, A099567, A135851.

Sequence in context: A004133 A180415 A344003 * A114089 A001976 A144115

Adjacent sequences: A050225 A050226 A050227 * A050229 A050230 A050231

Keyword

nonn,easy

Author

John W. Layman, Dec 20 1999

Status

approved