login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003168 Number of blobs with 2n+1 edges.
(Formerly M3574)
16
1, 1, 4, 21, 126, 818, 5594, 39693, 289510, 2157150, 16348960, 125642146, 976789620, 7668465964, 60708178054, 484093913917, 3884724864390, 31348290348086, 254225828706248, 2070856216759478, 16936016649259364 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

a(n) is the number of ways to dissect a convex (2n+2)-gon with non-crossing diagonals so that no (2m+1)-gons (m>0) appear. - Len Smiley

a(n) is the number of plane trees with 2n+1 leaves and all non-leaves having an odd number > 1 of children. - Jordan Tirrell, Jun 09 2017

REFERENCES

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

D. Birmajer, J. B. Gil, M. D. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv preprint arXiv:1503.05242 [math.CO], 2015.

L. Carlitz, Enumeration of two-line arrays, Fib. Quart., Vol. 11 Number 2 (1973), 113-130.

Frédéric Chapoton and Philippe Nadeau, Combinatorics of the categories of noncrossing partitions, Séminaire Lotharingien de Combinatoire 78B (2017), Article #37.

Michael Drmota, Anna de Mier, Marc Noy, Extremal statistics on non-crossing configurations, Discrete Math. 327 (2014), 103--117. MR3192420. See p. 116, B_b(z). - N. J. A. Sloane, May 18 2014

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 415

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

R. C. Read, On the enumeration of a class of plane multigraphs, Aequat. Math. 31 (1986) no 1, 47-63.

L. Smiley, Even-gon reference

FORMULA

a(n) = Sum_{k=1..n} binomial(n, k)*binomial(2*n+k, k-1)/n.

G.f.: A(x) = Sum_{n>=0} a(n)*x^(2*n+1) satisfies (A-2*A^3)/(1-A^2)=x. - Len Smiley.

4*n*(2*n + 1)*(17*n - 22)*a(n) = (1207*n^3 - 2769*n^2 + 1850*n - 360)*a(n - 1) - 2*(17*n - 5)*(n - 2)*(2*n - 3)*a(n - 2). - Vladeta Jovovic, Jul 16 2004

G.f.: A(x) = 1/(1-G003169(x)) where G003169(x) is the g.f. of A003169. - Paul D. Hanna, Nov 17 2004

a(n) = JacobiP(n-1,1,n+1,3)/n for n > 0. - Mark van Hoeij, Jun 02 2010

a(n) = 1/(2*n+1)*sum((-1)^j*2^(n-j)*binomial(2*n+1,j)*binomial(3*n-j,2*n),j=0..n). - Vladimir Kruchinin, Dec 24 2010

a(n) = upper left term in M^n, M = the production matrix:

1, 1

3, 3, 1

5, 5, 3, 1

7, 7, 5, 3, 1

9, 9, 7, 5, 3, 1

... . - Gary W. Adamson, Jul 08 2011

a(n) ~ sqrt(14+66/sqrt(17)) * (71+17*sqrt(17))^n / (sqrt(Pi) * n^(3/2) * 2^(4*n+4)). - Vaclav Kotesovec, Jul 01 2015

From Peter Bala, Oct 05 2015: (Start)

a(n) = 1/n * Sum_{i = 0..n} 2^(n-i-1)*binomial(2*n,i)* binomial(n,i+1).

O.g.f. = 1 + series reversion( x/((1 + 2*x)*(1 + x)^2) ).

Logarithmically differentiating the modified g.f. 1 + 4*x + 21*x^2 + 126*x^3 + 818*x^4 + ... gives the o.g.f. for A114496, apart from the initial term. (End)

G.f.: A(x) satisfies A = 1 + x*A^3/(1-x*A^2). - Jordan Tirrell, Jun 09 2017

a(n) = A100327(n)/2 for n>=1. - Peter Luschny, Jun 10 2017

EXAMPLE

a(2)=4 because we may place exactly one diagonal in 3 ways (forming 2 quadrilaterals), or not place any (leaving 1 hexagon).

MAPLE

Order := 40; solve(series((A-2*A^3)/(1-A^2), A)=x, A);

A003168 := n -> `if`(n=0, 1, A100327(n)/2): seq(A003168(n), n=0..20); # Peter Luschny, Jun 10 2017

MATHEMATICA

a[0] = 1; a[n_] = (2^(-n-1)*(3n)!* Hypergeometric2F1[-1-2n, -2n, -3n, -1])/((2n+1)* n!*(2n)!); Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 25 2011, after Vladimir Kruchinin *)

PROG

(PARI) a(n)=if(n<0, 0, polcoeff(serreverse((x-2*x^3)/(1-x^2)+O(x^(2*n+2))), 2*n+1))

(PARI) {a(n)=local(A=1+x+x*O(x^n)); for(i=1, n, A=(1+x*A)/(1-x*A)^2); sum(k=0, n, polcoeff(A^(n-k), k))} \\ Paul D. Hanna, Nov 17 2004

(Haskell)

import Data.List (transpose)

a003168 0 = 1

a003168 n = sum (zipWith (*)

   (tail $ a007318_tabl !! n)

   ((transpose $ take (3*n+1) a007318_tabl) !! (2*n+1)))

   `div` fromIntegral n

-- Reinhard Zumkeller, Oct 27 2013

CROSSREFS

Cf. A049124 (no 2m-gons).

Cf. A003169, A100327, A114496, A007318.

Sequence in context: A195262 A162480 A275758 * A211249 A185047 A032326

Adjacent sequences:  A003165 A003166 A003167 * A003169 A003170 A003171

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 19 14:52 EST 2018. Contains 317352 sequences. (Running on oeis4.)