How can you partition n number of distinguishable objects into m number of indistinguishable blocks given that each of the blocks consists of not less than k number of objects. (k =1 case can be explained by Stirling numbers of second kind and k= 3 case can be used to obtain number of different ways to partition the set of vertices of a convex n-gon into polygons.)
$\begingroup$
$\endgroup$
6
-
1$\begingroup$ You can use graph theory to obtain different ways of partitioning the set of vertices of a convex n-gon into nonintersecting polygons but my issue is important to find number of different ways to partition including intersecting polygons. Is there anyway to do this using trees? $\endgroup$– Janaka RodrigoCommented Apr 1, 2022 at 13:05
-
1$\begingroup$ Let $S$ be a subset of the positive integers. Let $f_S(n,m)$ be the number of partitions of an $n$-element set into $m$ blocks, where the block sizes all belong to $S$. Then $$ \sum_{n\geq 0}\sum_{m\geq 0}f_S(m,n)t^m\frac{x^n}{n!} = \exp t \sum_{k\in S}\frac{x^k}{k!}. $$ $\endgroup$– Richard StanleyCommented Apr 1, 2022 at 14:38
-
$\begingroup$ @ Richard Stanley is there no way for explicit function or recursive formula? $\endgroup$– Janaka RodrigoCommented Apr 1, 2022 at 15:01
-
1$\begingroup$ For your question you want the coefficient of $x^n/n!$ in $$ \frac{1}{m!}\left(e^x-1-x-\frac{x^2}{2!}-\cdots-\frac{x^{k-1}}{(k-1)!}\right)^m. $$ You can expand by the multinomial theorem and get a formula that becomes messier as $k$ increases. $\endgroup$– Richard StanleyCommented Apr 1, 2022 at 19:37
-
$\begingroup$ Here you have two special cases, 1) When m =2 , k=3 number of different ways for n - gon is a(n) = [ 2^n - 2 - 2*n - 2*C ( n,2) ]/2 OEIS A 272352. $\endgroup$– Janaka RodrigoCommented Apr 2, 2022 at 17:43
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
5
These are called "$k$-associated Stirling numbers of the 2nd kind": see https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Associated_Stirling_numbers_of_the_second_kind.
answered Apr 2, 2022 at 20:48
-
$\begingroup$ I checked with my previous research work on partitioning and this is ok with those special cases. $\endgroup$ Commented Apr 3, 2022 at 5:24
-
$\begingroup$ You can accept this answer if it resolves your question. $\endgroup$ Commented Apr 3, 2022 at 12:45
-
$\begingroup$ Yes definitely I am totally satisfied with this answer. Since I'm new to this community I didn't know how to show my acceptance. $\endgroup$ Commented Apr 3, 2022 at 14:06
-
$\begingroup$ There should be some Bell numbers associated also, right? Where each block has at least k members... $\endgroup$ Commented Apr 7, 2022 at 9:36
-
$\begingroup$ @PerAlexandersson: Sure, I guess so. You can just take a sum of these $k$-associated Stirlings. $\endgroup$ Commented Apr 7, 2022 at 13:25