login
A360182
Number of partitions of [n] where each block size occurs at most twice.
3
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
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
KEYWORD
nonn
AUTHOR
Alois P. Heinz, May 13 2023
STATUS
approved