A002802 -id:A002802 - cp's OEIS frontend

A035309 Triangle read by rows giving number of ways to glue sides of a 2n-gon so as to produce a surface of genus g.

1, 1, 2, 1, 5, 10, 14, 70, 21, 42, 420, 483, 132, 2310, 6468, 1485, 429, 12012, 66066, 56628, 1430, 60060, 570570, 1169740, 225225, 4862, 291720, 4390386, 17454580, 12317877, 16796, 1385670, 31039008, 211083730, 351683046, 59520825, 58786, 6466460, 205633428, 2198596400, 7034538511, 4304016990

Offset: 0

Dylan Thurston

Row n contains floor((n+2)/2) terms.
a(n,g) is also the number of unicellular (i.e., 1-faced) rooted maps of genus g with n edges. #(vertices) = n - 2g + 1. Dually, this is the number of 1-vertex maps. Catalan(n)=A000108(n) divides a(n,g)2^g.
From Akhmedov and Shakirov's abstract: By pairwise gluing of sides of a polygon, one produces two-dimensional surfaces with handles and boundaries. We give the number N_{g,L}(n_1, n_2, ..., n_L) of different ways to produce a surface of given genus g with L polygonal boundaries with given numbers of sides n_1, n_2, >..., n_L. Using combinatorial relations between graphs on real two-dimensional surfaces, we derive recursive relations between N_{g,L}. We show that Harer-Zagier numbers appear as a particular case of N_{g,L} and derive a new explicit expression for them. - Jonathan Vos Post, Dec 18 2007

			Triangle starts:
n\g    [0]        [1]        [2]        [3]        [4]        [5]
[0]    1;
[1]    1;
[2]    2;         1;
[3]    5,         10;
[4]    14,        70,        21;
[5]    42,        420,       483;
[6]    132,       2310,      6468,      1485;
[7]    429,       12012,     66066,     56628;
[8]    1430,      60060,     570570,    1169740,   225225;
[9]    4862,      291720,    4390386,   17454580,  12317877;
[10]   16796,     1385670,   31039008,  211083730, 351683046, 59520825;
[11]   ...

Gheorghe Coserea, Rows n = 0..200, flattened
E. T. Akhmedov and Sh. Shakirov, Gluing of Surfaces with Polygonal Boundaries, arXiv:0712.2448 [math.CO], 2007-2008, see p. 1.
Sean R. Carrell and Guillaume Chapuy, Simple recurrence formulas to count maps on orientable surfaces, arXiv:1402.6300 [math.CO], 2014.
Ricky X. F. Chen and Christian M. Reidys, A Combinatorial Identity Concerning Plane Colored Trees and its Applications, Journal of Integer Sequences, Vol. 20 (2017), Article 17.3.7.
Benoit Collins, Ion Nechita, and Deping Ye, The absolute positive partial transpose property for random induced states, Random Matrices: Theory Appl. 01, 1250002 (2012); arXiv:1108.1935 [math-ph], 2011.
I. P. Goulden and A. Nica, A direct bijection for the Harer-Zagier formula, J. Comb. Theory, A, 111, No. 2 (2005), 224-238.
J. L. Harer and D. B. Zagier, The Euler characteristic of the moduli space of curves, Invent. Math., 85, No.3 (1986), 457-486.
S. Lando and A. Zvonkin, Graphs on surfaces and their applications, Encyclopaedia of Mathematical Sciences, 141, Springer, 2004, p. 157.
B. Lass, Démonstration combinatoire de la formule de Harer-Zagier, C. R. Acad. Sci. Paris, Serie I, 333, No.3 (2001), 155-160.
A. Mironov, A. Morozov, A. Popolitov, and Sh. Shakirov, Summing up perturbation series around superintegrable point, arXiv:2401.14392 [hep-th], 2024.
T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus, J. Comb. Theory B 13 (1972), 192-218 (Tab. 1).
Nikolai Wyderka and Andreas Ketterer, Probing the geometry of correlation matrices with randomized measurements, arXiv:2211.09610 [quant-ph], 2022.
Liang Zhao and Fengyao Yan, Note on Total Positivity for a Class of Recursive Matrices, Journal of Integer Sequences, Vol. 19 (2016), Article 16.6.5.
Jian Zhou, Hermitian One-Matrix Model and KP Hierarchy, arXiv:1809.07951 [math-ph], 2018.

Row sums give A001147(n).
Columns g=0-2 give: A000108, A002802, A006298.
The last entries in the even rows give A035319.
Cf. A270406, A270790, A270791.

a[n_, g_] := (2n)!/(n+1)!/(n-2g)! Coefficient[Series[(x/2/Tanh[x/2])^(n+1), {x, 0, n}], x, 2g]; Flatten[DeleteCases[#, 0]& /@ Table[a[n, g], {n, 0, 11}, {g, 0, n}]] (* Jean-François Alcover, Aug 30 2011, after E. T. Akhmedov & Sh. Shakirov *)

N = 10; F = 1; gmax(n) = n\2;
Q = matrix(N + 1, N + 1);
Qget(n, g) = { if (g < 0 || g > n/2, 0, Q[n+1, g+1]) };
Qset(n, g, v) = { Q[n+1, g+1] = v };
Quadric({x=1}) = {
  Qset(0, 0, x);
  for (n = 1, length(Q)-1, for (g = 0, gmax(n),
    my(t1 = (1+x)*(2*n-1)/3 * Qget(n-1, g),
       t2 = (2*n-3)*(2*n-2)*(2*n-1)/12 * Qget(n-2, g-1),
       t3 = 1/2 * sum(k = 1, n-1, sum(i = 0, g,
       (2*k-1) * (2*(n-k)-1) * Qget(k-1, i) * Qget(n-k-1, g-i))));
    Qset(n, g, (t1 + t2 + t3) * 6/(n+1))));
};
Quadric('x + O('x^(F+1)));
concat(vector(N+2-F, n, vector(1 + gmax(n-1), g, polcoeff(Qget(n+F-2, g-1), F))))
\\ Gheorghe Coserea, Mar 16 2016

Let c be the number of cycles that appear in product of a (2n)-cycle and a product of n disjoint transpositions; genus is g = (n-c+1)/2.
The Harer-Zagier formula: 1 + 2*Sum_{g>=0} Sum_{n>=2*g} a(n,g) * x^(n+1) * y^(n-2*g+1) / (2*n-1)!! = (1+x/(1-x))^y.
Equivalently, for n >= 0, Sum_{g=0..floor(n/2)} a(n,g)*y^(n-2*g+1) = (2*n-1)!! * Sum_{k=0..n} 2^k * C(n,k) * C(y,k+1).
(n+2)*a(n+1,g) = (4*n+2)*a(n,g) + (4*n^3-n)*a(n-1,g-1) for n,g > 0, a(0,0)=1 and a(0,g)=0 for g > 0.
The g.f. for column g > 0 is x^(2*g) * A270790(g) * P_g(x) / (1-4*x)^(3*g-1/2), where P_g(x) is the polynomial associated with row g of the triangle A270791. - Gheorghe Coserea, Apr 17 2016

More terms and additional comments and references from Valery A. Liskovets, Apr 13 2006

Offset corrected by Gheorghe Coserea, Mar 17 2016

A054335 A convolution triangle of numbers based on A000984 (central binomial coefficients of even order).

Original entry on oeis.org

1, 2, 1, 6, 4, 1, 20, 16, 6, 1, 70, 64, 30, 8, 1, 252, 256, 140, 48, 10, 1, 924, 1024, 630, 256, 70, 12, 1, 3432, 4096, 2772, 1280, 420, 96, 14, 1, 12870, 16384, 12012, 6144, 2310, 640, 126, 16, 1, 48620, 65536, 51480, 28672, 12012, 3840, 924, 160, 18, 1

Offset: 0

Wolfdieter Lang, Mar 13 2000

In the language of the Shapiro et al. reference (given in A053121) such a lower triangular (ordinary) convolution array, considered as a matrix, belongs to the Bell-subgroup of the Riordan-group. The g.f. for the row polynomials p(n,x) (increasing powers of x) is 1/(sqrt(1-4*z)-x*z).
The column sequences are for m=0..20: A000984, A000302 (powers of 4), A002457, A002697, A002802, A038845, A020918, A038846, A020920, A040075, A020922, A045543, A020924, A054337, A020926, A054338, A020928, A054339, A020930, A054340, A020932.
Riordan array (1/sqrt(1-4*x),x/sqrt(1-4*x)). - Paul Barry, May 06 2009
The matrix inverse is apparently given by deleting the leftmost column from A206022. - R. J. Mathar, Mar 12 2013

			Triangle begins:
    1;
    2,    1;
    6,    4,   1;
   20,   16,   6,   1;
   70,   64,  30,   8,  1;
  252,  256, 140,  48, 10,  1;
  924, 1024, 630, 256, 70, 12, 1; ...
Fourth row polynomial (n=3): p(3,x) = 20 + 16*x + 6*x^2 + x^3.
From _Paul Barry_, May 06 2009: (Start)
Production matrix begins
    2,   1;
    2,   2,  1;
    0,   2,  2,  1;
   -2,   0,  2,  2,  1;
    0,  -2,  0,  2,  2,  1;
    4,   0, -2,  0,  2,  2, 1;
    0,   4,  0, -2,  0,  2, 2, 1;
  -10,   0,  4,  0, -2,  0, 2, 2, 1;
    0, -10,  0,  4,  0, -2, 0, 2, 2, 1; (End)

G. C. Greubel, Rows n = 0..100 of triangle, flattened
Paul Barry, Embedding structures associated with Riordan arrays and moment matrices, arXiv preprint arXiv:1312.0583 [math.CO], 2013.
Milan Janjić, Pascal Matrices and Restricted Words, J. Int. Seq., Vol. 21 (2018), Article 18.5.2.

Cf. A000984, A035324, A054336.

Row sums: A026671.

T:= function(n, k)
    if k mod 2=0 then return Binomial(2*n-k, n-Int(k/2))*Binomial(n-Int(k/2),Int(k/2))/Binomial(k,Int(k/2));
    else return 4^(n-k)*Binomial(n-Int((k-1)/2)-1, Int((k-1)/2));
    fi;
  end;
Flat(List([0..10], n-> List([0..n], k-> T(n, k) ))); # G. C. Greubel, Jul 20 2019

T:= func< n, k | (k mod 2) eq 0 select Binomial(2*n-k, n-Floor(k/2))* Binomial(n-Floor(k/2),Floor(k/2))/Binomial(k,Floor(k/2)) else 4^(n-k)*Binomial(n-Floor((k-1)/2)-1, Floor((k-1)/2)) >;
[[T(n,k): k in [0..n]]: n in [0..10]]; // G. C. Greubel, Jul 20 2019

A054335 := proc(n,k)
    if k <0 or k > n then
        0 ;
    elif type(k,odd) then
        kprime := floor(k/2) ;
        binomial(n-kprime-1,kprime)*4^(n-k) ;
    else
        kprime := k/2 ;
        binomial(2*n-k,n-kprime)*binomial(n-kprime,kprime)/binomial(k,kprime) ;
    end if;
end proc: # R. J. Mathar, Mar 12 2013
# Uses function PMatrix from A357368. Adds column 1,0,0,0,... to the left.
PMatrix(10, n -> binomial(2*(n-1), n-1)); # Peter Luschny, Oct 19 2022

Flatten[ CoefficientList[#1, x] & /@ CoefficientList[ Series[1/(Sqrt[1 - 4*z] - x*z), {z, 0, 9}], z]] (* or *)
a[n_, k_?OddQ] := 4^(n-k)*Binomial[(2*n-k-1)/2, (k-1)/2]; a[n_, k_?EvenQ] := (Binomial[n-k/2, k/2]*Binomial[2*n-k, n-k/2])/Binomial[k, k/2]; Table[a[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Sep 08 2011, updated Jan 16 2014 *)

T(n, k) = if(k%2==0, binomial(2*n-k, n-k/2)*binomial(n-k/2,k/2)/binomial(k,k/2), 4^(n-k)*binomial(n-(k-1)/2-1, (k-1)/2));
for(n=0,10, for(k=0,n, print1(T(n,k), ", "))) \\ G. C. Greubel, Jul 20 2019

def T(n, k):
    if (mod(k,2)==0): return binomial(2*n-k, n-k/2)*binomial(n-k/2,k/2)/binomial(k,k/2)
    else: return 4^(n-k)*binomial(n-(k-1)/2-1, (k-1)/2)
[[T(n,k) for k in (0..n)] for n in (0..10)] # G. C. Greubel, Jul 20 2019

a(n, 2*k+1) = binomial(n-k-1, k)*4^(n-2*k-1), a(n, 2*k) = binomial(2*(n-k), n-k)*binomial(n-k, k)/binomial(2*k, k), k >= 0, n >= m >= 0; a(n, m) := 0 if n

Column recursion: a(n, m)=2*(2*n-m-1)*a(n-1, m)/(n-m), n>m >= 0, a(m, m) := 1.

G.f. for column m: cbie(x)*(x*cbie(x))^m, with cbie(x) := 1/sqrt(1-4*x).

G.f.: 1/(1-x*y-2*x/(1-x/(1-x/(1-x/(1-x/(1-... (continued fraction). - Paul Barry, May 06 2009

Sum_{k>=0} T(n,2*k)*(-1)^k*A000108(k) = A000108(n+1). - Philippe Deléham, Jan 30 2012

Sum_{k=0..floor(n/2)} T(n-k,n-2*k) = A098615(n). - Philippe Deléham, Feb 01 2012

T(n,k) = 4*T(n-1,k) + T(n-2,k-2) for k>=1. - Philippe Deléham, Feb 02 2012

Vertical recurrence: T(n,k) = 1*T(n-1,k-1) + 2*T(n-2,k-1) + 6*T(n-3,k-1) + 20*T(n-4,k-1) + ... for k >= 1 (the coefficients 1, 2, 6, 20, ... are the central binomial coefficients A000984). - Peter Bala, Oct 17 2015

A006295 Number of genus 1 rooted maps with 2 faces with n vertices.

Original entry on oeis.org

10, 167, 1720, 14065, 100156, 649950, 3944928, 22764165, 126264820, 678405090, 3550829360, 18182708362, 91392185080, 452077562620, 2205359390592, 10627956019245, 50668344988068, 239250231713210, 1120028580999440, 5202779260636958, 23998704563581000, 109991785264412452

Offset: 3

N. J. A. Sloane

nonn

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
T. R. S. Walsh, Combinatorial Enumeration of Non-Planar Maps. Ph.D. Dissertation, Univ. of Toronto, 1971.

Vincenzo Librandi, Table of n, a(n) for n = 3..1000
W. T. Tutte, On the enumeration of planar maps, Bull. Amer. Math. Soc. 74 1968 64-74.
T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus, J. Comb. Thy B13 (1972), 122-141 and 192-218.
Notes

Rooted maps of genus 1 with n edges and f faces for 1<=f<=10: A002802(with offset 2) f=1, this sequence, A006296 f=3, A288071 f=4, A288072 f=5, A287046 f=6, A287047 f=7, A287048 f=8, A288073 f=9, A288074 f=10.

Column 2 of A269921, column 1 of A270406.

Rest[CoefficientList[Series[(1 - Sqrt[1 - 4 x]) (11 + 12 x + 9 Sqrt[1 - 4 x]) / (4 (4 x - 1)^4), {x, 0, 40}], x]] (* Vincenzo Librandi, Jun 06 2017 *)

A000108_ser(N) = my(x='x+O('x^(N+1))); (1 - sqrt(1-4*x))/(2*x);
A006295_ser(N) = {
  my(y = A000108_ser(N+1));  y*(y-1)^3*(y^2 + 15*y - 6)/(y-2)^8;
};
Vec(A006295_ser(31)) \\ Gheorghe Coserea, Jun 04 2017

my(x = 'x + O('x^60)); Vec(x*(1-sqrt(1-4*x))*(11+12*x+9*sqrt(1-4*x))/(4*(4*x-1)^4)) \\ Michel Marcus, Jun 05 2017

G.f.: x*(1-sqrt(1-4*x))*(11+12*x+9*sqrt(1-4*x))/(4*(4*x-1)^4). - Sean A. Irvine, Nov 14 2010

More terms from Sean A. Irvine, Nov 14 2010

A006296 Number of genus 1 rooted maps with 3 faces with n vertices.

Original entry on oeis.org

70, 1720, 24164, 256116, 2278660, 17970784, 129726760, 875029804, 5593305476, 34225196720, 201976335288, 1156128848680, 6447533938280, 35155923872640, 187959014565840, 987658610225052, 5110652802256260, 26084524995672080, 131501187454625560, 655590388845975000, 3235463376771463288, 15820770680078552000, 76708503479715247920, 369046200766330733880, 1762793459781859039080, 8364468224596427692896, 39445646133672676352560, 184956513528952419546448, 862615498961026097997392, 4003067488703222112053760, 18489846573354278755829152, 85028133934182275077421180, 389398354121840111751946628, 1776360539933013004774353872, 8073622060225813990245976280, 36567311475673299914222851832

Offset: 4

N. J. A. Sloane

nonn

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
T. R. S. Walsh, Combinatorial Enumeration of Non-Planar Maps. Ph.D. Dissertation, Univ. of Toronto, 1971.

Vincenzo Librandi, Table of n, a(n) for n = 4..1000
T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus, J. Comb. Thy B13 (1972), 122-141 and 192-218.
Notes

Rooted maps of genus 1 with n edges and f faces for 1<=f<=10: A002802(with offset 2) f=1, A006295 f=2, this sequence, A288071 f=4, A288072 f=5, A287046 f=6, A287047 f=7, A287048 f=8, A288073 f=9, A288074 f=10.

Column 3 of A269921, column g=1 of A270407.

Rest[CoefficientList[Series[(1 - Sqrt[1 - 4 x]) (45 + 152 x + (25 + 8 x) Sqrt[1 - 4 x]) / (2 (1 - 4 x)^(11 / 2)), {x, 0, 40}], x]] (* Vincenzo Librandi, Jun 06 2017 *)

A000108_ser(N) = my(x='x+O('x^(N+1))); (1 - sqrt(1-4*x))/(2*x);
A006296_ser(N) = {
  my(y = A000108_ser(N+1));
  -2*y*(y-1)^4*(10*y^3 + 97*y^2 - 64*y - 8)/(y-2)^11;
};
Vec(A006296_ser(36)) \\ Gheorghe Coserea, Jun 04 2017

G.f.: x(1-sqrt(1-4*x))(45+152*x+(25+8*x)sqrt(1-4*x))/(2(1-4*x)^(11/2)). - Sean A. Irvine, Nov 14 2010

More terms from Sean A. Irvine, Nov 14 2010

A020920 Expansion of 1/(1-4*x)^(9/2).

Original entry on oeis.org

1, 18, 198, 1716, 12870, 87516, 554268, 3325608, 19122246, 106234700, 573667380, 3024791640, 15628090140, 79342611480, 396713057400, 1957117749840, 9540949030470, 46021048264620, 219878341708740, 1041528987041400, 4895186239094580, 22844202449108040

Offset: 0

N. J. A. Sloane

Also convolution of A000984 with A038846, also convolution of A000302 with A020918, also convolution of A002457 with A038845, also convolution of A002697 with A002802. - Rui Duarte, Oct 08 2011

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Cf. A000302, A000332, A000984, A001622, A002457, A002697, A002802, A020918, A038845, A038846, A046521 (fifth column).

List([0..30], n-> Binomial(n+4, 4)*Binomial(2*(n+4), n+4)/70) # G. C. Greubel, Jul 20 2019

[(2*n+7)*(2*n+5)*(2*n+3)*(2*n+1)*Binomial(2*n, n)/105: n in [0..30]]; // Vincenzo Librandi, Jul 05 2013

seq(binomial(2*n+8, n+4)*binomial(n+4, n)/70, n=0..30); # Zerinvary Lajos, May 05 2007

CoefficientList[Series[1/(1-4x)^(9/2), {x,0,30}], x] (* Vincenzo Librandi, Jul 05 2013 *)

vector(30, n, n--; m=n+4; binomial(m, 4)*binomial(2*m, m)/70) \\ G. C. Greubel, Jul 20 2019

[binomial(n+4, 4)*binomial(2*(n+4), n+4)/70 for n in (0..30)] # G. C. Greubel, Jul 20 2019

a(n) = binomial(n+4, 4)*A000984(n+4)/A000984(4), where A000984 are the central binomial coefficients. - Wolfdieter Lang
a(n) = Sum_{ a+b+c+d+e+f+g+h+i=n} f(a)*f(b)*f(c)*f(d)*f(e)*f(f)*f(g) *f(h)*f(i) with f(n)=A000984(n). - Philippe Deléham, Jan 22 2004
a(n) = A000332(n+4)*A000984(n+4)/70. - Zerinvary Lajos, May 05 2007
From Rui Duarte, Oct 08 2011: (Start)
a(n) = ((2n+7)(2n+5)(2n+3)(2n+1)/(7*5*3*1)) * binomial(2n, n).
a(n) = binomial(2n+8, 8) * binomial(2n, n) / binomial(n+4, 4).
a(n) = binomial(n+4, 4) * binomial(2n+8, n+4) / binomial(8, 4). (End)
Boas-Buck recurrence: a(n) = (18/n)*Sum_{k=0..n-1} 4^(n-k-1)*a(k), n >= 1, a(0) = 1. Proof from a(n) = A046521(n+4, 4). See a comment there.
From Amiram Eldar, Mar 25 2022: (Start)
Sum_{n>=0} 1/a(n) = 1148/5 - 42*sqrt(3)*Pi.
Sum_{n>=0} (-1)^n/a(n) = 700*sqrt(5)*log(phi) - 11284/15, where phi is the golden ratio (A001622). (End)

A068763 Irregular triangle of the Fibonacci polynomials of A011973 multiplied diagonally by the Catalan numbers.

Original entry on oeis.org

1, 1, 1, 2, 2, 5, 6, 1, 14, 20, 6, 42, 70, 30, 2, 132, 252, 140, 20, 429, 924, 630, 140, 5, 1430, 3432, 2772, 840, 70, 4862, 12870, 12012, 4620, 630, 14, 16796, 48620, 51480, 24024, 4620, 252, 58786, 184756, 218790

Offset: 0

Wolfdieter Lang, Mar 04 2002

The row length sequence of this array is [1,2,2,3,3,4,4,5,5,...] = A008619(n+2), n>=0.
The row polynomials p(n,x) := Sum_{m=0..floor((n+1)/2)} a(n,m)*x^m produce, for x = (b-a^2)/a^2 (not 0), the two parameter family of sequences K(a,b; n) := (a^(n+1))*p(n,(b-a^2)/a^2) with g.f. K(a,b; x) := (1-sqrt(1-4*x*(a+x*(b-a^2))))/(2*x).
Some members are: K(1,1; n)=A000108(n) (Catalan), K(1,2; n)=A025227(n-1), K(2,1; n)=A025228(n-1), K(1,3; n)=A025229(n-1), K(3,1; n)=A025230(n-1). For a=b=2..10 the sequences K(a,a; n)/a are A068764-A068772.
The column sequences (without leading 0's) are: A000108 (Catalan), A000984 (central binomial), A002457, 2*A002802, 5*A020918, 14*A020920, 42*A020922, ...
a(n,m) is the number of ways to designate exactly m cherries over all binary trees with n internal nodes.  A cherry is an internal node whose descendants are both external nodes.  Cf. A091894 which gives the number of binary trees with m cherries. - Geoffrey Critzer, Jul 24 2020
This irregular triangle is essentially that of A011973 with its diagonals multiplied by the Catalan numbers of A000108. The diagonals of this triangle are then rows of the Pascal matrix A007318 multiplied by the Catalan numbers. - Tom Copeland, Dec 23 2023

			The irregular triangle begins:
   n\m    0     1     2     3    4   5
   0:     1
   1:     1     1
   2:     2     2
   3:     5     6     1
   4:    14    20     6
   5:    42    70    30     2
   6:   132   252   140    20
   7:   429   924   630   140    5
   8:  1430  3432  2772   840   70
   9:  4862 12870 12012  4620  630  14
  10: 16796 48620 51480 24024 4620 252
  ...
p(3,x) = 5 + 6*x + x^2.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 213.
Tad White, Quota Trees, arXiv:2401.01462 [math.CO], 2024. See p. 20.

Cf. A025227(n-1) (row sums).
Cf. A000007(n) (alternating row sums).
Cf. A000108, A001263, A007318, A011973, A033832, A034867, A133437 and A134264.

nn = 10; b[z_] := (1 - Sqrt[1 - 4 z])/(2 z);Map[Select[#, # > 0 &] &,
CoefficientList[Series[v b[v z] /. v -> (1 + u z ), {z, 0, nn}], {z, u}]] // Grid (* Geoffrey Critzer, Jul 24 2020 *)

a(n, m) = binomial(n+1-m, m)*C(n-m) if 0 <= m <= floor((n+1)/2), otherwise 0, with C(n) := A000108(n) (Catalan).
G.f. for column m=1, 2, ...: (x^(2*m-1))*C(m-1)/(1-4*x)^((2*m-1)/2); m=0: c(x), g.f. for A000108 (Catalan).
G.f. for row polynomials p(n, x): c(z) + x*z*c(x*(z^2)/(1-4*z))/sqrt(1-4*z) = (1-sqrt(1-4*z*(1+x*z)))/(2*z), where c(x) is the g.f. of A000108 (Catalan).
G.f. for triangle: (1 - sqrt(1 - 4*x (1 + y*x)))/(2*x). - Geoffrey Critzer, Jul 24 2020
The alternating row sums are {1,repeat 0} = {A000007(n)}{n>=0}. From the second comment p(n, x=-1) = K(1,0; n), with g.f. K(1,0; x) = 1. Or from the g.f. of the triangle with y = -1. Thanks to Aaron Li for asking for a proof. - _Wolfdieter Lang, Jan 21 2023
The series expansion of f(x) = (1 + 2sx - sqrt(1 + 4sx + 4d^2x^2))/(2x) at x = 0 is (s^2 - d^2) x + (2 d^2s - 2 s^3) x^2 + (d^4 - 6 d^2 s^2 + 5 s^4) x^3  + (-6 d^4 s + 20 d^2 s^3 - 14 s^5) x^4 + ..., containing the coefficients of this array. With s = (a+b)/2 and d = (a-b)/2, then f(x)/ab = g(x) = (1 + (a+b)x - sqrt((1+(a+b)x)^2 - 4abx^2))/(2abx) = x - (a + b) x^2 + (a^2 + 3 a b + b^2) x^3 - (a^3 + 6 a^2 b + 6 a b^2 + b^3) x^4 + ..., containing the Narayana polynomials of A001263, which can be simply transformed into A033282. The compositional inverse about the origin of g(x) is g^(-1)(x) = x/((1-ax)(1-bx)) = x/((1-(s+d)x)(1-(s-d)x)) = x + (a + b) x^2 + (a^2 + a b + b^2) x^3 + (a^3 + a^2 b + a b^2 + b^3) x^4 + ..., containing the complete homogeneous symmetric polynomials h_n(a,b) = (a^n - b^n)/(a-b), which are the polynomials of A034867 when expressed in s and d, e.g., ((s + d)^7 - (s - d)^7)/(2 d) = d^6 + 21 d^4 s^2 + 35 d^2 s^4 + 7 s^6. A133437 and A134264 for compositional inversion of o.g.f.s can be used to relate the sets of polynomials above. - Tom Copeland, Nov 28 2023

Title changed by Tom Copeland, Dec 23 2023

A177267 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having genus k (see first comment for definition of genus).

Original entry on oeis.org

1, 2, 0, 5, 1, 0, 14, 10, 0, 0, 42, 70, 8, 0, 0, 132, 420, 168, 0, 0, 0, 429, 2310, 2121, 180, 0, 0, 0, 1430, 12012, 20790, 6088, 0, 0, 0, 0, 4862, 60060, 174174, 115720, 8064, 0, 0, 0, 0, 16796, 291720, 1309308, 1624480, 386496, 0, 0, 0, 0, 0, 58786, 1385670, 9087078, 18748730, 10031736, 604800, 0, 0, 0, 0, 0, 208012, 6466460, 59306676, 188208020, 186698512, 38113920, 0

Offset: 1

Emeric Deutsch, May 27 2010

The genus g(p) of a permutation p of {1,2,...,n} is defined by g(p)=(1/2)[n+1-z(p)-z(cp')], where p' is the inverse permutation of p, c = 234...n1 = (1,2,...,n), and z(q) is the number of cycles of the permutation q.
The sum of the entries in row n is n!.
The number of nonzero entries in row n is floor((n+1)/2).
T(n,0) = A000108(n) (the Catalan numbers).
Apparently T(n,1) = A002802(n-3).
Last nonzero terms in rows with odd n appear to be A060593. [Joerg Arndt, Nov 01 2012.]

			T(3,1)=1 because 312 is the only permutation of {1,2,3} with genus 1 (we have p=312=(132), cp'=231*231=312=(132) and so g(p)=(1/2)(3+1-1-1)=1).
Triangle starts:
[ 1]  1,
[ 2]  2, 0,
[ 3]  5, 1, 0,
[ 4]  14, 10, 0, 0,
[ 5]  42, 70, 8, 0, 0,
[ 6]  132, 420, 168, 0, 0, 0,
[ 7]  429, 2310, 2121, 180, 0, 0, 0,
[ 8]  1430, 12012, 20790, 6088, 0, 0, 0, 0,
[ 9]  4862, 60060, 174174, 115720, 8064, 0, 0, 0, 0,
[10]  16796, 291720, 1309308, 1624480, 386496, 0, 0, 0, 0, 0,
[11]  58786, 1385670, 9087078, 18748730, 10031736, 604800, 0, 0, ...,
[12]  208012, 6466460, 59306676, 188208020, 186698512, 38113920, 0, ...,
[13]  742900, 29745716, 368588220, 1700309468, 2788065280, 1271140416, 68428800, 0, ...,
...

S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8, 1998, 169-191.

Alois P. Heinz, Rows n = 1..141, flattened

Cf. A178514 (genus of derangements), A178515 (genus of involutions), A178516 (genus of up-down permutations), A178517 (genus of non-derangement permutations), A178518 (permutations of [n] having genus 0 and p(1)=k), A185209 (genus of connected permutations), A218538 (genus of permutations avoiding [x,x+1]).
Row sums give A000142.
T(2n+1,n) gives A060593.
Cf. A000108, A002802.

n := 8: with(combinat): P := permute(n): inv := proc (p) local j, q: for j to nops(p) do q[p[j]] := j end do: [seq(q[i], i = 1 .. nops(p))] end proc: nrcyc := proc (p) local nrfp, pc: nrfp := proc (p) local ct, j: ct := 0: for j to nops(p) do if p[j] = j then ct := ct+1 else end if end do: ct end proc: pc := convert(p, disjcyc): nops(pc)+nrfp(p) end proc: b := proc (p) local c: c := [seq(i+1, i = 1 .. nops(p)-1), 1]: [seq(c[p[j]], j = 1 .. nops(p))] end proc: gen := proc (p) options operator, arrow: (1/2)*nops(p)+1/2-(1/2)*nrcyc(p)-(1/2)*nrcyc(b(inv(p))) end proc: f[n] := sort(add(t^gen(P[j]), j = 1 .. factorial(n))): seq(coeff(f[n], t, j), j = 0 .. ceil((1/2)*n)-1); # yields the entries in the specified row n
# second Maple program:
b:= proc(n) option remember; `if`(n<2, 1, ((4*n-2)*
      b(n-1)+(n-2)*(n-1)^2*expand(x*b(n-2)))/(n+1))
    end:
T:= (n, k)-> coeff(b(n), x, k):
seq(seq(T(n, k), k=0..n-1), n=1..12);  # Alois P. Heinz, Feb 16 2024

T[ n_, k_] := If[ n < 1 || k >= n, 0, Module[{pn = Table[i, {i, n}]}, Do[ pn[[i]] = ((4 i - 2) pn[[i - 1]] + x (i - 2) (i - 1)^2 pn[[i - 2]])/(i + 1) // Expand, {i, 3, n}]; Coefficient[pn[[n]], x, k]]]; (* Michael Somos, Sep 02 2017 *)

Let p(n, x) := g.f. of row n. Then (n+1) * p(n, x) = (4*n-2) * p(n-1, x) + x * (n-2) * (n-1)^2 * p(n-2, x). - Michael Somos, Sep 02 2017

Terms for rows 12 and 13 from Joerg Arndt, Jan 24 2011.

A287046 a(n) is the number of rooted maps with n edges and 6 faces on an orientable surface of genus 1.

Original entry on oeis.org

12012, 649950, 17970784, 344468530, 5188948072, 65723863196, 729734918432, 7302676928666, 67173739068760, 576218752277476, 4660202610532480, 35839052357422132, 263868150558327376, 1870153808268516280, 12816868756802256832, 85256107136168684650, 552171259884681058744

Offset: 7

Gheorghe Coserea, Jun 04 2017

nonn

Sean R. Carrell and Guillaume Chapuy, Simple recurrence formulas to count maps on orientable surfaces, arXiv:1402.6300 [math.CO], 2014.
Sean R. Carrell and Guillaume Chapuy, Simple recurrence formulas to count maps on orientable surfaces, Journal of Combinatorial Theory, Series A, 133 (2015), 58-75.

Rooted maps of genus 1 with n edges and f faces for 1<=f<=10: A002802(with offset 2) f=1, A006295 f=2, A006296 f=3, A288071 f=4, A288072 f=5, this sequence, A287047 f=7, A287048 f=8, A288073 f=9, A288074 f=10.
Column 6 of A269921, column 1 of A270410.
Cf. A000108.

Q[0, 1, 0] = 1; Q[n_, f_, g_] /; n < 0 || f < 0 || g < 0 = 0;
Q[n_, f_, g_] := Q[n, f, g] = 6/(n + 1) ((2 n - 1)/3 Q[n - 1, f, g] + (2 n - 1)/3 Q[n - 1, f - 1, g] + (2 n - 3) (2 n - 2) (2 n - 1)/12 Q[n - 2, f, g - 1] + 1/2 Sum[l = n - k; Sum[v = f - u; Sum[j = g - i; Boole[l >= 1 && v >= 1 && j >= 0] (2 k - 1) (2 l - 1) Q[k - 1, u, i] Q[l - 1, v, j], {i, 0, g}], {u, 1, f}], {k, 1, n}]);
a[n_] := Q[n, 6, 1];
Table[a[n], {n, 7, 23}] (* Jean-François Alcover, Oct 17 2018 *)

A000108_ser(N) = my(x='x+O('x^(N+1))); (1 - sqrt(1-4*x))/(2*x);
A287046_ser(N) = {
  my(y = A000108_ser(N+1));
  2*y*(y-1)^7*(28457*y^6 + 179171*y^5 - 222214*y^4 - 172512*y^3 + 257232*y^2 - 59904*y - 4224)/(y-2)^20;
};
Vec(A287046_ser(17))

A287047 a(n) is the number of rooted maps with n edges and 7 faces on an orientable surface of genus 1.

Original entry on oeis.org

60060, 3944928, 129726760, 2908358552, 50534154408, 729734918432, 9145847808784, 102432266545800, 1046677747672360, 9908748651241088, 87930943305742512, 738178726378902064, 5905479331377981200, 45289976937922983360, 334600965220354244896, 2391127223524518889064, 16585285393291515557928

Offset: 8

Gheorghe Coserea, Jun 04 2017

nonn

Sean R. Carrell, Guillaume Chapuy, Simple recurrence formulas to count maps on orientable surfaces, arXiv:1402.6300 [math.CO], 2014.

Rooted maps of genus 1 with n edges and f faces for 1<=f<=10: A002802(with offset 2) f=1, A006295 f=2, A006296 f=3, A288071 f=4, A288072 f=5, A287046 f=6, this sequence, A287048 f=8, A288073 f=9, A288074 f=10.
Column 7 of A269921, column 1 of A270411.
Cf. A000108.

Q[0, 1, 0] = 1; Q[n_, f_, g_] /; n < 0 || f < 0 || g < 0 = 0;
Q[n_, f_, g_] := Q[n, f, g] = 6/(n + 1) ((2 n - 1)/3 Q[n - 1, f, g] + (2 n - 1)/3 Q[n - 1, f - 1, g] + (2 n - 3) (2 n - 2) (2 n - 1)/12 Q[n - 2, f, g - 1] + 1/2 Sum[l = n - k; Sum[v = f - u; Sum[j = g - i; Boole[l >= 1 && v >= 1 && j >= 0] (2 k - 1) (2 l - 1) Q[k - 1, u, i] Q[l - 1, v, j], {i, 0, g}], {u, 1, f}], {k, 1, n}]);
a[n_] := Q[n, 7, 1];
Table[a[n], {n, 8, 24}] (* Jean-François Alcover, Oct 18 2018 *)

A000108_ser(N) = my(x='x+O('x^(N+1))); (1 - sqrt(1-4*x))/(2*x);
A287047_ser(N) = {
  my(y = A000108_ser(N+1));
  -4*y*(y-1)^8*(184142*y^7 + 1083793*y^6 - 1540136*y^5 - 1481152*y^4 + 2626176*y^3 - 737232*y^2 - 184896*y + 64320)/(y-2)^23;
};
Vec(A287047_ser(17))

A287048 a(n) is the number of rooted maps with n edges and 8 faces on an orientable surface of genus 1.

Original entry on oeis.org

291720, 22764165, 875029804, 22620890127, 448035881592, 7302676928666, 102432266545800, 1274461449989715, 14373136466094880, 149314477245194262, 1446563778096423816, 13196809961724011350, 114253624700659216080, 944690705838217837620, 7498935691376059259344, 57398464959432306918747

Offset: 9

Gheorghe Coserea, Jun 04 2017

nonn

Sean R. Carrell, Guillaume Chapuy, Simple recurrence formulas to count maps on orientable surfaces, arXiv:1402.6300 [math.CO], 2014.

Rooted maps of genus 1 with n edges and f faces for 1<=f<=10: A002802(with offset 2) f=1, A006295 f=2, A006296 f=3, A288071 f=4, A288072 f=5, A287046 f=6, A287047 f=7, this sequence, A288073 f=9, A288074 f=10.
Column 8 of A269921; column 1 of A270412.
Cf. A000108.

Q[0, 1, 0] = 1; Q[n_, f_, g_] /; n < 0 || f < 0 || g < 0 = 0;
Q[n_, f_, g_] := Q[n, f, g] = 6/(n + 1) ((2 n - 1)/3 Q[n - 1, f, g] + (2 n - 1)/3 Q[n - 1, f - 1, g] + (2 n - 3) (2 n - 2) (2 n - 1)/12 Q[n - 2, f, g - 1] + 1/2 Sum[l = n - k; Sum[v = f - u; Sum[j = g - i; Boole[l >= 1 && v >= 1 && j >= 0] (2 k - 1) (2 l - 1) Q[k - 1, u, i] Q[l - 1, v, j], {i, 0, g}], {u, 1, f}], {k, 1, n}]);
a[n_] := Q[n, 8, 1];
Table[a[n], {n, 9, 25}] (* Jean-François Alcover, Oct 18 2018 *)

A000108_ser(N) = my(x='x+O('x^(N+1))); (1 - sqrt(1-4*x))/(2*x);
A287048_ser(N) = {
  my(y = A000108_ser(N+1));
  y*(y-1)^9*(9370183*y^8 + 52321971*y^7 - 83853806*y^6 - 93946092*y^5 + 189910936*y^4 - 57493776*y^3 - 31383264*y^2 + 16878912*y - 1513344)/(y-2)^26;
};
Vec(A287048_ser(16))

Previous Showing 11-20 of 46 results. Next

cp's OEIS Frontend

A035309 Triangle read by rows giving number of ways to glue sides of a 2n-gon so as to produce a surface of genus g.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A054335 A convolution triangle of numbers based on A000984 (central binomial coefficients of even order).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A006295 Number of genus 1 rooted maps with 2 faces with n vertices.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A006296 Number of genus 1 rooted maps with 3 faces with n vertices.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A020920 Expansion of 1/(1-4*x)^(9/2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A068763 Irregular triangle of the Fibonacci polynomials of A011973 multiplied diagonally by the Catalan numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica