|
%I #74 Jan 01 2024 13:35:55
%S 1,2,3,5,8,12,18,27,40,59,87,128,188,276,405,594,871,1277,1872,2744,
%T 4022,5895,8640,12663,18559,27200,39864,58424,85625,125490,183915,
%U 269541,395032,578948,848490,1243523,1822472,2670963,3914487,5736960,8407924,12322412
%N Expansion of 1/((1-x)*(1-x-x^3)).
%C Row sums of Riordan array (1/(1-x), x*(1+x^2)). - _Paul Barry_, Feb 16 2005
%C a(n) is the number of partitions of {1, ..., n+3} into two blocks in which only 1- or 3-strings of consecutive integers can appear in a block and there is at least one 3-string. E.g., a(3)=5 because the enumerated partitions of {1,2,3,4,5,6} are 1235/46, 1345/26, 15/2346, 13/2456, 123/456. - _Augustine O. Munagi_, Apr 11 2005
%D Chu, Hung Viet. "Various Sequences from Counting Subsets." Fib. Quart., 59:2 (May 2021), 150-157.
%H G. C. Greubel, <a href="/A077868/b077868.txt">Table of n, a(n) for n = 0..1000</a>
%H Kassie Archer and Aaron Geary, <a href="https://arxiv.org/abs/2312.14351">Powers of permutations that avoid chains of patterns</a>, arXiv:2312.14351 [math.CO], 2023. See p. 15.
%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 A. O. Munagi, <a href="http://www.emis.de/journals/HOA/IJMMS/2005/3451.pdf">Set Partitions with Successions and Separations</a>, IJMMS 2005:3 (2005), 451-463.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1,1,-1).
%F Partial sums of A000930. a(n-1) = Sum_{k=0..floor(n/2)} binomial(n-2*k, k+1). - _Paul Barry_, Jul 07 2004
%F a(n-3) = Sum(binomial(n-r, r)), r=1, 2, ... which is the case t=3 and k=2 in the general case of t-strings and k blocks: a(n-3, k, t) = Sum(binomial(n-r*(t-1), r)*S2(n-r*(t-1)-1, k-1)), r=1, 2, ... - _Augustine O. Munagi_, Apr 11 2005
%F From _Paul Weisenhorn_, Oct 28 2011: (Start)
%F a(n) = a(n-1) + a(n-2) - a(n-5) for n > 4.
%F a(n) = a(n-2) + a(n-3) + a(n-4) + 2 for n > 3.
%F G.f.: 1/((1-x)*(1-x-x^3)). (End)
%F a(n) = 1 + a(n-1) + a(n-3), a(1)=1, a(2)=2, a(3)=3. - _Gerry Martens_, Jun 10 2018
%F a(n) = -A077888(-4-n) for all n in Z. - _Michael Somos_, Jun 17 2018
%F a(n) = A000930(n+3) - 1. - _Greg Dresden_, Jun 20 2021
%F a(n) = A099567(n+3, 4). - _G. C. Greubel_, Jul 27 2022
%p a:= n-> (Matrix(4, (i,j)-> if i=j-1 then 1 elif j=1 then [2,-1,1,-1][i] else 0 fi)^n)[1,1]: seq(a(n), n=0..41); # _Alois P. Heinz_, Sep 05 2008
%p g:=(1+z+z^2)/(1-z-z^3): gser:=series(g, z=0, 43): seq(coeff(gser, z, n)-1, n=1..42); # _Zerinvary Lajos_, Jan 09 2009
%t LinearRecurrence[{1,1,0,0,-1}, {1,2,3,5,8,12}, 42] (* or *)
%t CoefficientList[Series[1/((1-x)(1-x-x^3)), {x, 0, 41}], x] (* _Michael De Vlieger_, Jun 06 2018 *)
%o (PARI) Vec(1/(1-x)/(1-x-x^3)+O(x^99)) \\ _Charles R Greathouse IV_, Sep 23 2012
%o (PARI) {a = vector(50);
%o a[1] = 1; a[2] = 2; a[3] = 3;
%o for(n=4,50,
%o a[n] = 1 + a[n-1] + a[n-3];
%o ); a} \\ _Gerry Martens_, Jun 03 2018
%o (PARI) {a(n) = if( n<0, n=-4-n; polcoeff( -1 / (1 - x) / (1 + x^2 - x^3) + x * O(x^n), n), polcoeff( 1 / (1 - x) / (1 - x - x^3) + x * O(x^n), n))}; /* _Michael Somos_, Jun 17 2018 */
%o (Magma)
%o A077868:= func< n | n eq 0 select 0 else (&+[Binomial(n-2*j+, j+1): j in [0..Floor((n+1)/3)]]) >;
%o [A077868(n): n in [0..40]]; // _G. C. Greubel_, Jul 27 2022
%o (SageMath)
%o def A077868(n): return sum(binomial(n-2*j+1, j+1) for j in (0..((n+1)//3)))
%o [A077868(n) for n in (0..40)] # _G. C. Greubel_, Jul 27 2022
%Y Cf. A000071, A077888, A077941, A105489.
%Y Cf. A000930, A050228, A144898, A144899, A144900, A144901, A144902, A144903, A144904, A226405.
%Y Cf. A078012, A099567, A135851.
%K nonn,easy
%O 0,2
%A _N. J. A. Sloane_, Nov 17 2002
%E More terms from _Augustine O. Munagi_, Apr 11 2005
|
