A058884 Partial sums of the partition function (A000041), with the last term subtracted. Also the sum of the row of the character table for S_n corresponding to the partition n-1,1 for n>1. Also the sum over all partitions lambda of n of one less than the number of 1's in lambda.

-1, 0, 0, 1, 2, 5, 8, 15, 23, 37, 55, 83, 118, 171, 238, 332, 453, 618, 827, 1107, 1460, 1922, 2504, 3253, 4188, 5380, 6860, 8722, 11024, 13895, 17421, 21787, 27122, 33677, 41653, 51390, 63179, 77496, 94755, 115600, 140632, 170725, 206717, 249804, 301151, 362367, 435077, 521439, 623674, 744695

Offset

0,5

Comments

For n>=1 number of up-steps in all partitions of n (represented as weakly increasing lists), see example. - Joerg Arndt, Sep 03 2014

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1000

M. Archibald, A. Blecher, A. Knopfmacher, and M. E. Mays, Inversions and Parity in Compositions of Integers, J. Int. Seq., Vol. 23 (2020), Article 20.4.1.

Anders Claesson, Atli Fannar Franklín, and Einar Steingrímsson, Permutations with few inversions, arXiv:2305.09457 [math.CO], 2023.

S. Heubach, A. Knopfmacher, M. E. Mays and A. Munagi, Inversions in Compositions of Integers, Quaestiones Mathematicae 34 (2011), 187-202.

Formula

From Andrew Howroyd, Apr 21 2023: (Start)

a(n) = A000070(n-1) - A000041(n) for n > 0.

G.f.: (2*x - 1)*P(x)/(1 - x) where P(x) is the g.f. of A000041. (End)

Example

a(6) = 8 because the 11 partitions of 6
01:  [ 1 1 1 1 1 1 ]
02:  [ 1 1 1 1 2 ]
03:  [ 1 1 1 3 ]
04:  [ 1 1 2 2 ]
05:  [ 1 1 4 ]
06:  [ 1 2 3 ]
07:  [ 1 5 ]
08:  [ 2 2 2 ]
09:  [ 2 4 ]
10:  [ 3 3 ]
11:  [ 6 ]
contain 0+1+1+1+1+2+1+0+1+0+0 = 8 up-steps. - Joerg Arndt, Sep 03 2014

Maple

a:= proc(n) uses combinat; add(numbpart(k), k=0..n-1)-numbpart(n) end:
seq(a(n), n=0..49);

Mathematica

p[n_] := IntegerPartitions[n]; l[n_] := Length[p[n]]; Table[Count[Flatten[p[n]], 1] - l[n], {n, 0, 30}] (* Clark Kimberling, Mar 08 2012 *)

Prog

(PARI) a(n) = {sum(k=0, n-1, numbpart(k)) - numbpart(n)} \\ Andrew Howroyd, Apr 21 2023
(PARI) Vec((2*x - 1)/(1 - x)/eta(x + O(x^51))) \\ Andrew Howroyd, Apr 21 2023

Crossrefs

Cf. A000041, A000070.

Cf. A218074 (up-steps in partitions into distinct parts).

Sequence in context: A098894 A121641 A349796 * A073335 A239258 A362864

Adjacent sequences: A058881 A058882 A058883 * A058885 A058886 A058887

Keyword

sign,easy

Author

Edward Early, Jan 08 2001

Extensions

More terms from James A. Sellers, Sep 28 2001

Status

approved