A056711 -id:A056711

Search: a056711 -id:a056711

Displaying 1-2 of 2 results found.

page 1

A275431

Triangle read by rows: T(n,k) = number of ways to insert n pairs of parentheses in k words.

+10
6

1, 2, 1, 5, 2, 1, 14, 8, 2, 1, 42, 24, 8, 2, 1, 132, 85, 28, 8, 2, 1, 429, 286, 100, 28, 8, 2, 1, 1430, 1008, 358, 105, 28, 8, 2, 1, 4862, 3536, 1309, 378, 105, 28, 8, 2, 1, 16796, 12618, 4772, 1410, 384, 105, 28, 8, 2, 1, 58786, 45220, 17556, 5220, 1435, 384, 105, 28, 8, 2, 1

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

Multiset transformation of A000108. Each word is dissected by a number of parentheses associated to its length.

Also the number of forests of exactly k (unlabeled) ordered rooted trees with a total of n non-root nodes where each tree has at least 1 non-root node. - Alois P. Heinz, Sep 20 2017

LINKS

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

Index entries for triangles generated by the Multiset Transformation

FORMULA

T(n,1) = A000108(n).

T(n,k) = Sum_{c_i*N_i=n,i=1..k} binomial(T(N_i,1)+c_i-1,c_i) for 1<k<=n.

G.f.: Product_{j>=1} 1/(1-y*x^j)^A000108(j). - Alois P. Heinz, Apr 13 2017

EXAMPLE

2 1

5 2 1

14 8 2 1

42 24 8 2 1

132 85 28 8 2 1

429 286 100 28 8 2 1

1430 1008 358 105 28 8 2 1

4862 3536 1309 378 105 28 8 2 1

16796 12618 4772 1410 384 105 28 8 2 1

58786 45220 17556 5220 1435 384 105 28 8 2 1

MAPLE

C:= proc(n) option remember; binomial(2*n, n)/(n+1) end:

b:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1,

`if`(min(i, p)<1, 0, add(b(n-i*j, i-1, p-j)*

binomial(C(i)+j-1, j), j=0..min(n/i, p)))))

end:

T:= (n, k)-> b(n$2, k):

seq(seq(T(n, k), k=1..n), n=1..12); # Alois P. Heinz, Apr 13 2017

MATHEMATICA

c[n_] := c[n] = Binomial[2*n, n]/(n + 1);

b[n_, i_, p_] := b[n, i, p] = If[p > n, 0, If[n == 0, 1, If[Min[i, p] < 1, 0, Sum[b[n - i*j, i - 1, p - j]*Binomial[c[i] + j - 1, j], {j, 0, Min[n/i, p]}]]]];

T[n_, k_] := b[n, n, k];

Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, May 18 2018, after Alois P. Heinz *)

CROSSREFS

Cf. A000108 (1st column), A007223 (2nd column), A056711 (3rd column), A088327 (row sums).

T(2n,n) gives A292668.

KEYWORD

nonn,tabl

AUTHOR

R. J. Mathar, Jul 27 2016

STATUS

approved

A046342

Number of 3-bead necklaces where each bead is a planted trivalent plane tree [or anything else enumerated by the Catalan numbers], by total number of nodes.

+10
3

1, 1, 3, 8, 24, 74, 245, 815, 2796, 9707, 34186, 121562, 436298, 1577310, 5740299, 21008777, 77279892, 285544700, 1059332082, 3944254118, 14734260864, 55207053787, 207421476390, 781283558998, 2949675307082, 11160264942376, 42309912978708, 160700303600030

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

With offset = 3, a(n) is the number of forests having exactly three rooted plane trees with n total nodes. - Geoffrey Critzer, Feb 22 2013

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000

FORMULA

Plug g.f. for A000108, 1/2*(1-(1-4*x)^(1/2))/x, into cycle index for dihedral group D_6.

Cycle index for D_6: 1/6*Z[1]^3+1/2*Z[1]*Z[2]+1/3*Z[3].

a(n) = Sum_{j=0..3} A275431(n,j). - Alois P. Heinz, Sep 20 2017

MATHEMATICA

nn=30; Drop[CoefficientList[Series[ CycleIndex[SymmetricGroup[3], s]/.Table[s[i]->(1-(1-4x^i)^(1/2))/2, {i, 1, nn}], {x, 0, nn}], x], 3] (* Geoffrey Critzer, Feb 22 2013 *)

CROSSREFS

See A058855 (a 6-bead analog) for details.

Cf. A000108, A058855, A056711, A275431.

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Jan 19 2001

STATUS

approved

page 1

Search completed in 0.009 seconds