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

1, 1, 2, 6, 22, 92, 426, 2146, 11624, 67146, 411142, 2656052, 18035178, 128318314, 954086192, 7396278762, 59659032142, 499778527628, 4341025729290, 39035256389026, 362878164902216, 3482882959111530, 34472032118214598

Offset: 1

Author

Michael Somos, Aug 29 2002

Keywords

• nonn
• easy
• nice

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)

Examples

			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.
		

References

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

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 1..573 (terms 1..100 from T. D. Noe)
• Vsevolod 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
• Jean-Luc Baril, Toufik Mansour, Armen Petrossian, Equivalence classes of permutations modulo excedances, 2014.
• Nantel Bergeron, Christophe Reutenauer, Mercedes Rosas, and Mike Zabrocki, Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables, arXiv:math/0502082 [math.CO], 2005.
• Daniel Birmajer, Juan B. Gil, Michael D. Weiner, A family of Bell transformations, arXiv:1803.07727 [math.CO], 2018.
• David 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.
• Alice L.L. Gao, Sergey Kitaev, and Philip B. Zhang, On pattern avoiding indecomposable permutations, arXiv:1605.05490 [math.CO], 2016.
• Ignas Gasparavičius, Andrius Grigutis, and Juozas Petkelis, Picturesque convolution-like recurrences and partial sums' generation, arXiv:2507.23619 [math.NT], 2025. See p. 27.
• Meng He, J. Ian Munro, S. Srinivasa 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.
• Martin Klazar, Bell numbers, their relatives and algebraic differential equations
• Martin Klazar, Bell numbers, their relatives and algebraic differential equations, Journal of Combinatorial Theory, Series A, Volume 102, Issue 1, April 2003, pp. 63-87.
• Margarete C. Wolf, Symmetric Functions of Non-commutative Elements, Duke Math. J., 2 (1936), 626-637.
• Chunyan Yan and Zhicong Lin, Inversion sequences avoiding pairs of patterns, arXiv:1912.03674 [math.CO], 2019.

Crossrefs

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

Row sums of A087903, A055105, A055106, A055107.

Programs

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 *)

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

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

From Sergei N. Gladkovskii, Sep 28 2012 to May 19 2013: (Start)

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)

Extensions

Edited by Mike Zabrocki, Sep 03 2005