login
Number of set partitions of [n] with distinct block sizes and one of the block sizes is 2.
2

%I #10 Dec 18 2020 04:02:16

%S 0,0,1,3,0,10,75,126,196,1548,15525,39820,161106,358722,3705884,

%T 46623045,142988280,768721504,3560215293,12250746432,144581799790,

%U 2542575063630,8955836934660,55657973021431,319349051391228,1983548989621200,7898257536096850

%N Number of set partitions of [n] with distinct block sizes and one of the block sizes is 2.

%C Sum of multinomials M(n; lambda), where lambda ranges over all integer partitions of n into distinct parts and one part is 2.

%H Alois P. Heinz, <a href="/A327881/b327881.txt">Table of n, a(n) for n = 0..697</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients">Multinomial coefficients</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_(number_theory)">Partition (number theory)</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_of_a_set">Partition of a set</a>

%e a(2) = 1: 12.

%e a(3) = 3: 12|3, 13|2, 1|23.

%e a(4) = 0.

%e a(5) = 10: 123|45, 124|35, 125|34, 12|345, 134|25, 135|24, 13|245, 145|23, 14|235, 15|234.

%p b:= proc(n, i, k) option remember; `if`(i*(i+1)/2<n, 0,

%p `if`(n=0, 1, `if`(i<2, 0, b(n, i-1, `if`(i=k, 0, k)))+

%p `if`(i=k, 0, b(n-i, min(n-i, i-1), k)*binomial(n, i))))

%p end:

%p a:= n-> b(n$2, 0)-b(n$2, 2):

%p seq(a(n), n=0..29);

%t b[n_, i_, k_] := b[n, i, k] = If[i(i+1)/2 < n, 0, If[n == 0, 1, If[i < 2, 0, b[n, i - 1, If[i == k, 0, k]]] + If[i == k, 0, b[n - i, Min[n - i, i - 1], k] Binomial[n, i]]]];

%t a[n_] := b[n, n, 0] - b[n, n, 2];

%t a /@ Range[0, 29] (* _Jean-François Alcover_, Dec 18 2020, after _Alois P. Heinz_ *)

%Y Column k=2 of A327869.

%K nonn

%O 0,4

%A _Alois P. Heinz_, Sep 28 2019