|
|
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
|
|
|
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
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Aaron Lauve (lauve(AT)math.luc.edu), Jun 17 2010
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|