login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A178841 The number of pure inverting compositions of n. 2
1, 0, 0, 1, 2, 5, 9, 19, 37, 74, 148, 296, 591, 1183, 2366, 4731, 9463, 18926, 37852, 75704, 151408, 302816, 605633, 1211265, 2422530, 4845060, 9690121, 19380241, 38760482, 77520964, 155041928, 310083856, 620167712, 1240335424, 2480670848, 4961341695, 9922683391, 19845366782, 39690733564 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

A. Garsia and N. Wallach show that the algebra of quasisymmetric functions is a free module over the algebra of symmetric functions.

The pure inverting compositions index a basis for this module, as conjectured by F. Bergeron and C. Reutenauer.

Georg Fischer observes that the terms of this sequence are very similar to those of A152537. This may be just a coincidence, caused by the fact that their generating functions are almost identical. - N. J. A. Sloane, Mar 23 2019

LINKS

G. C. Greubel, Table of n, a(n) for n = 0..1000

A. Garsia and N. Wallach, Qsym over Sym is free, J. Combin. Theory Ser. A 104 (2003), no. 2, 217--263.

A. Lauve and S. Mason, Qsym over Sym has a stable basis, arXiv:1003.2124 [math.CO], 2010.

Eric Weisstein's World of Mathematics, q-Factorial from MathWorld.

FORMULA

G.f.: P(q) = ((1-q)/(1-2*q))*(Product_{k>=1} (1-q^k)) = 1 + Sum_{n>=1} a(n)*q^n = the g.f. for A011782 divided by the g.f. for A000041.

Define P(m,q) recursively by P(0,q) = 1; P(m,q) = P(m-1,q) + q^m*(m!_q - P(m-1,q)). (Here m!_q is the standard q-factorial.) Then P(m,q) enumerates the pure inverting compositions of length at most m and lim_{m->infinity} P(m,q) = P(q).

Define a(n,0) = a(n); a(n,1) = a(0) + ... + a(n); and a(n,k) = a(n,k-1) + a(n-k,k+1) + a(n-2k, n+1) + ... Then a(n) + a(n-1,1) + a(n-2,2) + ... + a(0,n) = A011782(n), the number of compositions of n. - Gregory L. Simay, Jun 03 2019

The convolution of a(n) with A000041(n), the partitions of n, is A001782(n). - Gregory L. Simay, Jun 03 2019

EXAMPLE

Call a composition w=w1w2...wk "inverting" if for all N > 1 appearing within the word w, there is a pair i < j with w_i = N and w_j = N-1. Factor a composition w as w=uv, with v of maximal length taking the form k^d ... 3^c 2^b 1^a. Call w "pure" if k is even.

Let A(n) be the pure inverting compositions of n, so that a(n) = #A(n). For example, A(3) = {21}, A(4) = {121, 211}, A(5) = {212, 221, 1121, 1211, 2111}.

MATHEMATICA

With[{m = 45}, CoefficientList[Series[((1-q)/(1-2*q))*Product[(1-q^k), {k, 1, m+2}], {q, 0, m}], q]] (* G. C. Greubel, Jan 21 2019 *)

PROG

(PARI) m=45; my(q='q+O('q^m)); Vec(((1-q)/(1-2*q))*prod(k=1, m+2, (1-q^k))) \\ G. C. Greubel, Jan 21 2019

(MAGMA) m:=45; R<q>:=PowerSeriesRing(Integers(), m); Coefficients(R!( ((1-q)/(1-2*q))*(&*[1-q^k: k in [1..m]]) )); // G. C. Greubel, Jan 21 2019

(Sage) m=45; (((1-x)/(1-2*x))*prod(1-x^k for k in (1..m))).series(x, m).coefficients(x, sparse=False) # G. C. Greubel, Jan 21 2019

CROSSREFS

Cf. A000041, A011782, A152537.

Sequence in context: A280247 A261049 A122893 * A214319 A062092 A320172

Adjacent sequences:  A178838 A178839 A178840 * A178842 A178843 A178844

KEYWORD

nonn

AUTHOR

Aaron Lauve (lauve(AT)math.luc.edu), Jun 17 2010

EXTENSIONS

Terms a(26) onward added by G. C. Greubel, Jan 21 2019

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 26 08:44 EDT 2021. Contains 347664 sequences. (Running on oeis4.)