Explore BrainMass
Share

Explore BrainMass

    Exponential generating function for number ordered partition

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    An ordered partition of [n]={1,...,n} is a partition (B_1,...B_k), where the order of the blocks matter. (Thus ({1,2},{3}) and ({3},{1,2}) are different ordered partitions of [3].) Let OS(n,3) be the numbered partitions of [n] into 3 nonempty blocks. Thus OS(n,3)=3! S(n,3).

    a) Find an explicit formula for the exponential generating function:

    OS_3(x) = SUMMATION(n more than or equal to 0)[OS(n,3)*((x^(n))/n!)]

    b) Deduce a formula for the numbers OS(n,3) and S(n,3).

    c) Find the exponential generating function for the number of all ordered partitions of [n]. SKETCH ONLY.

    Please see the attached for the formula's adequate notation.

    © BrainMass Inc. brainmass.com October 10, 2019, 5:46 am ad1c9bdddf
    https://brainmass.com/math/basic-algebra/exponential-generating-function-for-number-ordered-partition-517334

    Attachments

    Solution Preview

    See the attached pdf file for the full breakdown of the solutions with their adequate notations and formulas.

    (a) In order to find an explicit formula for the generating function we need to find a recurrence, that is, express OS(n+1,3) in terms of OS(n,3),OS(n-1,3),...,OS(3,3). Then use the recurrence to find a differential equation satisfied by OS_3(x).

    Note that OS(0,3)=OS(1,3)=OS(2,3)=0 ...

    Solution Summary

    We find the exponential generating function for the number of (ordered) partitions of {1,...n} into 3 nonempty blocks. We the use the generating function to obtain the values. We then give a sketch for how to go about finding the generating function for the number of (ordered) partitions of {1,...n} (with no restriction on how many blocks)

    $2.19