A116088 -id:A116088 - cp's OEIS frontend

A002478 Bisection of A000930.

1, 1, 3, 6, 13, 28, 60, 129, 277, 595, 1278, 2745, 5896, 12664, 27201, 58425, 125491, 269542, 578949, 1243524, 2670964, 5736961, 12322413, 26467299, 56849086, 122106097, 262271568, 563332848, 1209982081, 2598919345, 5582216355, 11990037126, 25753389181

Offset: 0

N. J. A. Sloane

Number of ways to tile a 3 X n region with 1 X 1, 2 X 2 and 3 X 3 tiles.
Number of ternary words with subwords (0,0), (0,1) and (1,1) not allowed. - Olivier Gérard, Aug 28 2012
Diagonal sums of A063967. - Paul Barry, Nov 09 2005
Row sums of number triangle A116088. - Paul Barry, Feb 04 2006
Sequence is identical to its second differences negated, minus the first 3 terms. - Paul Curtz, Feb 10 2008
a(n) = term (3,3) in the 3 X 3 matrix [0,1,0; 0,0,1; 1,2,1]^n. - Gary W. Adamson, May 30 2008
a(n)/a(n-1) tends to 2.147899035..., an eigenvalue of the matrix and a root to x^3 - x^2 - 2x - 1 = 0. - Gary W. Adamson, May 30 2008
INVERT transform of (1, 2, 1, 0, 0, 0, ...) = (1, 3, 6, 13, 28, ...); such that (1, 2, 1, 0, 0, 0, ...) convolved with (1, 1, 3, 6, 13, 28, 0, 0, 0, ...) shifts to the left. - Gary W. Adamson, Apr 18 2010
a(n) is the top left entry in the n-th power of the 3 X 3 matrix [1, 1, 1; 1, 0, 1; 1, 0, 0] or of the 3 X 3 matrix [1, 1, 1; 1, 0, 0; 1, 1, 0]. - R. J. Mathar, Feb 03 2014

			a(3)=6 as there is one tiling of a 3 X 3 region with only 1 X 1 tiles, 4 tilings with exactly one 2 X 2 tile and 1 tiling consisting of the 3 X 3 tile.

Kenneth Edwards, Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Part II, Fib. Q., 58:2 (2020), 169-177.
L. Euler, (E388) Vollstaendige Anleitung zur Algebra, Zweiter Theil, reprinted in: Opera Omnia. Teubner, Leipzig, 1911, Series (1), Vol. 1, p. 322.
S. Heubach, Tiling an m X n Area with Squares of Size up to k X k (m<=5), Congressus Numerantium 140 (1999), pp. 43-64.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..300
Paul Barry, Centered polygon numbers, heptagons and nonagons, and the Robbins numbers, arXiv:2104.01644 [math.CO], 2021.
Emeric Deutsch, Counting tilings with L-tiles and squares, Problem 10877, Amer. Math. Monthly, 110 (March 2003), 245-246.
Kenneth Edwards and Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, arXiv:1907.06517 [math.CO], 2019.
Leonhard Euler, Vollstaendige Anleitung zur Algebra, Zweiter Teil.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 412
Milan Janjić, Pascal Triangle and Restricted Words, arXiv:1705.02497 [math.CO], 2017.
Milan Janjić, Pascal Matrices and Restricted Words, J. Int. Seq., Vol. 21 (2018), Article 18.5.2.
Richard J. Mathar, Paving Rectangular Regions with Rectangular Tiles: Tatami and Non-Tatami Tilings, arXiv:1311.6135 [math.CO], 2013, Table 19 (halved...).
Richard J. Mathar, Bivariate Generating Functions Enumerating Non-Bonding Dominoes on Rectangular Boards, arXiv:2404.18806 [math.CO], 2024. See p. 5.
Sam Northshield, Some generalizations of a formula of Reznick, SUNY Plattsburgh (2022).
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2.
Index entries for linear recurrences with constant coefficients, signature (1,2,1).

Cf. A000930, A054856, A054857, A025234, A078007, A078039, A226546, A077936 (INVERT transform), A008346 (inverse INVERT transform).

I:=[1,1,3]; [n le 3 select I[n] else Self(n-1) +2*Self(n-2) +Self(n-3): n in [1..41]]; // G. C. Greubel, Apr 14 2023

f[A_]:= Module[{til = A}, AppendTo[til, A[[-1]] + 2A[[-2]] + A[[-3]]]]; NumOfTilings[ n_ ]:= Nest[ f, {1,1,3}, n-2]; NumOfTilings[30]
LinearRecurrence[{1,2,1},{1,1,3},40] (* Vladimir Joseph Stephan Orlovsky, Jan 28 2012 *)
CoefficientList[Series[1/(1-x-2x^2-x^3),{x,0,40}],x] (* Harvey P. Dale, Oct 17 2024 *)

a(n)=([0,1,0; 0,0,1; 1,2,1]^n*[1;1;3])[1,1] \\ Charles R Greathouse IV, Apr 08 2016

@CachedFunction
def a(n): # A002478
    if (n<3): return (1,1,3)[n]
    else: return sum(binomial(2,j)*a(n-j) for j in range(1,4))
[a(n) for n in (0..40)] # G. C. Greubel, Apr 14 2023

G.f.: 1 / (1-x-2*x^2-x^3). [Simon Plouffe in his 1992 dissertation.]
a(n) = a(n-1) + 2*a(n-2) + a(n-3).
a(n) = Sum_{k=0..n} binomial(2*n-2*k, k). - Paul Barry, Nov 13 2004
a(n) = Sum_{k=0..floor(n/2)} Sum_{j=0..n-k} C(j, n-k-j)*C(j, k). - Paul Barry, Nov 09 2005
a(n) = Sum_{k=0..n} C(2*k,n-k) = Sum_{k=0..n} C(n,k)*C(3*k,n)/C(3*k,k). - Paul Barry, Feb 04 2006
a(n) = A000930(n) + 2*Sum_{i=0..n-2} a(i)*A000930(n-2-i). - Michael Tulskikh, Jun 07 2020

Additional comments from Silvia Heubach (silvi(AT)cine.net), Apr 21 2000

A094686 A Fibonacci convolution.

Original entry on oeis.org

1, 0, 1, 2, 2, 4, 7, 10, 17, 28, 44, 72, 117, 188, 305, 494, 798, 1292, 2091, 3382, 5473, 8856, 14328, 23184, 37513, 60696, 98209, 158906, 257114, 416020, 673135, 1089154, 1762289, 2851444, 4613732, 7465176, 12078909, 19544084, 31622993, 51167078, 82790070

Offset: 0

Paul Barry, May 19 2004

Convolution of A000045 and A049347.
Diagonal sums of number triangle A116088. - Paul Barry, Feb 04 2006
Let (b(n)) be the p-INVERT of (1,1,0,0,0,0,0,0,...) using p(S) = 1 - S^2; then b(n) = a(n+1) for n >=0. See A292324. - Clark Kimberling, Sep 15 2017

G. C. Greubel, Table of n, a(n) for n = 0..1000
Elena Barcucci, Antonio Bernini, Stefano Bilotta, and Renzo Pinzani, Non-overlapping matrices, arXiv:1601.07723 [cs.DM], 2016 (see 1st column of Table 1 p. 8).
Stefano Bilotta, Variable-length Non-overlapping Codes, arXiv preprint arXiv:1605.03785 [cs.IT], 2016 [See Table 2].
Joshua P. Bowman, Compositions with an Odd Number of Parts, and Other Congruences, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 19.
David Broadhurst, Multiple Deligne values: a data mine with empirically tamed denominators, arXiv:1409.7204 [hep-th], 2014 (see p. 10).
Leonard Rozendaal, Pisano word, tesselation, plane-filling fractal, Preprint, 2017.
Index entries for linear recurrences with constant coefficients, signature (0,1,2,1).

Cf. A000045, A005252, A049347, A093040, A116088, A292324.

[(Fibonacci(n+1) +((n+2) mod 3) -1)/2: n in [0..40]]; // G. C. Greubel, Feb 09 2023

LinearRecurrence[{0,1,2,1}, {1,0,1,2}, 40] (* Jean-François Alcover, Sep 21 2017 *)

Vec(1/((1-x-x^2)*(1+x+x^2)) + O(x^50)) \\ Michel Marcus, Sep 27 2014

[(fibonacci(n+1) + (n+2)%3 - 1)/2 for n in range(41)] # G. C. Greubel, Feb 09 2023

G.f.: 1/((1-x-x^2)*(1+x+x^2)).
a(n) = 2*sqrt(3)*Sum_{k=0..n} Fibonacci(k+1)*cos((4*(n-k)+1)*Pi/6)/3.
a(n) = a(n-2) + 2*a(n-3) + a(n-4).
From Paul Barry, Jan 13 2005: (Start)
a(n) = A005252(n) - (-cos((2*n+1)*Pi/3)/2 - sqrt(3)*sin((2*n+1)*Pi/3)/6 + sqrt(3)*cos(Pi*n/3+Pi/6)/6 + sin((2*n+1)*Pi/6)/2).
a(n) = Sum_{k=0..floor(n/2)} if(mod(n-k, 2)=0, binomial(n-k, k), 0).
a(n) = A093040(n-1) - Fibonacci(n). (End)
a(n) = Sum_{k=0..floor(n/2)} C(n-k, k)*(1+(-1)^(n-k))/2. - Paul Barry, Sep 09 2005
From Paul Barry, Feb 04 2006: (Start)
a(n) = Sum_{k=0..floor(n/2)} C(2*k, n-2*k).
a(n) = Sum_{k=0..floor(n/2)} C(n-k,k)*C(3*k,n-k)/C(3*k,k). (End)
2*a(n) = A000045(n+1) + A049347(n). - R. J. Mathar, Feb 13 2020
a(n) = (1/2)*(A000045(n+1) + A049347(n)). - G. C. Greubel, Feb 09 2023

A179330 E.g.f. satisfies: A(x) = (1+x)/(1+3x) A(x*(1+x)^2).

Original entry on oeis.org

0, 2, -6, 42, -468, 7080, -133128, 2938824, -73169568, 1997384832, -58814501760, 1868053207680, -65311214042880, 2585560450337280, -115344597684718080, 5424254194395456000, -244310147229735014400, 10256126830544041574400

Offset: 0

Paul D. Hanna, Jul 21 2010

sign

			E.g.f.: A(x) = 2*x - 6*x^2/2! + 42*x^3/3! - 468*x^4/4! + 7080*x^5/5! - 133128*x^6/6! + 2938824*x^7/7! - 73169568*x^8/8! + 1997384832*x^9/9! - 58814501760*x^10/10! + 1868053207680*x^11/11! - 65311214042880*x^12/12! +...
...
A(x*(1+x)^2) = 2*x + 2*x^2/2! - 18*x^3/3! + 108*x^4/4! - 480*x^5/5! - 2808*x^6/6! + 162792*x^7/7! - 3940128*x^8/8! + 57267648*x^9/9! + 534366720*x^10/10! - 78703384320*x^11/11! + 2883142045440*x^12/12! +...
...
where A(x*(1+x)^2) = (1+3*x)/(1+x) * A(x).
...
Related expansions begin:
. A = 2*x - 6*x^2/2! + 42*x^3/3! - 468*x^4/4! + 7080*x^5/5! +...
. A*Dx(A)/2! = 8*x^2/2! - 90*x^3/3! + 1332*x^4/4! - 25200*x^5/5! +...
. A*Dx(A*Dx(A))/3! = 48*x^3/3! - 1248*x^4/4! + 32760*x^5/5! -+...
. A*Dx(A*Dx(A*Dx(A)))/4! = 384*x^4/4! - 18480*x^5/5! + 770400*x^6/6! -+...
. A*Dx(A*Dx(A*Dx(A*Dx(A))))/5! = 3840*x^5/5! - 300672*x^6/6! +-...
...
Sums of which generate the square of the g.f. of A001764:
. G001764(-x)^2 = 1 - A + A*Dx(A)/2! - A*Dx(A*Dx(A))/3! + A*Dx(A*Dx(A*Dx(A)))/4! -+...
. G001764(-x)^2 = 1 - 2*x + 7*x^2 - 30*x^3 + 143*x^4 - 728*x^5 +...+ A006013(n)*(-x)^n +...
...
The Riordan array ((1+x)^2, x*(1+x)^2) (cf. A116088) begins:
1;
2, 1;
1, 4, 1;
0, 6, 6, 1;
0, 4, 15, 8, 1;
0, 1, 20, 28, 10, 1;
0, 0, 15, 56, 45, 12, 1; ...
The matrix log of Riordan array ((1+x)^2, x*(1+x)^2) begins:
0;
2, 0;
-6/2!, 4, 0;
42/3!, -12/2!, 6, 0;
-468/4!, 84/3!, -18/2!, 8, 0;
7080/5!, -936/4!, 126/3!, -24/2!, 10, 0;
-133128/6!, 14160/5!, -1404/4!, 168/3!, -30/2!, 12, 0; ...
where the g.f. of the leftmost column equals the e.g.f. of this sequence.

Cf. A179331, variants: A179320, A179420.

/* E.g.f. satisfies: A(x) = (1+x)/(1+3*x)*A(x*(1+x)^2): */
{a(n)=local(A=2*x, B); for(m=2, n, B=(1+x)/(1+3*x+O(x^(n+3)))*subst(A,x,x*(1+x)^2+O(x^(n+3))); A=A-polcoeff(B, m+1)*x^m/(m-1)/2); n!*polcoeff(A, n)}

/* (1+x)^2 = 1 + A + A*Dx(A)/2! + A*Dx(A*Dx(A))/3! +...: */
{a(n)=local(A=0+sum(m=1,n-1,a(m)*x^m/m!),D=1,R=0);R=-((1+x)^2+x*O(x^n))+1+sum(m=1,n,(D=A*deriv(x*D+x*O(x^n)))/m!);-n!*polcoeff(R,n)}

/* First column of the matrix log of triangle A116088: */
{a(n)=local(M=matrix(n+1, n+1, r, c, if(r>=c, polcoeff(((1+x)^2+x*O(x^n))^c,r-c))), LOG, ID=M^0); LOG=sum(m=1, n+1, -(ID-M)^m/m); n!*LOG[n+1, 1]}

E.g.f. A=A(x) satisfies:
. (1+x)^2 = 1 + A + A*Dx(A)/2! + A*Dx(A*Dx(A))/3! + A*Dx(A*Dx(A*Dx(A)))/4! +...
. (1+x)^2*(1+x*(1+x)^2)^2 = 1 + 2*A + 2^2*A*Dx(A)/2! + 2^3*A*Dx(A*Dx(A))/3! + 2^4*A*Dx(A*Dx(A*Dx(A)))/4! +...
. G001764(-x)^2 = 1 - A + A*Dx(A)/2! - A*Dx(A*Dx(A))/3! + A*Dx(A*Dx(A*Dx(A)))/4! -+...; G001764(x) = g.f. of A001764;
where Dx(F) = d/dx(x*F).
INVERSION FORMULA:
More generally, if A(x) = A(G(x)) * G(x)/(x*G'(x)) with G(0)=0, G'(0)=1,
then G(x) can be obtained from A=A(x) by the series:
. G(x)/x = 1 + A + A*Dx(A)/2! + A*Dx(A*Dx(A))/3! + A*Dx(A*Dx(A*Dx(A)))/4! +... where Dx(F) = d/dx(x*F).
ITERATION FORMULA:
Let G_n(x) denote the n-th iteration of G(x) = x*(1+x)^2, and A=A(x), then:
. A(x) = A(G_n(x)) * G_n(x)/(x*G_n'(x)) for all n;
. G_n(x)/x = 1 + n*A + n^2*A*Dx(A)/2! + n^3*A*Dx(A*Dx(A))/3! + n^4*A*Dx(A*Dx(A*Dx(A)))/4! +... where Dx(F) = d/dx(x*F).
...
MATRIX LOG OF RIORDAN ARRAY (G(x)/x, G(x)) where G(x) = x*(1+x)^2:
. k*A(x) = e.g.f. of column k of the matrix log of triangle A116088 for k>=0.

cp's OEIS Frontend

A002478 Bisection of A000930.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions

A094686 A Fibonacci convolution.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

A179330 E.g.f. satisfies: A(x) = (1+x)/(1+3*x) * A(x*(1+x)^2).

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

PARI

PARI

Formula

A179330 E.g.f. satisfies: A(x) = (1+x)/(1+3x) A(x*(1+x)^2).