OFFSET
1,3
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!.
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
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!.
EXAMPLE
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.
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 *)
PROG
(C++) /* in the attached file, see the function: template <typename Number > Number C(const Number& n); */
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Viktar Karatchenia, Oct 03 2015
STATUS
approved