login
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.
10

%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