A316861 a(n) = Sum_{p in P} y(1)*y(2), where P is the set of partitions of n, and y(k) is the number of parts with multiplicity at least k in p.

0, 0, 1, 1, 4, 7, 13, 22, 38, 58, 93, 139, 208, 302, 438, 616, 869, 1200, 1650, 2239, 3026, 4038, 5374, 7081, 9292, 12103, 15704, 20236, 25992, 33191, 42237, 53490, 67524, 84860, 106341, 132736, 165212, 204928, 253518, 312629, 384585, 471734, 577276, 704584, 858078

Offset

0,5

Comments

Also (1/2)*Sum_{p in P} H(1)*H(2), where P is the set of partitions of n, and H(k) is the number of k-hooks in p.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Formula

G.f.: (q^3/((1-q)(1-q^2)) + q^2/(1-q^2) - q^3/(1-q^3))*Product_{j>=1} 1/(1-q^j).

a(n) = A000097(n+3) + A116646(n).

In general, Sum_{n>=0} q^n Sum_{p in P} y(s)*y(t) for s < t is given by (q^(s+t)/((1-q^s)(1-q^t)) + q^t/(1-q^t) - q^(s+t)/(1-q^(s+t))) * Product_{j>=1} 1/(1-q^j).

Example

For n=6, we sum over the partitions of 6. For each partition, we count the parts with multiplicity at least one, and those of at least two.
6............y(1)*y(2) = 1*0 = 0
5,1..........y(1)*y(2) = 2*0 = 0
4,2..........y(1)*y(2) = 2*0 = 0
4,1,1........y(1)*y(2) = 2*1 = 2
3,3..........y(1)*y(2) = 1*1 = 1
3,2,1........y(1)*y(2) = 3*0 = 0
3,1,1,1......y(1)*y(2) = 2*1 = 2
2,2,2........y(1)*y(2) = 1*1 = 1
2,2,1,1......y(1)*y(2) = 2*2 = 4
2,1,1,1,1....y(1)*y(2) = 2*1 = 2
1,1,1,1,1,1..y(1)*y(2) = 1*1 = 1
--------------------------------
Total.........................13

Maple

b:= proc(n, i, x, y) option remember;
     `if`(n=0, x*y, `if`(i<1, 0, add(b(n-i*j, i-1,
     `if`(j>0, 1, 0)+x, `if`(j>1, 1, 0)+y), j=0..n/i)))
    end:
a:= n-> b(n$2, 0$2):
seq(a(n), n=0..55);  # Alois P. Heinz, Jul 30 2018

Mathematica

Array[Total[
   Count[Split@#, (_?(Length@# >= 1 &))] Count[
       Split@#, (_?(Length@# >= 2 &))] & /@
    IntegerPartitions[#]] &, 50]
(* Second program: *)
b[n_, i_, x_, y_] := b[n, i, x, y] = If[n == 0, x*y, If[i < 1, 0, Sum[b[n - i*j, i - 1, If[j > 0, 1, 0] + x, If[j > 1, 1, 0] + y], {j, 0, n/i}]]];
a[n_] := b[n, n, 0, 0];
a /@ Range[0, 55] (* Jean-François Alcover, Sep 16 2019, after Alois P. Heinz *)

Prog

(PARI) seq(n)={Vec(x*(1 + x^2 + x^3)/((1 - x)^2*(1 + x)*(1 + x + x^2)*prod(i=1, n-1, 1 - x^i + O(x^n))) + O(x^n), -n)} \\ Andrew Howroyd, Jul 15 2018

Crossrefs

Cf. A000097, A116646, A000070, A024786.

Sequence in context: A008471 A156622 A111314 * A298354 A139217 A038391

Adjacent sequences: A316858 A316859 A316860 * A316862 A316863 A316864

Keyword

nonn

Author

Emily Anible, Jul 15 2018

Status

approved