login
This site is supported by donations to The OEIS Foundation.

 

Logo

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. Klazar, Bell numbers, their relatives and algebraic differential equations

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.

License Agreements, Terms of Use, Privacy Policy .

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