A045720 3-fold convolution of A001700(n), n >= 0.

1, 9, 57, 312, 1578, 7599, 35401, 161052, 719790, 3173090, 13836426, 59803104, 256596276, 1094249019, 4642178601, 19605872724, 82483419846, 345839048094, 1445715336366, 6027524015664, 25070662980876, 104056307673654

Offset: 0

Author

Wolfdieter Lang

Keywords

• easy
• nonn

Comments

Total number of 132 (or 213) patterns in the set of all 123-avoiding permutations of length (n+3). - Cheyne Homberger, Mar 16 2012

a(n) is the degree of the cyclic graphical Gaussian model for the (n+3) cycle. - Mateusz Michalek, Mar 04 2023

References

• B. Sturmfels, and C. Uhler. Multivariate Gaussians, semidefinite matrix completion, and convex algebraic geometry. Annals of the Institute of Statistical Mathematics 62.4 (2010): 603-638, Conjecture 2 proved in "Geometry of the Gaussian graphical model of the cycle"

Links

• Indranil Ghosh, Table of n, a(n) for n = 0..1500
• José Agapito, Ângela Mestre, Maria M. Torres, and Pasquale Petrullo, On One-Parameter Catalan Arrays, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.1.
• A. Ayyer, Towards a Human Proof of Gessel's Conjecture, JIS 12 (2009) 09.4.2
• R. Dinu, M. Michalek, and M. Vodička. Geometry of the Gaussian graphical model of the cycle, arXiv preprint arXiv:2111.02937 [math.AG] (2021).
• C. Homberger, Expected patterns in permutation classes, Electronic Journal of Combinatorics, 19(3) (2012), P43.
• Milan Janjić, Pascal Matrices and Restricted Words, J. Int. Seq., Vol. 21 (2018), Article 18.5.2.
• D. R. Snow, Spreadsheets, Power Series, Generating Functions and Integers, The College Maths. J. 20 (1989) 149.

Crossrefs

Cf. A000108, A001700, A008549.

Programs

Mathematica

Table[(n+5)*Binomial[2*(n+3),n+3]/4-3*2^(2n+3),{n,0,21}] (* Indranil Ghosh, Feb 18 2017 *)

PARI

x='x+O('x^30); Vec((((1-4*x)^(-1/2)-1)/(2*x))^3) \\ Altug Alkan, Sep 04 2018

Python

import math
def C(n,r):
    f=math.factorial
    return f(n)/f(r)/f(n-r)
def A045720(n):
    return (n+5)*C(2*(n+3),n+3)/4-3*2**(2*n+3) # Indranil Ghosh, Feb 18 2017

Formula

a(n) = (n+5)*binomial(2*(n+3), n+3)/4 - 3*2^(2*n+3);

G.f.: (c(x)/sqrt(1-4*x))^3, where c(x) = g.f. for Catalan numbers A000108;

recursion: a(n)=(2*(2*n+7)/(n+3))*a(n-1)+(3/(n+3))*A008549(n+1), a(0)=1.