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

Author

John W. Layman, Dec 20 1999

Keywords

• nonn
• easy

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

Crossrefs

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

Cf. A078012, A099567, A135851.

Programs

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

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

PARI

my(x='x+O('x^50)); Vec(x/((1-x)^3-x^3*(1-x)^2)) \\ G. C. Greubel, Apr 27 2017

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

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)