|
%I #67 Apr 09 2021 22:19:12
%S 1,1,2,3,6,10,18,31,55,96,169,296,520,912,1601,2809,4930,8651,15182,
%T 26642,46754,82047,143983,252672,443409,778128,1365520,2396320,
%U 4205249,7379697,12950466,22726483,39882198,69988378,122821042,215535903,378239143,663763424,1164823609
%N Number of compositions (ordered partitions) of n into 1's, 2's and 4's.
%C Diagonal sums of A038137. - _Paul Barry_, Oct 24 2005
%C From _Gary W. Adamson_, Oct 28 2010: (Start)
%C INVERT transform of the aerated Fibonacci sequence (1, 0, 1, 0, 2, 0, 3, 0, 5, ...).
%C a(n) = term (4,4) in the n-th power of the matrix [0,1,0,0; 0,0,1,0; 0,0,0,1; 1,0,1,1]. (End)
%C Number of permutations satisfying -k <= p(i)-i <= r and p(i)-i not in I, i=1..n, with k=1, r=3, I={2}. - _Vladimir Baltic_, Mar 07 2012
%C Number of compositions of n if the summand 2 is frozen in place or equivalently, if the ordering of the summand 2 does not count. - _Gregory L. Simay_, Jul 18 2016
%C a(n) - a(n-2) = number of compositions of n with no 2's = A005251(n+1). - _Gregory L. Simay_, Jul 18, 2016
%C In general, the number of compositions of n with summand k frozen in place is equal to the number of compositions of n with only summands 1,...,k,2k. - _Gregory L. Simay_, May 10 2017
%H Harry J. Smith, <a href="/A060945/b060945.txt">Table of n, a(n) for n = 0..500</a>
%H Vladimir Baltic, <a href="http://pefmath.etf.rs/vol4num1/AADM-Vol4-No1-119-135.pdf">On the number of certain types of strongly restricted permutations</a>, Applicable Analysis and Discrete Mathematics 4 (2010), 119-135
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,0,1).
%F a(n) = a(n-1) + a(n-2) + a(n-4).
%F G.f.: 1 / (1 - x - x^2 - x^4).
%F a(n) = Sum_{k=0..floor(n/2)} Sum_{i=0..n-k} C(i, n-k-i)*C(2*i-n+k, 3*k-2*n+2*i). - _Paul Barry_, Oct 24 2005
%F a(2n) = A238236(n), a(2n+1) = A097472(n). - _Philippe Deléham_, Feb 20 2014
%F a(n) + a(n+1) = A005314(n+2). - _R. J. Mathar_, Jun 17 2020
%e There are 18=a(6) compositions of 6 with the summand 2 frozen in place: (6), (51), (15), (4,[2]), (3,3) (411), (141), (114), (3[2]1), (1[2]3)), ([222]), (3111), (1311), (1131), (1113), ([22]11), ([2]1111), (111111). Equivalently, the position of the summand 2 does not affect the composition count. For example, (321)=(231)=(312) and (123)=(213)=(132).
%p m:= 40; S:= series( 1/(1-x-x^2-x^4), x, m+1);
%p seq(coeff(S, x, j), j = 0..m); # _G. C. Greubel_, Apr 09 2021
%t LinearRecurrence[{1,1,0,1}, {1,1,2,3}, 39] (* or *)
%t CoefficientList[Series[1/(1-x-x^2-x^4), {x, 0, 38}], x] (* _Michael De Vlieger_, May 10 2017 *)
%o (Haskell)
%o a060945 n = a060945_list !! (n-1)
%o a060945_list = 1 : 1 : 2 : 3 : 6 : zipWith (+) a060945_list
%o (zipWith (+) (drop 2 a060945_list) (drop 3 a060945_list))
%o -- _Reinhard Zumkeller_, Mar 23 2012
%o (PARI)
%o N=66; my(x='x+O('x^N));
%o Vec(1/(1-x-x^2-x^4))
%o /* _Joerg Arndt_, Oct 21 2012 */
%o (Magma)
%o R<x>:=PowerSeriesRing(Integers(), 40);
%o Coefficients(R!( 1/(1-x-x^2-x^4) )); // _G. C. Greubel_, Apr 09 2021
%o (Sage)
%o def A060945_list(prec):
%o P.<x> = PowerSeriesRing(ZZ, prec)
%o return P( 1/(1-x-x^2-x^4) ).list()
%o A060945_list(40) # _G. C. Greubel_, Apr 09 2021
%Y Cf. A000045 (1's and 2's only), A023359 (all powers of 2)
%Y Same as unsigned version of A077930.
%Y All of A060945, A077930, A181532 are variations of the same sequence. - _N. J. A. Sloane_, Mar 04 2012
%K nonn,easy
%O 0,3
%A _Len Smiley_, May 07 2001
%E a(0) = 1 prepended by _Joerg Arndt_, Oct 21 2012
|
