如何找到給定大小n和聚類數爲k的聚類方式數量的遞推公式？

在這裏，我有點卡住了這個測驗問題。它要求遞歸函數有多種方式，一組n個點可以聚類成k個非空簇。我最初的想法是它應該是S（n，k）= nS（n，k-1），因爲每增加一個簇的數量，應該有更多的方法來增加一個簇到大小爲k-1的現有羣集。如何找到給定大小n和聚類數爲k的聚類方式數量的遞推公式？

附圖是實際問題。非常感謝！ enter image description here

簇的順序是否重要？也就是說，如果有2個點和2個簇，有1個或2個方法嗎？ – kraskevich

@kraskevich給出（在圖像中）S（n，n）= 1，所以羣集被識別，但點不是。 –

你可以得到ķ非空簇，包含n個對象：通過將第n個對象到任何現有的簇

（有它們中的K，所以k*S(n-1,k)變體）

或使除了（k-1）個現有簇以外還包含單個第n個對象的新簇（S(n-1,k-1)變體）

2016-12-28 06:43:34 MBo

回答