%I #46 Oct 21 2022 22:04:07
%S 1,3,6,11,19,31,49,76,116,175,262,390,578,854,1259,1853,2724,4001,
%T 5873,8617,12639,18534,27174,39837,58396,85596,125460,183884,269509,
%U 394999,578914,848455,1243487,1822435,2670925,3914448,5736920,8407883
%N 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.
%C 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.
%C Partial sums of A077868. - _Paul Barry_, Sep 16 2004
%D Chu, Hung Viet. "Various Sequences from Counting Subsets." Fib. Quart., 59:2 (May 2021), 150-157.
%H G. C. Greubel, <a href="/A050228/b050228.txt">Table of n, a(n) for n = 1..1000</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 Z. Kasa, <a href="http://arxiv.org/abs/1104.4425">On scattered subword complexity</a>, arXiv preprint arXiv:1104.4425 [cs.DM], 2011.
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (3,-3,2,-2,1).
%F From _Paul Barry_, Sep 16 2004: (Start)
%F G.f.: x/((1-x)^3 - x^3(1-x)^2).
%F a(n) = 3*a(n-1) - 3*a(n-2) + 2*a(n-3) - 2*a(n-4) + a(n-5).
%F a(n-1) = Sum_{k=0..floor(n/3)} binomial(n-2*k, k+2). (End)
%F G.f. = 1/((1-x)^2*(1-x-x^3)). - _N. J. A. Sloane_, Jun 02 2021
%F a(n) = A000930(n+5) - n - 4. - _Greg Dresden_, Jun 20 2021
%F From _G. C. Greubel_, Jul 27 2022: (Start)
%F a(n) = Sum_{j=0..floor((n+1)/3)} binomial(n-2*j+1, j+2).
%F a(n) = A099567(n+1, 2). (End)
%p 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
%t Rest[CoefficientList[Series[1/((1-x)^2*(1-x-x^3)), {x, 0, 50}], x]] (* _G. C. Greubel_, Apr 27 2017 *)
%t LinearRecurrence[{3,-3,2,-2,1},{1,3,6,11,19},50] (* _Harvey P. Dale_, Apr 21 2020 *)
%o (PARI) my(x='x+O('x^50)); Vec(x/((1-x)^3-x^3*(1-x)^2)) \\ _G. C. Greubel_, Apr 27 2017
%o (Magma)
%o A050228:= func< n | n eq 0 select 0 else (&+[Binomial(n-2*j+1, j+2): j in [0..Floor((n+1)/3)]]) >;
%o [A050228(n): n in [1..40]]; // _G. C. Greubel_, Jul 27 2022
%o (SageMath)
%o def A050228(n): return sum(binomial(n-2*j+1, j+2) for j in (0..((n+1)//3)))
%o [A050228(n) for n in (1..40)] # _G. C. Greubel_, Jul 27 2022
%Y Cf. A000930, A077868, A144898, A144899, A144900, A144901, A144902, A144903, A144904, A226405.
%Y Cf. A078012, A099567, A135851.
%K nonn,easy
%O 1,2
%A _John W. Layman_, Dec 20 1999