A060945 Number of compositions (ordered partitions) of n into 1's, 2's and 4's.

1, 1, 2, 3, 6, 10, 18, 31, 55, 96, 169, 296, 520, 912, 1601, 2809, 4930, 8651, 15182, 26642, 46754, 82047, 143983, 252672, 443409, 778128, 1365520, 2396320, 4205249, 7379697, 12950466, 22726483, 39882198, 69988378, 122821042, 215535903, 378239143, 663763424, 1164823609

Offset

0,3

Comments

Diagonal sums of A038137. - Paul Barry, Oct 24 2005

From Gary W. Adamson, Oct 28 2010: (Start)

INVERT transform of the aerated Fibonacci sequence (1, 0, 1, 0, 2, 0, 3, 0, 5, ...).

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)

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

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

a(n) - a(n-2) = number of compositions of n with no 2's = A005251(n+1). - Gregory L. Simay, Jul 18, 2016

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

Links

Harry J. Smith, Table of n, a(n) for n = 0..500

Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics 4 (2010), 119-135

Index entries for linear recurrences with constant coefficients, signature (1,1,0,1).

Formula

a(n) = a(n-1) + a(n-2) + a(n-4).

G.f.: 1 / (1 - x - x^2 - x^4).

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

a(2n) = A238236(n), a(2n+1) = A097472(n). - Philippe Deléham, Feb 20 2014

a(n) + a(n+1) = A005314(n+2). - R. J. Mathar, Jun 17 2020

Example

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

Maple

m:= 40; S:= series( 1/(1-x-x^2-x^4), x, m+1);
seq(coeff(S, x, j), j = 0..m); # G. C. Greubel, Apr 09 2021

Mathematica

LinearRecurrence[{1, 1, 0, 1}, {1, 1, 2, 3}, 39] (* or *)
CoefficientList[Series[1/(1-x-x^2-x^4), {x, 0, 38}], x] (* Michael De Vlieger, May 10 2017 *)

Prog

(Haskell)
a060945 n = a060945_list !! (n-1)
a060945_list = 1 : 1 : 2 : 3 : 6 : zipWith (+) a060945_list
   (zipWith (+) (drop 2 a060945_list) (drop 3 a060945_list))
-- Reinhard Zumkeller, Mar 23 2012
(PARI)
N=66; my(x='x+O('x^N));
Vec(1/(1-x-x^2-x^4))
/* Joerg Arndt, Oct 21 2012 */
(Magma)
R<x>:=PowerSeriesRing(Integers(), 40);
Coefficients(R!( 1/(1-x-x^2-x^4) )); // G. C. Greubel, Apr 09 2021
(Sage)
def A060945_list(prec):
    P.<x> = PowerSeriesRing(ZZ, prec)
    return P( 1/(1-x-x^2-x^4) ).list()
A060945_list(40) # G. C. Greubel, Apr 09 2021

Crossrefs

Cf. A000045 (1's and 2's only), A023359 (all powers of 2)

Same as unsigned version of A077930.

All of A060945, A077930, A181532 are variations of the same sequence. - N. J. A. Sloane, Mar 04 2012

Sequence in context: A102702 A077930 A181532 * A349904 A023359 A357455

Adjacent sequences: A060942 A060943 A060944 * A060946 A060947 A060948

Keyword

nonn,easy

Author

Len Smiley, May 07 2001

Extensions

a(0) = 1 prepended by Joerg Arndt, Oct 21 2012

Status

approved