A002296 Number of dissections of a polygon: binomial(7n,n)/(6n+1). (Formerly M4442 N1878)

1, 1, 7, 70, 819, 10472, 141778, 1997688, 28989675, 430321633, 6503352856, 99726673130, 1547847846090, 24269405074740, 383846168712104, 6116574500860880, 98106248306858715, 1582638261961640247, 25661404527790252375, 417980115131315136400

Offset

0,3

Comments

a(n), n>=1, enumerates heptic (7-ary) trees (rooted, ordered, incomplete) with n vertices (including the root).

Pfaff-Fuss-Catalan sequence C^{m}_n for m=7. See the Graham et al. reference, p. 347. eq. 7.66. See also the Pólya-Szegő reference.

Also 7-Raney sequence. See the Graham et al. reference, pp. 346-347.

a(n) = A258708(3*n,2*n) for n > 0. - Reinhard Zumkeller, Jun 23 2015

This is instance k = 7 of the generalized Catalan family {C(k, n)}_{n>=0} given in a comment of A130564. - Wolfdieter Lang, Feb 05 2024

References

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, pp. 200, 347.

G. Pólya and G. Szegő, Problems and Theorems in Analysis, Springer-Verlag, Heidelberg, New York, 2 vols., 1972, Vol. 1, problem 211, p. 146 with solution on p. 348.

Ulrike Sattler, Decidable classes of formal power series with nice closure properties, Diplomarbeit im Fach Informatik, Univ. Erlangen - Nürnberg, Jul 27 1994.

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

Links

T. D. Noe, Table of n, a(n) for n = 0..100

Wun-Seng Chou, Tian-Xiao He, Peter J.-S. Shiue, On the Primality of the Generalized Fuss-Catalan Numbers, J. Int. Seqs., Vol. 21 (2018), #18.2.1.

F. Harary, E. M. Palmer, and R. C. Read, On the cell-growth problem for arbitrary polygons, computer printout, circa 1974.

F. Harary, E. M. Palmer and R. C. Read, On the cell-growth problem for arbitrary polygons, Discr. Math. 11 (1975), 371-389. See Table 6. n = 8. Sequence U(8) p. 387.

Clemens Heuberger, Sarah J. Selkirk, and Stephan Wagner, Enumeration of Generalized Dyck Paths Based on the Height of Down-Steps Modulo k, arXiv:2204.14023 [math.CO], 2022.

V. E. Hoggatt, Jr., 7-page typed letter to N. J. A. Sloane with suggestions for new sequences, circa 1977.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 289.

R. P. Loh, A. G. Shannon, and A. F. Horadam, Divisibility Criteria and Sequence Generators Associated with Fermat Coefficients, Preprint, 1980.

J.-C. Novelli and J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv:1403.5962 [math.CO], 2014.

Editor's note: Über die Bestimmung der Anzahl der verschiedenen Arten, auf welche sich ein n-Eck durch Diagonalen in lauter m-Ecke zerlegen laesst, mit Bezug auf einige Abhandlungen der Herren Lame, Rodrigues, Binet, Catalan und Duhamel in dem Journal de Mathematiques pures et appliquees, publie par Joseph Liouville. T. III. IV., Archiv der Mathematik u. Physik, 1 (1841), pp. 193ff; see especially p. 198.

B. Sury, Generalized Catalan numbers: linear recursion and divisibility, JIS 12 (2009), Article 09.7.5.

Lajos Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (5).

Formula

O.g.f. A(x) = 1 + x*A(x)^7 = 1/(1-x*A(x)^6).

a(n) = binomial(7*n,n-1)/n, n>=1, a(0)=1. From the Lagrange series of the o.g.f. A(x) with its above given implicit equation.

D-finite with recurrence: 72*n*(6*n-1)*(3*n-1)*(2*n-1)*(3*n-2)*(6*n+1)*a(n) - 7*(7*n-3)*(7*n-6)*(7*n-2)*(7*n-5)*(7*n-1)*(7*n-4)*a(n-1) = 0. - R. J. Mathar, Nov 16 2012

a(n) are special values of Jacobi polynomials, in Maple notation:

a(n) = JacobiP(n-1, 6*n+1, -n, 1)/n, n = 1, 2, ... . - Karol A. Penson, Mar 16 2015

a(n) = binomial(7*n+1, n)/(7*n+1) = A062993(n+5,5). - Robert FERREOL, Apr 02 2015

a(0) = 1; a(n) = Sum_{i1+i2+...+i7=n-1} a(i1)*a(i2)*...*a(i7) for n>=1. - Robert FERREOL, Apr 02 2015

From Ilya Gutkovskiy, Jan 16 2017: (Start)

O.g.f.: 6F5(1/7,2/7,3/7,4/7,5/7,6/7; 1/3,1/2,2/3,5/6,7/6; 823543*x/46656).

E.g.f.: 6F6(1/7,2/7,3/7,4/7,5/7,6/7; 1/3,1/2,2/3,5/6,1,7/6; 823543*x/46656).

a(n) ~ 7^(7*n+1/2)/(sqrt(Pi)*3^(6*n+3/2)*4^(3*n+1)*n^(3/2)). (End)

x*A'(x)/A(x) = (A(x) - 1)/(- 6*A(x) + 7) = x + 13*x^2 + 190*x^3 + 2925*x^4 + ... = (1/7)*Sum_{n >= 1} binomial(7*n,n)*x^n. Cf. A001764 and A002293, A002294, A002295. - Peter Bala, Feb 04 2022

Example

There are a(2)=7 heptic trees (vertex degree <= 7 and 7 possible branchings) with 2 vertices (one of them the root). Adding one more branch (one more vertex) to these 7 trees yields 7*7 + binomial(7,2) = 70 = a(3) such trees.

Maple

seq(binomial(7*n+1, n)/(7*n+1), n=0..30); # Robert FERREOL, Apr 02 2015
n:=30: G:=series(RootOf(g = 1+x*g^7, g), x=0, n+1): seq(coeff(G, x, k), k=0..n); # Robert FERREOL, Apr 02 2015

Mathematica

Table[Binomial[7n, n]/(6n+1), {n, 0, 20}] (* Harvey P. Dale, Nov 21 2011 *)

Prog

(PARI) a(n)=binomial(7*n, n)/(6*n+1) \\ Charles R Greathouse IV, Feb 06 2012
(Haskell)
a002296 n = a002296_list !! n
a002296_list = [a258708 (4 * n) (3 * n) | n <- [1..]]
-- Reinhard Zumkeller, Jun 23 2015

Crossrefs

Cf. A001764, A002293, A002294, A002295.

Sixth column of triangle A062993.

Cf. A235535: binomial(9n,3n)/(6n+1); A235536: binomial(8n,2n)/(6n+1).

Cf. A258708.

Cf. A130564.

Sequence in context: A268301 A228927 A097184 * A027394 A346767 A209327

Adjacent sequences: A002293 A002294 A002295 * A002297 A002298 A002299

Keyword

easy,nonn,nice

Author

N. J. A. Sloane

Extensions

Pfaff-Fuss-Catalan, Raney, o.g.f. and 7-ary tree comments from Wolfdieter Lang, Sep 14 2007

Status

approved