cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

This page as a plain text file.
%I A262875 #44 Aug 05 2019 12:58:15
%S A262875 0,1,4,14,41,127,400,1297,4520,17064,64857,262286,1156325,5199261,
%T A262875 23835336,117674608,609741279,3268286263,18109939168,102866828839,
%U A262875 620474818814,4005211833858,25747541532731,166978138395205,1168773990780772
%N A262875 Number of equal-sized disjoint subset combinations from a set of n items.
%C A262875 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.
%C A262875 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.
%C A262875 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!.
%H A262875 Vaclav Kotesovec, <a href="/A262875/b262875.txt">Table of n, a(n) for n = 1..600</a> (terms 1..100 from Viktar Karatchenia)
%H A262875 Viktar Karatchenia, <a href="/A262875/a262875_1.txt">C++ program to calculate b(n,m) and a(n).</a>
%H A262875 Viktar Karatchenia, <a href="/A262875/a262875.cpp.txt">C++ file for InfInt class</a>
%H A262875 Viktar Karatchenia, <a href="/A262875/a262875.h.txt">Header file for InfInt class</a>
%F A262875 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!.
%e A262875 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:
%e A262875 A) Pairs can have 1 or 2 items, contributing 10+15=25:
%e A262875 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".
%e A262875 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".
%e A262875 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.
%e A262875 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.
%e A262875 D) There is one 5-tuple: 1|2|3|4|5.
%t A262875 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 *)
%t A262875 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 *)
%o A262875 (C++) /* in the attached file, see the function: template <typename Number > Number C(const Number& n); */
%o A262875 (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
%Y A262875 Cf. A097861 (b(n,2)).
%K A262875 nonn
%O A262875 1,3
%A A262875 _Viktar Karatchenia_, Oct 03 2015