A262875 Number of equal-sized disjoint subset combinations from a set of n items.

0, 1, 4, 14, 41, 127, 400, 1297, 4520, 17064, 64857, 262286, 1156325, 5199261, 23835336, 117674608, 609741279, 3268286263, 18109939168, 102866828839, 620474818814, 4005211833858, 25747541532731, 166978138395205, 1168773990780772

Offset: 1

Author

Viktar Karatchenia, Oct 03 2015

Keywords

• nonn

Comments

a(n) is the total number of combinations of m disjoint subsets of equal size k from a set of n>=2 items, for 2 <= m <= n, 1 <= k <= n/m. m starts at 2 in order to have more than one subset, and m <= n because a subset must contain at least one item.

Given m, for each subset size k, k items are chosen from n; then k items are chosen from the remaining n-k items; then k items are chosen from the remaining n-2*k items; and so on until there are fewer than k items left. Since each m-tuple "kSubSet|kSubSet| ... |kSubSet" is chosen m! times (for example, pairs are chosen as "A|B" and as "B|A"), in order to remove repetitions, we must then divide by m!. Since binomial(n, n + d) = 0 when d>0, the upper limit can be safely increased from floor(n/m) to n.

Thus a(n) = Sum_{m=2..n} b(n,m), where b(n,m) = Sum_{k=1..floor(n/m)} (Product_{j=0..m-1} binomial(n-k*j, k))/m!.

Examples

			a(5) = 25+10+5+1 = 41 combinations of equal size disjoint subsets, i.e., given 5 items, there can be 2, 3, 4 or 5 subsets:
A) Pairs can have 1 or 2 items, contributing 10+15=25:
A.1) There are 10 distinct pairs of size 1: "1|2, 1|3, 1|4, 1|5, and 2|3, 2|4, 2|5, and 3|4, 3|5, 4|5".
A.2) And 15 distinct pairs of size 2: "12|34, 12|35, 12|45, and 13|24, 13|25, 13|45, and 14|23, 14|25, 14|35, and 15|23, 15|24, 15|34, and 23|45, 24|35, 25|34".
B) Triplet can have only 1 item, 10 of them: 1|2|3, 1|2|4, 1|2|5, and 1|3|4, 1|3|5, 1|4|5, and 2|3|4, 2|3|5, 2|4|5, 3|4|5.
C) Four-tuple from one item, 5 in total: 1|2|3|4, and 1|2|3|5, 1|2|4|5, 1|3|4|5, finally 2|3|4|5.
D) There is one 5-tuple: 1|2|3|4|5.
		

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 1..600 (terms 1..100 from Viktar Karatchenia)
• Viktar Karatchenia, C++ program to calculate b(n,m) and a(n).
• Viktar Karatchenia, C++ file for InfInt class
• Viktar Karatchenia, Header file for InfInt class

Crossrefs

Cf. A097861 (b(n,2)).

Programs

Mathematica

Table[Sum[Sum[Product[Binomial[n - k*j, k], {j, 0, m - 1}]/m!, {k, 1, Floor[n/m]}], {m, 2, n}], {n, 1, 30}] (* Vaclav Kotesovec, Aug 05 2019 *)
Table[Sum[Sum[n!/(k!^m * (n - k*m)! * m!), {k, 1, Floor[n/m]}], {m, 2, n}], {n, 1, 30}] (* Vaclav Kotesovec, Aug 05 2019 *)

PARI

a(n) = sum(m=2, n, sum(k=1, n\m, prod(j=0, m-1, binomial(n-k*j, k))/m!)); \\ Michel Marcus, Oct 04 2015

Formula

a(n) = Sum_{m=2..n} b(n,m), where b(n,m) = Sum_{k=1..floor(n/m)} (Product_{j=0..(m-1)} binomial(n-k*j, k))/m!.