A360182 Number of partitions of [n] where each block size occurs at most twice.

1, 1, 2, 4, 14, 41, 152, 575, 2634, 13207, 59927, 312170, 1946870, 10547135, 65168469, 421552409, 3148178034, 20138277895, 141300123713, 1063603633154, 9108280640649, 68154636145922, 549824347467969, 4551458909818969, 39948625639349706, 406913301246314341

Offset

0,3

Links

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

Wikipedia, Partition of a set

Formula

a(n) = Sum_{k=0..2} A271423(n,k).

Example

a(0) = 1: (), the empty partition.
a(1) = 1: 1.
a(2) = 2: 12, 1|2.
a(3) = 4: 123, 12|3, 13|2, 1|23.
a(4) = 14: 1234, 123|4, 124|3, 12|34, 12|3|4, 134|2, 13|24, 13|2|4, 14|23, 1|234, 1|23|4, 14|2|3, 1|24|3, 1|2|34.
a(5) = 41: 12345, 1234|5, 1235|4, 123|45, 123|4|5, 1245|3, 124|35, 124|3|5, 125|34, 12|345, 12|34|5, 125|3|4, 12|35|4, 12|3|45, 1345|2, 134|25, 134|2|5, 135|24, 13|245, 13|24|5, 135|2|4, 13|25|4, 13|2|45, 145|23, 14|235, 14|23|5, 15|234, 1|2345, 1|234|5, 15|23|4, 1|235|4, 1|23|45, 145|2|3, 14|25|3, 14|2|35, 15|24|3, 1|245|3, 1|24|35, 15|2|34, 1|25|34, 1|2|345.

Maple

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(combinat[multinomial](n, n-i*j, i$j)/j!*
        b(n-i*j, i-1), j=0..min(2, n/i))))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..25);

Mathematica

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, Sum[multinomial[n, {n - i*j}~Join~ Table[i, {j}]]/j!*b[n - i*j, i - 1], {j, 0, Min[2, n/i]}]]];
a[n_] :=  b[n, n];
Table[a[n], {n, 0, 25}](* Jean-François Alcover, Nov 21 2023, after Alois P. Heinz *)

Crossrefs

Cf. A000110, A007837, A114917, A115275, A271423.

Sequence in context: A152011 A000912 A228477 * A169982 A367101 A243323

Adjacent sequences: A360179 A360180 A360181 * A360183 A360184 A360185

Keyword

nonn

Author

Alois P. Heinz, May 13 2023

Status

approved