|
%I #36 May 19 2023 18:46:24
%S 1,0,0,1,2,5,9,19,37,74,148,296,591,1183,2366,4731,9463,18926,37852,
%T 75704,151408,302816,605633,1211265,2422530,4845060,9690121,19380241,
%U 38760482,77520964,155041928,310083856,620167712,1240335424,2480670848,4961341695,9922683391,19845366782,39690733564
%N The number of pure inverting compositions of n.
%C A. Garsia and N. Wallach show that the algebra of quasisymmetric functions is a free module over the algebra of symmetric functions.
%C The pure inverting compositions index a basis for this module, as conjectured by F. Bergeron and C. Reutenauer.
%C _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
%H G. C. Greubel, <a href="/A178841/b178841.txt">Table of n, a(n) for n = 0..1000</a>
%H Anders Claesson, Atli Fannar Franklín, and Einar Steingrímsson, <a href="https://arxiv.org/abs/2305.09457">Permutations with few inversions</a>, arXiv:2305.09457 [math.CO], 2023.
%H A. Garsia and N. Wallach, <a href="https://doi.org/10.1016/S0097-3165(03)00042-6">Qsym over Sym is free</a>, J. Combin. Theory Ser. A 104 (2003), no. 2, 217--263.
%H A. Lauve and S. Mason, <a href="http://arxiv.org/abs/1003.2124">Qsym over Sym has a stable basis</a>, arXiv:1003.2124 [math.CO], 2010.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/q-Factorial.html">q-Factorial</a>.
%F 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.
%F 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).
%F 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
%F The convolution of a(n) with A000041(n), the partitions of n, is A011782(n). - _Gregory L. Simay_, Jun 03 2019
%e 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.
%e 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}.
%t 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 *)
%o (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
%o (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
%o (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
%Y Cf. A000041, A011782, A152537.
%K nonn
%O 0,5
%A Aaron Lauve (lauve(AT)math.luc.edu), Jun 17 2010
%E Terms a(26) onward added by _G. C. Greubel_, Jan 21 2019
|
