login
Number of vertices of the n-th multiplihedron.
10

%I #79 Aug 23 2024 10:49:15

%S 0,1,2,6,21,80,322,1348,5814,25674,115566,528528,2449746,11485068,

%T 54377288,259663576,1249249981,6049846848,29469261934,144293491564,

%U 709806846980,3506278661820,17385618278700,86500622296800,431718990188850,2160826237261692

%N Number of vertices of the n-th multiplihedron.

%C G.f. = x*c(x)*c(x*c(x)) where c(x) is the generating function of the Catalan numbers C(n). Thus a(n) is the Catalan transform of the sequence C(n-1). Reference for the definition of Catalan transform is the paper by Paul Barry. - Stefan Forcey (sforcey(AT)tnstate.edu), Aug 02 2007

%C A129442 is an essentially identical sequence. - _R. J. Mathar_, Jun 13 2008

%C From _Peter Bala_, Jan 27 2020: (Start)

%C This sequence is the main diagonal of the lower triangular array formed by putting the sequence [0, 1, 1, 2, 5, 14, 42, ...] of Catalan numbers (with 0 prepended) in the first column (k = 0) of the array and then completing the triangle using the relation T(n,k) = T(n-1,k) + T(n,k-1) for k >= 1.

%C 0

%C 1 1

%C 1 2 2

%C 2 4 6 6

%C 5 9 15 21 21

%C 14 23 38 59 80 80

%C ...

%C Cf. A307495.

%C Alternatively, the sequence can be obtained by multiplying the sequence of Catalan numbers by the array A106566. (End)

%H Alois P. Heinz, <a href="/A121988/b121988.txt">Table of n, a(n) for n = 0..500</a>

%H R. Bacher, <a href="http://arxiv.org/abs/math/0409050">On generating series of complementary plane trees</a> arXiv:math/0409050 [math.CO], 2004. See p. 19.

%H Paul Barry, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Barry/barry84.html">A Catalan Transform and Related Transformations on Integer Sequences</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5, pp. 1-24.

%H David Callan, <a href="https://arxiv.org/abs/1111.0996">A combinatorial interpretation of the Catalan transform of the Catalan numbers</a>, arXiv:1111.0996 [math.CO], 2011.

%H Stefan Forcey, <a href="https://arxiv.org/abs/0706.3226">Convex Hull Realizations of the Multiplihedra</a>, Theorem 3.2, p. 8, arXiv:0706.3226 [math.AT], 2007-2008.

%H Stefan Forcey, Aaron Lauve, and Frank Sottile, <a href="https://dmtcs.episciences.org/2740/">New Hopf Structures on Binary Trees</a>, dmtcs:2740 - Discrete Mathematics & Theoretical Computer Science, January 1, 2009, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009).

%H Elżbieta Liszewska and Wojciech Młotkowski, <a href="https://arxiv.org/abs/1907.10725">Some relatives of the Catalan sequence</a>, arXiv:1907.10725 [math.CO], 2019.

%H Tian-Xiao He and Louis W. Shapiro, <a href="https://doi.org/10.1016/j.laa.2016.05.035">Row sums and alternating sums of Riordan arrays</a>, Linear Algebra and its Applications, Volume 507, 15 October 2016, Pages 77-95.

%F a(0) = 0; a(n) = C(n-1) + Sum_{i=1..n-1} a(i)*a(n-i), where C(n) = A000108(n).

%F G.f.: (1-sqrt(2*sqrt(1-4x)-1))/2. a(n) = (1/n)*Sum_{k=1..n} binomial(2*n-k-1,n-1)*binomial(2k-2, k-1); a(0)=0. - Stefan Forcey (sforcey(AT)tnstate.edu), Aug 02 2007

%F a(n) = Sum_{k = 0..n} A106566(n,k)*A000108(k-1) with A000108(-1)=0. - _Philippe Deléham_, Aug 27 2007

%F D-finite with recurrence 3*(n-1)*n*a(n) = 14*(n-1)*(2*n-3)*a(n-1) - 4*(4*n-9)*(4*n-7)*a(n-2). - _Vaclav Kotesovec_, Oct 19 2012

%F a(n) ~ 2^(4*n-5/2)/(sqrt(Pi)*3^(n-1/2)*n^(3/2)). - _Vaclav Kotesovec_, Oct 19 2012

%F G.f.: A(x) satisfies A(x)=x*(1+A(x))/((1-A(x))*(1+A(x)^3). - _Vladimir Kruchinin_, Jun 01 2014

%F G.f. is series reversion of (x - x^2) * (1 - x + x^2) = x - 2*x^2 + 2*x^3 - x^4. - _Michael Somos_, Jun 01 2014

%F From _Peter Bala_, Aug 22 2024: (Start)

%F G.f. A(x) = 1 - 1/c(x*c(x)), where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108.

%F Sum_{n >= 1} a(n)*y^n = x*c(x), where y = x*(1 - x). (End)

%e G.f. = x + 2*x^2 + 6*x^3 + 21*x^4 + 80*x^5 + 322*x^6 + 1348*x^7 + 5814*x^8 + ...

%p a:= proc(n) option remember; `if`(n<3, n, (14*(n-1)*(2*n-3)*a(n-1)

%p -4*(4*n-9)*(4*n-7)*a(n-2))/ (3*n*(n-1)))

%p end:

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Oct 20 2012

%t a[0] = 0; a[n_] := a[n] = (2 n - 2)!/((n - 1)! n!) + Sum[ a[i]*a[n - i], {i, n - 1}]; Table[ a@n, {n, 0, 24}] (* _Robert G. Wilson v_, Jun 28 2007 *)

%t a[ n_] := If[ n < 1, 0, SeriesCoefficient[ InverseSeries[ Series[ x - 2 x^2 + 2 x^3 - x^4, {x, 0, n}]], {x, 0, n}]]; (* _Michael Somos_, Jun 01 2014 *)

%t a[0] = 0; a[n_] := Binomial[2n-2, n-1]*Hypergeometric2F1[1/2, 1-n, 2-2n, 4] /n; Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Jan 31 2016 *)

%o (PARI) {a(n) = if( n<1, 0, polcoeff( serreverse( x - 2*x^2 + 2*x^3 - x^4 + x * O(x^n)), n))}; /* _Michael Somos_, Jun 01 2014 */

%Y Cf. A000108, A127632, A129442, A007317, A164965, A106566, A158826, A307495.

%K easy,nonn

%O 0,3

%A _Jonathan Vos Post_, Jun 24 2007

%E More terms from _Robert G. Wilson v_, Jun 28 2007