This site is supported by donations to The OEIS Foundation.

 Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS". Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A074664 Number of algebraically independent elements of degree n in the algebra of symmetric polynomials in noncommuting variables. 38
 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 From David Callan, Jul 21 2017: (Start) 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, TAOCP, Vol. 4, Section 7.2.1.7, Problem 26. LINKS T. D. Noe, Table of n, a(n) for n = 1..100 V. E. Adler, Set partitions and integrable hierarchies, arXiv:1510.02900 [nlin.SI], 2015. Marcelo Aguiar and Swapneel Mahajan, On the Hadamard product of Hopf monoids J.-L. Baril, T. Mansour, A. Petrossian, Equivalence classes of permutations modulo excedances, 2014. N. Bergeron, C. Reutenauer, M. Rosas and M. Zabrocki, Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables, arXiv:math/0502082 [math.CO], 2005. D. Callan, On permutations avoiding the dashed patterns 32-41 and 41-32, arXiv preprint arXiv:1405.2064 [math.CO], 2014 William Y.C. Chen, Teresa X.S. Li, David G.L. Wang, A Bijection  between Atomic Partitions and Unsplitable Partitions, Electron. J. Combin. 18 (2011), no. 1, Paper 7. A. L. L. Gao, S. Kitaev, P. B. Zhang. On pattern avoiding indecomposable permutations, arXiv:1605.05490 [math.CO], 2016. M. He, J. Munro, S. Rao, A Categorization Theorem on Suffix Arrays with Applications to Space Efficient Text Indexes, SODA 2005, Definition 2.2. Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011. M. C. Wolf, Symmetric Functions of Non-commutative Elements, Duke Math. J., 2 (1936), 626-637. FORMULA G.f.: 1 - 1 / B(x) where B(x) = g.f. for A000110 the Bell numbers. a(n) = Sum_{k=1..n-1} A087903(n,k). a(n+1) = Sum_{k=0..n} A086329(n,k). a(n+2) = Sum_{k=0..n} A086211(n,k). - Philippe Deléham, Jun 13 2004 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 Hankel transform is A000142. - Philippe Deléham, Jun 21 2007 From Paul Barry, Nov 26 2009: (Start) 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 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); (continued fraction, 1-step). - Sergei N. Gladkovskii, Sep 28 2012 G.f.: (1+U(0))/x  where U(k)= +x*k - 1 + x - x^2*(k+1)/U(k+1); (continued fraction, 1-step). - Sergei N. Gladkovskii, Sep 29 2012 G.f.: 1 + 1/x - U(0)/x where U(k)= 1 + x - x*(k+1)/(1 - x/U(k+1)); (continued fraction, 2-step). - Sergei N. Gladkovskii, Oct 12 2012 G.f.: 1/U(0) where U(k) = 1 - x*(k+1)/(1 - x/U(k+1)); (continued fraction, 2-step). - Sergei N. Gladkovskii, Nov 12 2012 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) )); (continued fraction). - Sergei N. Gladkovskii, Jan 04 2013. G.f.: (1 - G(0) )/x where G(k) = 1 - x/(1 - x*(k + 1)/G(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Jan 30 2013 G.f.: 1/Q(0) where Q(k) = 1 + x/( x*k - 1 )/Q(k+1) ; (continued fraction). - Sergei N. Gladkovskii, Feb 23 2013 G.f.: Q(0), where Q(k)= 1 + x/(1 - x + x*(k+1)/(x - 1/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 19 2013 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: A074664 := n -> T(n, 0); seq(A074664(n), n=0..22); # Peter Luschny, May 13 2014 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 (* Mats Granvik, Jul 11 2015 *) 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 Row sums of A055105, A055106, A055107. Cf. A098742, A003319. Row sums of A087903, A055105, A055106, A055107. Sequence in context: A225294 A124294 A124295 * A091768 A229741 A261518 Adjacent sequences:  A074661 A074662 A074663 * A074665 A074666 A074667 KEYWORD nonn,easy,nice AUTHOR Michael Somos, Aug 29 2002 EXTENSIONS Edited by Mike Zabrocki, Sep 03 2005 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 11 21:15 EST 2017. Contains 295919 sequences.