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

Author

Len Smiley, May 07 2001

Keywords

• nonn
• easy

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

In the same way that the sum of any two alternating terms of A006498 produces a term from A000045 (the Fibonacci sequence), so it could be thought of as a "meta-Fibonacci," and the sum of any two alternating terms of A013979 produces a term from A000930 (Narayana’s cows), so it could analogously be called "meta-Narayana’s cows," this sequence embeds (can generate) A000931 (the Padovan sequence), as the odd terms of A000931 are generated by the sum of successive elements (e.g. 1+2=3, 2+3=5, 3+6=9, 6+10=16) and its even terms are generated by the difference of "supersuccessive" (second-order successive or "alternating," separated by a single other term) terms (e.g. 10-3=7, 18-6=12, 31-10=21, 55-18=37) — or, equivalently, adding "supersupersuccessive" terms (separated by 2 other terms, e.g. 1+6=7, 2+10=12, 3+18=21, 6+31=37) — so it could be dubbed the "metaPadovan." - Michael Cohen and Yasuyuki Kachi, Jun 13 2024

Examples

			There are 18=a(6) compositions of 6 with the summand 2 frozen in place: (6), (51), (15), (4[2]), (33), (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).
		

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
• Michael Cohen and Yasuyuki Kachi (2024). Recurrence Relations Rhythm. In: Noll, T., Montiel, M., Gómez, F., Hamido, O.C., Besada, J.L., Martins, J.O. (eds) Mathematics and Computation in Music. MCM 2024. Lecture Notes in Computer Science, vol. 14639. Springer, Cham.
• K. Edwards, M. A. Allen, Strongly restricted permutations and tiling with fences, Disc. Appl. Math. 187 (2015) 82-90, Sect. 4.3
• Index entries for linear recurrences with constant coefficients, signature (1,1,0,1).

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

Programs

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

Magma

R:=PowerSeriesRing(Integers(), 40);
Coefficients(R!( 1/(1-x-x^2-x^4) )); // G. C. Greubel, Apr 09 2021

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

PARI

N=66; my(x='x+O('x^N));
Vec(1/(1-x-x^2-x^4))
/* Joerg Arndt, Oct 21 2012 */

Sage

def A060945_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( 1/(1-x-x^2-x^4) ).list()
A060945_list(40) # G. C. Greubel, Apr 09 2021

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

Extensions

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