Share
Explore BrainMass

Exponential generating function for number ordered partition

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.

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