| Displaying 1-4 of 4 results found.
page
1
Square array A(n,k) by antidiagonals. A(n,k) is the number of length 2n k-ary words (n,k>=0) that can be built by repeatedly inserting doublets into the initially empty word.
+10
15
1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 6, 1, 0, 1, 4, 15, 20, 1, 0, 1, 5, 28, 87, 70, 1, 0, 1, 6, 45, 232, 543, 252, 1, 0, 1, 7, 66, 485, 2092, 3543, 924, 1, 0, 1, 8, 91, 876, 5725, 19864, 23823, 3432, 1, 0, 1, 9, 120, 1435, 12786, 71445, 195352, 163719, 12870, 1, 0
COMMENTS
A(n,k) is also the number of rooted closed walks of length 2n on the infinite rooted k-ary tree. - Danny Rorabaugh, Oct 31 2017 A(n,2k) is the number of unreduced words of length 2n that reduce to the empty word in the free group with k generators. - Danny Rorabaugh, Nov 09 2017
FORMULA
A(n,k) = k/n * Sum_{j=0..n-1} C(2*n,j)*(n-j)*(k-1)^j if n>0, A(0,k) = 1.
A(n,k) = A183134(n,k) if n=0 or k<2, A(n,k) = A183134(n,k)*k otherwise. G.f. of column k: 1/(1-k*x) if k<2, 2*(k-1)/(k-2+k*sqrt(1-(4*k-4)*x)) otherwise.
EXAMPLE
A(2,2) = 6, because 6 words of length 4 can be built over 2-letter alphabet {a, b} by repeatedly inserting doublets (words with two equal letters) into the initially empty word: aaaa, aabb, abba, baab, bbaa, bbbb.
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, ...
0, 1, 2, 3, 4, 5, ...
0, 1, 6, 15, 28, 45, ...
0, 1, 20, 87, 232, 485, ...
0, 1, 70, 543, 2092, 5725, ...
0, 1, 252, 3543, 19864, 71445, ...
MAPLE
A:= proc(n, k) local j;
if n=0 then 1
else k/n *add(binomial(2*n, j) *(n-j) *(k-1)^j, j=0..n-1)
fi
end:
seq(seq(A(n, d-n), n=0..d), d=0..10);
MATHEMATICA
A[_, 1] = 1; A[n_, k_] := If[n == 0, 1, k/n*Sum[Binomial[2*n, j]*(n - j)*(k - 1)^j, {j, 0, n - 1}]]; Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Dec 27 2013, translated from Maple *)
CROSSREFS
Columns k=0-10 give: A000007, A000012, A000984, A089022, A035610, A130976, A130977, A130978, A130979, A130980, A131521. Coefficients of row polynomials in k, (k-1) are given by A157491, A039599.
Number T(n,k) of length 2n words such that all letters of the k-ary alphabet occur at least once and are introduced in ascending order and which can be built by repeatedly inserting doublets into the initially empty word; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
+10
14
1, 0, 1, 0, 1, 2, 0, 1, 9, 5, 0, 1, 34, 56, 14, 0, 1, 125, 465, 300, 42, 0, 1, 461, 3509, 4400, 1485, 132, 0, 1, 1715, 25571, 55692, 34034, 7007, 429, 0, 1, 6434, 184232, 657370, 647920, 231868, 32032, 1430, 0, 1, 24309, 1325609, 7488228, 11187462, 6191808, 1447992, 143208, 4862
COMMENTS
In general, column k>2 is asymptotic to (4*(k-1))^n / ((k-2)^2 * (k-2)! * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jun 01 2015
FORMULA
T(n,k) = Sum_{i=0..k} (-1)^i * A183135(n,k-i) / (i!*(k-i)!). T(n,k) = A256116(n,k) / (k-1)! for k > 0.
EXAMPLE
T(0,0) = 1: (the empty word).
T(1,1) = 1: aa.
T(2,1) = 1: aaaa.
T(2,2) = 2: aabb, abba.
T(3,1) = 1: aaaaaa.
T(3,2) = 9: aaaabb, aaabba, aabaab, aabbaa, aabbbb, abaaba, abbaaa, abbabb, abbbba.
T(3,3) = 5: aabbcc, aabccb, abbacc, abbcca, abccba.
Triangle T(n,k) begins:
1;
0, 1;
0, 1, 2;
0, 1, 9, 5;
0, 1, 34, 56, 14;
0, 1, 125, 465, 300, 42;
0, 1, 461, 3509, 4400, 1485, 132;
0, 1, 1715, 25571, 55692, 34034, 7007, 429;
0, 1, 6434, 184232, 657370, 647920, 231868, 32032, 1430;
...
MAPLE
A:= proc(n, k) option remember; `if`(n=0, 1, k/n*
add(binomial(2*n, j)*(n-j)*(k-1)^j, j=0..n-1))
end:
T:= (n, k)-> add((-1)^i*A(n, k-i)/(i!*(k-i)!), i=0..k):
seq(seq(T(n, k), k=0..n), n=0..10);
MATHEMATICA
A[n_, k_] := A[n, k] = If[n == 0, 1, k/n*Sum[Binomial[2*n, j]*(n - j)*If[j == 0, 1, (k - 1)^j], {j, 0, n - 1}]];
T[n_, k_] := Sum[(-1)^i*A[n, k - i]/(i!*(k - i)!), {i, 0, k}];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Feb 22 2016, after Alois P. Heinz, updated Jan 01 2021 *)
CROSSREFS
Columns k=0-10 give: A000007, A057427, A010763(n-1) (for n>1), A258490, A258491, A258492, A258493, A258494, A258495, A258496, A258497.
a(n) = n! * Catalan(n+1).
+10
8
1, 2, 10, 84, 1008, 15840, 308880, 7207200, 196035840, 6094932480, 213322636800, 8303173401600, 355850288640000, 16653793508352000, 845180020548864000, 46236318771202560000, 2712530701243883520000, 169890080762116915200000, 11314679378756986552320000
COMMENTS
a(n) is the number of flags in the associahedron of dimension n. For example, there are a(2) = 10 flags in the associahedron of dimension 2, a pentagon. (In this case a flag corresponds to a triple v:e:f of a mutually incident vertex v, edge e, and face f, with f necessarily the unique face of the pentagon.)
Equivalently, a(n) is the number of maximal sequences of consistent parenthesizations of a string of n + 2 letters, starting with n + 1 pairs of parentheses, then removing one pair, and so on, ending with the trivial (outermost) parenthesization. For example, (a(b(cd))):(ab(cd)):(abcd) and (a(b(cd))):(a(bcd)):(abcd) are two of the a(2) = 10 maximal sequences of consistent parenthesizations of the letters abcd. (End)
REFERENCES
R. L. Graham, D. E. Knuth, and O. Patashnik, "Concrete Mathematics", Addison-Wesley, 1994, pp. 200-204.
FORMULA
a(n) = 2 * (2n+1)!/(n+2)!.
E.g.f.: (1-2*x-sqrt(1-4*x))/(2*x^2) = (O.g.f. for A000108)^2 = B_2(x)^2 (cf. GKP reference). 0 = a(n)*(-7200*a(n+2) + 2700*a(n+3) + 246*a(n+4) - 33*a(n+5)) + a(n+1)*(+36*a(n+2) + 372*a(n+3) + 36*a(n+4) - a(n+5)) + a(n+2)*(-18*a(n+2) + 9*a(n+3) + a(n+4)) for n >= 0. - Michael Somos, Apr 14 2015 The e.g.f. A(x) satisfies 0 = -2 + A(x) * (6*x - 2) + A'(x) * (4*x^2 - x). - Michael Somos, Apr 14 2015 Conjecture: (n+2)*a(n) - 2*n*(2*n+1)*a(n-1) = 0. - R. J. Mathar, Oct 31 2015 a(n) ~ 4^n*exp(-n)*n^(n - 2)*sqrt(2)*(24*n - 61)/6. - Peter Luschny, Mar 20 2019 Sum_{n>=0} 1/a(n) = (25*exp(1/4)*sqrt(Pi)*erf(1/2) + 22)/32, where erf is the error function. - Amiram Eldar, Dec 04 2022 a(n) = 2 * Sum_{k=0..n} (n+2)^(k-1) * |Stirling1(n,k)|. - Seiichi Manyama, Aug 31 2024
EXAMPLE
G.f. = 1 + 2*x + 10*x^2 + 84*x^3 + 1008*x^4 + 15840*x^5 + 308880*x^6 + ...
MAPLE
with(combstruct): ZL:=[T, {T=Union(Z, Prod(Epsilon, Z, T), Prod(T, Z, Epsilon), Prod(T, T, Z))}, labeled]: seq(count(ZL, size=i+1)/(i+1), i=0..18); # Zerinvary Lajos, Dec 16 2007 a := n -> (2^(2*n+2)*GAMMA(n+3/2))/(sqrt(Pi)*(n+1)*(n+2)):
MATHEMATICA
Table[2*(2n+1)!/(n+2)!, {n, 0, 20}] (* G. C. Greubel, Mar 19 2019 *) Table[n! CatalanNumber[n+1], {n, 0, 20}] (* Harvey P. Dale, Feb 02 2023 *)
PROG
(PARI) { for (n = 0, 100, a = 2 * (2*n + 1)!/(n + 2)!; write("b065866.txt", n, " ", a) ) } \\ Harry J. Smith, Nov 02 2009 (Magma) [Factorial(n)*Catalan(n+1): n in [0..20]]; // G. C. Greubel, Mar 19 2019 (Sage) [factorial(n)*catalan_number(n+1) for n in (0..20)] # G. C. Greubel, Mar 19 2019 (GAP) List([0..20], n-> 2*Factorial(2*n+1)/Factorial(n+2)) # G. C. Greubel, Mar 19 2019
Number of words of semilength n over n-ary alphabet, either empty or beginning with the first letter of the alphabet, such that the index set of occurring letters is an integer interval [1, k], that can be built by repeatedly inserting doublets into the initially empty word.
+10
3
1, 1, 3, 20, 231, 3864, 85360, 2353546, 77963599, 3019479344, 133966276692, 6702399275538, 373406941221160, 22930441709648290, 1539004344848618466, 112089683771614695478, 8805334896381292460191, 742162775145283382779168, 66809386370870410069346476
EXAMPLE
a(0) = 1: the empty word.
a(1) = 1: aa.
a(2) = 3: aaaa, aabb, abba.
a(3) = 20: aaaaaa, aaaabb, aaabba, aabaab, aabbaa, aabbbb, aabbcc, aabccb, aacbbc, aaccbb, abaaba, abbaaa, abbabb, abbacc, abbbba, abbcca, abccba, acbbca, accabb, accbba.
MAPLE
A:= proc(n, k) option remember; `if`(n=0, 1, k/n*
add(binomial(2*n, j) *(n-j) *(k-1)^j, j=0..n-1))
end:
T:= proc(n, k) option remember;
add(A(n, k-i)*(-1)^i*binomial(k, i), i=0..k)/`if`(k=0, 1, k)
end:
a:= n-> add(T(n, k), k=0..n):
seq(a(n), n=0..20);
MATHEMATICA
A[n_, k_] := A[n, k] = If[n == 0, 1, k/n*
Sum[Binomial[2*n, j]*(n-j) *If[j == 0, 1, (k - 1)^j], {j, 0, n - 1}]];
T[n_, k_] := T[n, k] =
Sum[A[n, k - i]*(-1)^i*Binomial[k, i], {i, 0, k}]/If[k == 0, 1, k];
a[n_] := Sum[T[n, k], {k, 0, n}];
Search completed in 0.012 seconds
|