%I #154 Feb 13 2022 04:34:28

%S 1,1,2,6,22,92,426,2146,11624,67146,411142,2656052,18035178,128318314,

%T 954086192,7396278762,59659032142,499778527628,4341025729290,

%U 39035256389026,362878164902216,3482882959111530,34472032118214598

%N Number of algebraically independent elements of degree n in the algebra of symmetric polynomials in noncommuting variables.

%C 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}; ...

%C Also the number of non-nesting permutations on n elements (see He et al.). - _Chad Brewbaker_, Apr 11 2010

%C The Chen-Li-Wang link presents a bijection from indecomposable (= atomic) partitions to irreducible partitions. - _David Callan_, May 13 2014

%C From _David Callan_, Jul 21 2017: (Start)

%C 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, ... .

%C 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)

%D D. E. Knuth, The Art of Computer Programming, Vol. 4, Section 7.2.1.7, Problem 26.

%H Vaclav Kotesovec, <a href="/A074664/b074664.txt">Table of n, a(n) for n = 1..573</a> (terms 1..100 from T. D. Noe)

%H V. E. Adler, <a href="http://arxiv.org/abs/1510.02900">Set partitions and integrable hierarchies</a>, arXiv:1510.02900 [nlin.SI], 2015.

%H Marcelo Aguiar and Swapneel Mahajan, <a href="http://pi.math.cornell.edu/~maguiar/hadamard.pdf">On the Hadamard product of Hopf monoids</a>

%H J.-L. Baril, T. Mansour, A. Petrossian, <a href="http://jl.baril.u-bourgogne.fr/equival.pdf">Equivalence classes of permutations modulo excedances</a>, 2014.

%H N. Bergeron, C. Reutenauer, M. Rosas and M. Zabrocki, <a href="https://arxiv.org/abs/math/0502082">Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables</a>, arXiv:math/0502082 [math.CO], 2005.

%H Daniel Birmajer, Juan B. Gil, Michael D. Weiner, <a href="https://arxiv.org/abs/1803.07727">A family of Bell transformations</a>, arXiv:1803.07727 [math.CO], 2018.

%H D. Callan, <a href="http://arxiv.org/abs/1405.2064">On permutations avoiding the dashed patterns 32-41 and 41-32</a>, arXiv preprint arXiv:1405.2064 [math.CO], 2014

%H William Y.C. Chen, Teresa X.S. Li, David G.L. Wang, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p7">A Bijection between Atomic Partitions and Unsplitable Partitions</a>, Electron. J. Combin. 18 (2011), no. 1, Paper 7.

%H A. L. L. Gao, S. Kitaev, P. B. Zhang. <a href="https://arxiv.org/abs/1605.05490">On pattern avoiding indecomposable permutations</a>, arXiv:1605.05490 [math.CO], 2016.

%H Meng He, J. Ian Munro, S. Srinivasa Rao, <a href="https://web.cs.dal.ca/~mhe/publications/soda05_suffixarray.pdf">A Categorization Theorem on Suffix Arrays with Applications to Space Efficient Text Indexes</a>, SODA 2005, Definition 2.2.

%H Aoife Hennessy, <a href="http://repository.wit.ie/1693/1/AoifeThesis.pdf">A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths</a>, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.

%H M. Klazar, <a href="http://kam.mff.cuni.cz/~klazar/bell.pdf">Bell numbers, their relatives and algebraic differential equations</a>

%H M. Klazar, <a href="https://doi.org/10.1016/S0097-3165(03)00014-1">Bell numbers, their relatives and algebraic differential equations</a>, Journal of Combinatorial Theory, Series A, Volume 102, Issue 1, April 2003, pp. 63-87.

%H M. C. Wolf, <a href="http://dx.doi.org/10.1215/S0012-7094-36-00253-3">Symmetric Functions of Non-commutative Elements</a>, Duke Math. J., 2 (1936), 626-637.

%H Chunyan Yan, Zhicong Lin, <a href="https://arxiv.org/abs/1912.03674">Inversion sequences avoiding pairs of patterns</a>, arXiv:1912.03674 [math.CO], 2019.

%F G.f.: 1 - 1 / B(x) where B(x) = g.f. for A000110 the Bell numbers.

%F 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

%F 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

%F Hankel transform is A000142. - _Philippe Deléham_, Jun 21 2007

%F From _Paul Barry_, Nov 26 2009: (Start)

%F 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);

%F 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)

%F 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

%F G.f. satisfies: A(x) = x/(1 - (1-x)*A( x/(1-x) )). - _Paul D. Hanna_, Aug 15 2010

%F a(n) = upper left term in M^(n-1), where M is the following infinite square production matrix:

%F 1, 1, 0, 0, 0, 0, ...

%F 1, 2, 1, 0, 0, 0, ...

%F 1, 1, 3, 1, 0, 0, ...

%F 1, 1, 1, 4, 1, 0, ...

%F 1, 1, 1, 1, 5, 1, ...

%F 1, 1, 1, 1, 1, 6, ...

%F ...

%F 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

%F From _Sergei N. Gladkovskii_, Sep 28 2012 to May 19 2013: (Start)

%F Continued fractions:

%F 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).

%F G.f.: (1+U(0))/x where U(k) = +x*k - 1 + x - x^2*(k+1)/U(k+1).

%F G.f.: 1 + 1/x - U(0)/x where U(k) = 1 + x - x*(k+1)/(1 - x/U(k+1)).

%F G.f.: 1/U(0) where U(k) = 1 - x*(k+1)/(1 - x/U(k+1)).

%F 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))).

%F G.f.: (1 - G(0))/x where G(k) = 1 - x/(1 - x*(k + 1)/G(k+1)).

%F G.f.: 1/Q(0) where Q(k) = 1 + x/(x*k - 1)/Q(k+1).

%F G.f.: Q(0) where Q(k) = 1 + x/(1 - x + x*(k+1)/(x - 1/Q(k+1))). (End)

%e G.f. = x + x^2 + 2*x^3 + 6*x^4 + 22*x^5 + 92*x^6 + 426*x^7 + 2146*x^8 + ...

%e m{1} = x1 + x2 + x3 + ..., so a(1) = 1.

%e 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.

%e 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.

%p T := proc(n, k) option remember; local j;

%p if k=n then 1

%p elif k<0 then 0

%p else k*T(n-1,k) + add(T(n-1,j), j=k-1..n-1)

%p fi end:

%p A074664 := n -> T(n, 0);

%p seq(A074664(n), n=0..22); # _Peter Luschny_, May 13 2014

%t 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_ *)

%t 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 t[n_, k_] := t[n, k] = If[n >= k,

%t Sum[t[n - i, k - 1], {i, 1, 2 - 1}] +

%t Sum[t[n - i, k], {i, 1, 2 - 1}], 0];

%t A4 = Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}];

%t A5 = A4[[1 ;; nn - 1]]; A5 = Prepend[A5, ConstantArray[0, nn]];

%t cc = Total[

%t Table[coeff[[n]]*mp[A5, n - 1][[All, 1]], {n, 1,

%t nn}]];, {i, 1, nn}], i]; cc

%t (* _Mats Granvik_, Jul 11 2015 *)

%o (PARI) {a(n) = if( n<0, 0, polcoeff( 1 - 1 / serlaplace( exp( exp( x + x * O(x^n)) - 1)), n))};

%o (PARI) x='x+O('x^100); B=exp(exp(x) - 1); Vec( 1-1/serlaplace(B)) \\ _Joerg Arndt_, Aug 13 2015

%Y Row sums of A055105, A055106, A055107. Cf. A098742, A003319.

%Y Row sums of A087903, A055105, A055106, A055107.

%K nonn,easy,nice

%O 1,3

%A _Michael Somos_, Aug 29 2002

%E Edited by _Mike Zabrocki_, Sep 03 2005