|
|
A074664
|
|
Number of algebraically independent elements of degree n in the algebra of symmetric polynomials in noncommuting variables.
|
|
40
|
|
|
1, 1, 2, 6, 22, 92, 426, 2146, 11624, 67146, 411142, 2656052, 18035178, 128318314, 954086192, 7396278762, 59659032142, 499778527628, 4341025729290, 39035256389026, 362878164902216, 3482882959111530, 34472032118214598
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
Also the number of irreducible set partitions of size n (see A055105) {1}; {1,2}; {1,2,3}, {1,23}; ...; and also the number of set partitions of n which do not have a proper subset of parts with a union equal to a subset {1,2,...,j} with j < n (atomic set partitions, see A087903) {1}; {12}; {13,2}, {123}; ...
Also the number of non-nesting permutations on n elements (see He et al.). - Chad Brewbaker, Apr 11 2010
The Chen-Li-Wang link presents a bijection from indecomposable (= atomic) partitions to irreducible partitions. - David Callan, May 13 2014
The "non-nesting" permutations in Definition 2.2 of the He et al. reference seem to be the permutations whose inverses avoid all four of the patterns 14-23, 23-14, 32-41, and 41-32 (no nested ascents or descents), counted by 1, 2, 6, 20, 68, 240, 848, 3048, ... .
a(n) is the number of permutations of [n-1] with no nested descents, that is, permutations of [n-1] that avoid both of the dashed patterns 32-41 and 41-32. For example, for p = 823751694, the descents 82 and 75 are nested, as are the descents 75 and 94, but 82 and 94 are not because neither of the intervals [2,8] and [4,9] is contained in the other. Since 82 and 75 are nested, 8275 is a 41-32 pattern in p. (End)
|
|
REFERENCES
|
D. E. Knuth, The Art of Computer Programming, Vol. 4, Section 7.2.1.7, Problem 26.
|
|
LINKS
|
|
|
FORMULA
|
G.f.: 1 - 1 / B(x) where B(x) = g.f. for A000110 the Bell numbers.
G.f.: x / (1 - (x - x^2) / (1 - x - (x - 2*x^2) / (1 - 2*x - (x - 3*x^2) / ...))) (a continued fraction). - Michael Somos, Sep 22 2005
G.f.: (of 1,1,2,6,...) 1/(1-x-x^2/(1-3x-2x^2/(1-4x-3x^2/(1-5x-4x^2/(1-6x-5x^2/(1-... (continued fraction);
G.f.: (of 1,2,6,...) 1/(1-2x-2x^2/(1-3x-3x^2/(1-4x-4x^2/(1-5x-5x^2/(1-... (continued fraction). (End)
G.f.: 1/(1-x/(1-x/(1-2x/(1-x/(1-3x/(1-x/(1-4x/(1-x/(1-5x/(1-x/(1-... (continued fraction). - Paul Barry, Mar 03 2010
G.f. satisfies: A(x) = x/(1 - (1-x)*A( x/(1-x) )). - Paul D. Hanna, Aug 15 2010
a(n) = upper left term in M^(n-1), where M is the following infinite square production matrix:
1, 1, 0, 0, 0, 0, ...
1, 2, 1, 0, 0, 0, ...
1, 1, 3, 1, 0, 0, ...
1, 1, 1, 4, 1, 0, ...
1, 1, 1, 1, 5, 1, ...
1, 1, 1, 1, 1, 6, ...
...
a(n) = sum of top row terms in M^(n-2). Example: top row of M^4 = (22, 31, 28, 10, 1, 0, 0, 0, ...), where 22 = a(5) and (22 + 31 + 28 + 10 + 1) = 92 = a(6). - Gary W. Adamson, Jul 11 2011
Continued fractions:
G.f.: (2+(x^2-4)/(U(0)-x^2+4))/x where U(k) = k*(2*k+3)*x^2 + x - 2 - (2 - x + 2*k*x)*(2 + 3*x + 2*k*x)*(k+1)*x^2/U(k+1).
G.f.: (1+U(0))/x where U(k) = +x*k - 1 + x - x^2*(k+1)/U(k+1).
G.f.: 1 + 1/x - U(0)/x where U(k) = 1 + x - x*(k+1)/(1 - x/U(k+1)).
G.f.: 1/U(0) where U(k) = 1 - x*(k+1)/(1 - x/U(k+1)).
G.f.: 1/x - ((1+x)/x)/G(0) where G(k) = 1 - 2*x*(k+1)/((2*k+1)*(2*x*k-1) - x*(2*k+1)*(2*k+3)*(2*x*k-1)/(x*(2*k+3) - 2*(k+1)*(2*x*k+x-1)/G(k+1))).
G.f.: (1 - G(0))/x where G(k) = 1 - x/(1 - x*(k + 1)/G(k+1)).
G.f.: 1/Q(0) where Q(k) = 1 + x/(x*k - 1)/Q(k+1).
G.f.: Q(0) where Q(k) = 1 + x/(1 - x + x*(k+1)/(x - 1/Q(k+1))). (End)
|
|
EXAMPLE
|
G.f. = x + x^2 + 2*x^3 + 6*x^4 + 22*x^5 + 92*x^6 + 426*x^7 + 2146*x^8 + ...
m{1} = x1 + x2 + x3 + ..., so a(1) = 1.
m{1,2} = x1 x2 + x2 x1 + x2 x3 + x3 x2 + x1 x3 + ..., m{12} = x1 x1 + x2 x2 + x3 x3 + ... where m{1} m{1} = m{1,2} + m{12}, so a(2) = 2-1 = 1.
m{1,2,3} = x1 x2 x3 + x1 x2 x4 + x1 x3 x4 + ..., m{12,3} = x1 x1 x2 + x2 x2 x1 + ..., m{13,2} = x1 x2 x1 + x2 x1 x2 + ..., m{1,23} = x1 x2 x2 + x2 x1 x1 + ..., m{123} = x1 x1 x1 + x2 x2 x2 + ... and there are 3 independent relations among these 5 elements m{12} m{1} = m{123} + m{12,3}, m{1} m{12} = m{123} + m{1,23}, m{1} m{1,1} = m{1,2,3} + m{12,3} + m{13,2} so a(3) = 5-3 = 2.
|
|
MAPLE
|
T := proc(n, k) option remember; local j;
if k=n then 1
elif k<0 then 0
else k*T(n-1, k) + add(T(n-1, j), j=k-1..n-1)
fi end:
|
|
MATHEMATICA
|
nmax = 23; A087903[n_, k_] := A087903[n, k] = StirlingS2[n-1, k] + Sum[ (k-d-1)*A087903[n-j-1, k-d]*StirlingS2[j, d], {d, 0, k-1}, {j, 0, n-2}]; a[n_] := Sum[ A087903[n, k], {k, 1, n-1}]; a[1] = 1; Table[a[n], {n, 1, nmax}](* Jean-François Alcover, Oct 04 2011, after Philippe Deléham *)
Clear[t, n, k, i, nn, x]; coeff = ConstantArray[1, 23]; mp[m_, e_] := If[e==0, IdentityMatrix@ Length@ m, MatrixPower[m, e]]; nn = Length[coeff]; cc = Range[nn]*0 + 1; Monitor[ Do[Clear[t]; t[n_, 1] := t[n, 1] = cc[[n]];
t[n_, k_] := t[n, k] = If[n >= k,
Sum[t[n - i, k - 1], {i, 1, 2 - 1}] +
Sum[t[n - i, k], {i, 1, 2 - 1}], 0];
A4 = Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}];
A5 = A4[[1 ;; nn - 1]]; A5 = Prepend[A5, ConstantArray[0, nn]];
cc = Total[
Table[coeff[[n]]*mp[A5, n - 1][[All, 1]], {n, 1,
nn}]]; , {i, 1, nn}], i]; cc
|
|
PROG
|
(PARI) {a(n) = if( n<0, 0, polcoeff( 1 - 1 / serlaplace( exp( exp( x + x * O(x^n)) - 1)), n))};
(PARI) x='x+O('x^100); B=exp(exp(x) - 1); Vec( 1-1/serlaplace(B)) \\ Joerg Arndt, Aug 13 2015
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|