A194560 G.f.: Sum_{n>=1} G_n(x)^n where G_n(x) = x + x*G_n(x)^n.

1, 2, 2, 4, 2, 10, 2, 20, 14, 49, 2, 217, 2, 438, 310, 1580, 2, 6352, 2, 18062, 7824, 58799, 2, 258971, 2532, 742915, 246794, 2729095, 2, 11154954, 2, 35779660, 8414818, 129644809, 242354, 531132915, 2, 1767263211, 300830821, 6593815523, 2, 26289925026, 2, 91708135773

Offset: 1

Author

Paul D. Hanna, Aug 28 2011

Keywords

• nonn

Comments

Number of Dyck n-paths with all ascents of equal length. - David Scambler, Nov 17 2011

From Gus Wiseman, Feb 15 2019: (Start)

Also the number of uniform (all blocks have the same size) non-crossing set partitions of {1,...,n}. For example, the a(3) = 2 through a(6) = 10 uniform non-crossing set partitions are:

{{123}} {{1234}} {{12345}} {{123456}}

{{1}{2}{3}} {{12}{34}} {{1}{2}{3}{4}{5}} {{123}{456}}

{{14}{23}} {{126}{345}}

{{1}{2}{3}{4}} {{156}{234}}

{{12}{34}{56}}

{{12}{36}{45}}

{{14}{23}{56}}

{{16}{23}{45}}

{{16}{25}{34}}

{{1}{2}{3}{4}{5}{6}}

(End)

Examples

			G.f.: A(x) = x + 2*x^2 + 2*x^3 + 4*x^4 + 2*x^5 + 10*x^6 + 2*x^7 + ...
where
A(x) = G_1(x) + G_2(x)^2 + G_3(x)^3 + G_4(x)^4 + G_5(x)^5 + ...
and G_n(x) = x + x*G_n(x)^n is given by:
G_n(x) = Sum_{k>=0} C(n*k+1,k)/(n*k+1)*x^(n*k+1),
G_n(x)^n = Sum_{k>=1} C(n*k,k)/(n*k-k+1)*x^(n*k);
the first few expansions of G_n(x)^n begin:
G_1(x) = x + x^2 + x^3 + x^4 + x^5 + ...
G_2(x)^2 = x^2 + 2*x^4 + 5*x^6 + 14*x^8 + ... + A000108(n)*x^(2*n) + ...
G_3(x)^3 = x^3 + 3*x^6 + 12*x^9 + 55*x^12 + ... + A001764(n)*x^(3*n) + ...
G_4(x)^4 = x^4 + 4*x^8 + 22*x^12 + 140*x^16 + ... + A002293(n)*x^(4*n) + ...
G_5(x)^5 = x^5 + 5*x^10 + 35*x^15 + 285*x^20 + ... + A002294(n)*x^(5*n) + ...
		

Links

• Paul D. Hanna, Table of n, a(n) for n = 1..1000
• Eric Weisstein's World of Mathematics, Dyck Path.
• Wikipedia, Noncrossing partition.

Crossrefs

Row sums of A306437.

Cf. A000108, A001263, A001764, A016098, A038041, A061095, A125181, A134264, A194558, A306418, A306438.

Programs

Mathematica

Table[Sum[Binomial[n,d]/(n-d+1),{d,Divisors[n]}],{n,20}] (* Gus Wiseman, Feb 15 2019 *)

PARI

{a(n)=if(n<1,0,sumdiv(n,d,binomial(n,d)/(n-d+1)))}

PARI

{a(n)=polcoeff(sum(m=1,n,serreverse(x/(1+x^m+x*O(x^n)))^m),n)}

Formula

a(n) = Sum_{d|n} C(n,d)/(n-d+1).

G.f.: Sum_{n>=1} Series_Reversion( x/(1+x^n) )^n.