A086329 -id:A086329 - cp's OEIS frontend

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

Michael Somos, Aug 29 2002

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)

			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.

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

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.

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

Row sums of A087903, A055105, A055106, A055107.

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

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

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

x='x+O('x^100); B=exp(exp(x) - 1); Vec( 1-1/serlaplace(B)) \\ Joerg Arndt, Aug 13 2015

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)

Edited by Mike Zabrocki, Sep 03 2005

A087903 Triangle read by rows of the numbers T(n,k) (n > 1, 0 < k < n) of set partitions of n of length k which do not have a proper subset of parts with a union equal to a subset {1,2,...,j} with j < n.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 11, 9, 1, 1, 26, 48, 16, 1, 1, 57, 202, 140, 25, 1, 1, 120, 747, 916, 325, 36, 1, 1, 247, 2559, 5071, 3045, 651, 49, 1, 1, 502, 8362, 25300, 23480, 8260, 1176, 64, 1, 1, 1013, 26520, 117962, 159736, 84456, 19404, 1968, 81, 1, 1, 2036, 82509, 525608, 998830, 749154, 253764, 40944, 3105, 100, 1

Offset: 2

Mike Zabrocki, Oct 14 2003

Another version of the triangle T(n,k), 0 <= k <= n, given by [1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, ...] DELTA [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...] where DELTA is the operator defined in A084938; see also A086329 for a triangle transposed. - Philippe Deléham, Jun 13 2004

			T(2,1)=1 for {12};
T(3,1)=1, T(3,2) = 1 for {123}; {13|2};
T(4,1)=1, T(4,2)=4, T(4,3)=1 for {1234}; {14|23}, {13|24}, {124|3}, {134|2}; {14|2|3}.
From _Philippe Deléham_, Jul 16 2007: (Start)
Triangle begins:
  1;
  1,    1;
  1,    4,     1;
  1,   11,     9,      1;
  1,   26,    48,     16,      1;
  1,   57,   202,    140,     25,     1;
  1,  120,   747,    916,    325,    36,     1;
  1,  247,  2559,   5071,   3045,   651,    49,    1;
  1,  502,  8362,  25300,  23480,  8260,  1176,   64,  1;
  1, 1013, 26520, 117962, 159736, 84456, 19404, 1968, 81, 1;
  ...
Triangle T(n,k), 0 <= k <= n, given by [1,0,2,0,3,0,4,0,...] DELTA [0,1,0,1,0,1,0,...] begins:
  1;
  1,    0;
  1,    1,     0;
  1,    4,     1,      0;
  1,   11,     9,      1,      0;
  1,   26,    48,     16,      1,     0;
  1,   57,   202,    140,     25,     1,     0;
  1,  120,   747,    916,    325,    36,     1,    0;
  1,  247,  2559,   5071,   3045,   651,    49,    1,  0;
  1,  502,  8362,  25300,  23480,  8260,  1176,   64,  1, 0;
  1, 1013, 26520, 117962, 159736, 84456, 19404, 1968, 81, 1, 0;
  ...
(End)

G. C. Greubel, Rows n = 2..52 of the triangle, flattened
V. E. Adler, Set partitions and integrable hierarchies, arXiv:1510.02900 [nlin.SI], 2015.
Mercedes H. Rosas and Bruce E. Sagan, Symmetric functions in noncommuting variables, arXiv:math/0208168 [math.CO], 2002, 2004.
Yves Le Jan, Loop clusters on complete graphs, arXiv:2504.16976 [math.PR], 2025. See p. 6.
Margarete C. Wolf, Symmetric Functions of Non-commutative Elements, Duke Math. J., 2 (1936), 626-637.

Cf. A000110, A000295, A008277, A055106, A074664.

Cf. A055105.

A := proc(n,k) option remember; local j,ell; if n<=0 or k>=n then 0; elif k=1 or k=n-1 then 1; else S2(n-1,k)+add(add((k-ell-1)*A(n-j-1,k-ell)*S2(j,ell),ell=0..k-1),j=0..n-2); fi; end: S2 := (n,k)->if n<0 or k>n then 0; elif k=n or k=1 then 1 else k*S2(n-1,k)+S2(n-1,k-1); fi:

nmax = 12; t[n_, k_] := t[n, k] = StirlingS2[n-1, k] + Sum[ (k-d-1)*t[n-j-1, k-d]*StirlingS2[j, d], {d, 0, k-1}, {j, 0, n-2}]; Flatten[ Table[ t[n, k], {n, 2, nmax}, {k, 1, n-1}]] (* Jean-François Alcover, Oct 04 2011, after given formula *)

@CachedFunction # T = A087903
def T(n,k): return stirling_number2(n-1, k) + sum( sum( (k-m-1)*T(n-j-1, k-m)*stirling_number2(j, m) for m in (0..k-1) ) for j in (0..n-2) )
flatten([[T(n, k) for k in (1..n-1)] for n in (2..14)]) # G. C. Greubel, Jun 21 2022

T(n, n-1) = T(n,1) = 1.
T(n, n-2) = (n-2)^2.
T(n, 2) = A000295(n).
T(n, k) = S2(n-1, k) + Sum_{j=0..n-2} Sum_{d=0..k-1} (k-d-1)*T(n-j-1, k-d)*S2(j, d), where S2(n, k) is the Stirling number of the second kind.
Sum_{k = 1..n-1} T(n, k) = A074664(n). - Philippe Deléham, Jun 13 2004
G.f.: 1-1/(1+add(add(q^n t^k S2(n, k), k=1..n), n >= 1)) where S2(n, k) are the Stirling numbers of the 2nd kind A008277. - Mike Zabrocki, Sep 03 2005

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A087903 Triangle read by rows of the numbers T(n,k) (n > 1, 0 < k < n) of set partitions of n of length k which do not have a proper subset of parts with a union equal to a subset {1,2,...,j} with j < n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

SageMath

Formula

A171151 Expansion of (A(x)-1)/(x*A(x)), A(x) the g.f. of A004211.

Views

Author

Keywords

Comments

Formula