Skip main navigation

Sharings into nonempty sets

Sharings into nonempty sets
10.8
Do you remember sharings? You want to distribute distinguishable objects to several people. But there’s the problem that somebody may receive nothing. Now we want to share objects in such a way that everybody receives at least one object. So we want to deal with sharings that do not have empty sets. For instance, take the set I7 This is a sharing of I7 in which the box number 2 remains empty. We do not want this. We want just sharings, 4-sharings of I7, in which every box contains at least one element like that.
68.2
Let me remind that this is strictly connected to certain sequences. Actually, a 4-sharing of I7 may be represented by a 7 sequence of I4. Namely, in that case, in the first case, this 4-sharing corresponds to the 7 sequence of I4 where, in the first place, there is the box– the number of the box that receives number 1, in the second place, the number of the box that receives number 2, and so on. And so it corresponds to the sequence 3, 1, 4, 3, 3, 4, 1. In the second case, the 4-sharing that we obtain corresponds to the sequence where, at the first place, we have 3. Because object number 1 goes into the box, number 3.
120.5
The second element is 1 because object number 2 goes to the box number 1, and so on. Notice that the second sequence contains all the numbers 1, 2, 3, 4. Whereas, the first sequence does not contain number 2. This is because box number 2 remains empty. And this is a quite general fact. Recall this correspondence between sharings and sequences to n sharing of Ik corresponds k sequence of In. And if we require that no sets are empty, so c1, cn are not empty, well, this can be translated in terms of the sequence saying that, the sequence contains all the elements of In. So there is 1, there is 2, and there is n.
177.2
That is, all the boxes appear in the sequence. So looking at sharings without empty sets is equivalent to look at what we call complete sequences. That is, k sequences of In in which all the elements of In appear. But it is another interest which is related to functions. Let us recall that there is a correspondence between functions and sequences– more precisely between functions from Ik to In between k sequences of In. And to every function, f, corresponds the sequence f1, f2, fk of the k values of f. Let me recall that an injective function corresponds a sequence without repetition.
233.9
But notice that a subjective function, that is, for each element of In, there is an element of Ik that goes in that element. So this means that in the sequence f1, fk appear all the elements of In. So to a subjective function, corresponds a k sequence of In that contains all the terms of In. Therefore, counting sharings without empty sets counts, actually, several different objects. At the same time, the number of n sharings of Ik without empty sets, the number of k sequences of In that contains all the terms of In and the number of subjective functions from Ik to In. So let us compute this number.
288.4
We consider the set of k sequences of In. Among these sequences, there are sequences that do not contain all the terms of In, like 1, 1, 1, 1, 1. So let us introduce the sets of sequences that contain the term 1– b1, b2, the set of sequences that contain the term 2, and Bi, the set of k sequences that contain term i. The k sequences with all the elements of In are of the elements of the intersection of B1 with B2 with Bn. Now, the idea is to apply the inclusion-exclusion principle, but it is formulated in terms of intersection of complements of sets. Well, let us see, at B1, as the complement of something else, of its complement.
344.4
So we write that B1 is the complement of A1, B2 the compliment of A2, and Bn the complement of An. Where? Well, if Bi is a set of k sequences that contain i, its complement is the set of k sequences that do not contain i, for each i from 1 to n. And therefore, to compute the cardinality of the elements of this interseciton, in order to compute the cardinality of this intersection, we apply the inclusion-exclusion principle. Let us compute the number of elements of x. x is the set of k sequences of In, so n to the k elements. How about sigma 1?
385.9
Sigma 1 is the sum of the elements of A1, An, so n times the number of elements of A1, by symmetry. A1 is the set of k sequences that do not contain the number 1, so it is a set of sequences, k sequences, of 2, 3n, so of n minus 1 terms. So it has n minus 1 to the k elements. And therefore, Sigma 1 equals n times n minus 1 to the k. How about sigma 2? Well, it is the sum of the number of elements of [INAUDIBLE] intersection of these sets that are binomial n over 2 intersections. And let us compute the number of elements of A1 intersection A2.
436.3
These are sequences that do not contain 1 and 2, neither 1, nor 2. So these are the k sequences from 3 to n. And they are n minus 2 to the k. So sigma 2 equals n over 2 times n minus 2 to the k. And we continue up to sigma n minus 1, which equals n over n minus 1 times the number of elements of the intersection of A1 with A2 with n minus 1, which are the sequences that do not contain 1 to n minus 1. So there is just one sequence– n, n, n, n, n. Of course, sigma n are the k sequences that do not contain 1 to n, so there are no such sequences.
494.7
And putting all together, so we get n to the k minus binomial n over 1 times n minus 1 to the k, plus, plus, plus. It is an alternating sum of terms of the form n over i, binomial n over i times n minus i to the k.

We learn here how to count the number of distributions of different objects into distinguishable boxes in such a way that no box remains empty. For instance, assume a hostel has got 3 big rooms A, B, C. How many ways are there to distribute 14 students in the 3 rooms in such a way that each room has at least a student? Translated into mathematical terms this is counting the number of sharings of a finite set into a prescribed number nonempty sets.

You can access the content of the video in the PDF file at the bottom of this step.

This article is from the free online

Combinatorics: Strategies and Methods for Counting

Created by
FutureLearn - Learning For Life

Our purpose is to transform access to education.

We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.

We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.

Learn more about how FutureLearn is transforming access to education