Partitioning a set into lists

in #steemstem3 years ago

The Bell numbers count how many ways there are to partition N elements into sets. What if we want to partition the elements into ordered groups instead, as this Quora question asks?

For example, {a,b} {c,d,e} and {b,a} {c,d,e} are the same partitioning into sets, but not into ordered lists.

The Bell numbers obey a recurrence:

B(n+1) = sum k=0..n { binom(n,k) * B(k) }

which is justified in terms of removing the set containing the “first” (lowest-valued, say) element. k
indexes over the number of elements not in this set, there are binom(n,k ways to pick them, and B(k) ways to partition them.

We can easily turn this into a recurrence over ways to order the elements in each partition:

C(n+1) = sum k=0..n { (n+1-k)! * binom(n,k) * B(k) }

The set we removed (that contains the “first” element of the original set) is of size n+1−k, so it can be ordered in (n+k-1)! distinct ways, and each of these orderings can be paired with any of the available choices and orders of the remaining k elements.

I threw together some Python code to implement this recurrence:

# From https://gist.github.com/rougier/ebe734dcc6f4ff450abf
def binomial(n, k):
    """
    A fast way to calculate binomial coefficients by Andrew Dalke.
    See http://stackoverflow.com/questions/3025162/statistics-combinations-in-python
    """
    if 0 <= k <= n:
        ntok = 1
        ktok = 1
        for t in xrange(1, min(k, n - k) + 1):
            ntok *= n
            ktok *= t
            n -= 1
        return ntok // ktok
    else:
        return 0

def factorial( n ):
    if n == 0:
        return 1
    ret = 1
    for i in xrange( 2, n + 1 ):
        ret *= i
    return ret

def partitions_into_total_orders( m ):
    val = [None] * (m+1)
    val[0] = 1
    val[1] = 1
    for n in xrange( 1, m ):
        # Compute n+1
        tmp = 0
        for k in xrange( 0, n+1 ):
            tmp += binomial( n, k ) * factorial(n + 1 - k ) * val[k]
        val[n+1] = tmp
    return val

(The Haskell version would probably be prettier, as a self-recursive array definition.)

>>> pprint.pprint( partitions_into_total_orders(20) )
[1,
 1,
 3,
 13,
 73,
 501,
 4051,
 37633,
 394353,
 4596553,
 58941091,
 824073141,
 12470162233L,
 202976401213L,
 3535017524403L,
 65573803186921L,
 1290434218669921L,
 26846616451246353L,
 588633468315403843L,
 13564373693588558173L,
 327697927886085654441L]

This sequence is A000262 in the Online Encyclopedia of Integer Sequences, and more information can be found about it there. But, unlike the Bell Numbers, it doesn't appear to have a well-known name (though one or more of the references might name it.)

It seems trivial to extend the list beyond the 444 values currently in the OEIS:

>>> a = partitions_into_total_orders(500)
>>> a[445]
3549292370508805159816569987954285344396657510795554322174219200284938021552459305649764453676879331381726227308397349706332625735109322766384742689512837781933552271696452295507430453816017653770782548820800979477740762113630101472674590941070346886789347195166700719170015194143370749361014294622013831855459606619587788493906733145088876951867607064510581907335203726336222112549590988879213985659408433063349187438926065642124233265796247240308820380730636134217026702329240813645548435857866916318250327238530003440951684492429199855392402883015419785783782503556422217719938263845879893216604137311263061583644474420492077874479568291772742379482126859778320972094748833190234383500913296967990387469226679302739115758348855376993890250878022951237465510031943420668964594817338460644504177345168761851434514344256171704617556018164197594391584888906518228567907405660857519991265072822823355837407025410807672466016140913725137763011076901797240961561552844550260012058991623122900932503937295341L

However, one of the other formulas given in the OEIS, such as the recursion a_n=(2 * n - 1) * a_{n-1} - (n-1) * (n-2) * a{n-2} may be more efficient than my code above.

Sort:  




This post has been voted on by the SteemSTEM curation team and voting trail in collaboration with @curie.

If you appreciate the work we are doing then consider voting both projects for witness by selecting stem.witness and curie!

For additional information please join us on the SteemSTEM discord and to get to know the rest of the community!

Congratulations @markgritter! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :

You received more than 500 as payout for your posts. Your next target is to reach a total payout of 1000

Click here to view your Board
If you no longer want to receive notifications, reply to this comment with the word STOP

Support SteemitBoard's project! Vote for its witness and get one more award!

Hello @markgritter, I am working alongside @steemcommunity with the #tenkminnows project. Read more about the project here Let's Make 250 New Minnows in a Month.
You have been selected to join the initiative to help you reach minnow status with some extra support. If you choose to accept we expect you to power up all earnings so this can be achieved. Look out for my post regarding the initial post topic for you to write on and then do a post at least once a week using the tag. It would be better if you could do regular posts so we can grow you quicker than just one post per week.
Let me know if you need any help and have a nice day.