This therminology, while precise is not usually used in the statement of a problem, and the student must

read the problem carefully to decide which types are involved. We also note that some that some authors
favor other therminology. For example, r-combinations are often called r-sets, and r-multisets are often
called r-assortments. Once again, we emphasize that the point of combinatorial reasoning is to find a
correspondence between the problem being considered and some other problem. In particular, we often
try to reduce problems to one or more of the four problems described above.

Example 2.3.1

We take a sample of two object from {x1, x2, x3}; that is, n = 3 and r = 2. Figure 2-4 illustrated the four
different problems and their solutions. Note that sequence and permutations are given by listing the
elements in the correct order, and combinations and multisets use the bracket notation.

At this point, the careful reader often asks about the case r = 0. What is our attitude about sampels of size
0? As has already been mentioned, r-combinations can be viewed as the empty set. Since there is only
one empty set, we say that there is exactly one 0-combination. Mathematicians also say that there is
exactly one 0-sequence, one 0-permutation, and one 0-multiset. While the latter cases may seem less
intuitive than the case for combinations, they provide uniformity.

In the previous example, we determined the number of solutions to each of our four problems by explicit
enumeration. We now develop formulas giving the number of solutions to each problem.

Proposition 2-1. The number of r-sequences from n object is nr.

Proof. If r = 0, then nr = 1, agreening with our convention that there is exactly one 0-permutation. If r > n,
then P (n, r) = 0, agreening with the fact that there is no way to take r distinct objects from n < r objects.
It remains to consider the case in which n ≥ 1. An important heuristic is counting is to imagine the
construction of an r-sequence into r-stages – we pick the first object and then the second, and so on. At
each stages we have n choices, and hence the rule of product says that this construction may be performed
in nr ways. Q.E.D.

Proposition 2-2. The number of r-permutations from n object is n(n – 1) ( n - 2) … (n – r + 1).

We denote the latter expression by P(n, r). If r = 0, then P (n, r) is the vacuous product, which is one by
definition.

Proof. If r = 0, then P(n, r) = 1, agreening with our convention that there is exactly one 0-permutation. If r
> n, then P(n, r) = 0, agreeing with the fact that there is no way to take r distinct object from n < r objects.
It remains to consider the case in which n ≥ r ≥ 1. We may decompose the construction of an r-
permutation into r stages – we pick the first object and then a DIFFERENT second object, and so on. We
have n choices at the first stage, n – 1 choices at the second stage, … , and n – r + 1 choices at the rth
stage. Hence th rule of product says that this construction may be performed in n(n -1)( n - 2) … (n – r +
1) ways. Q.E.D.

When r = n, we have the number of ways to arrage n distinct objects in a row. We refer to such an
arrangement as a permutation as well as an n-permutation. In particular, the number of ways to arrange n
different people in a row is n (n – 1) …1. This latter expression appears so frequently that is receives a
special name, n! called n factorial. For example, 6 people can be arranged in 6! = 6 x 5 x 4 x 3 x 2 x 1 =
720 ways. Notice that n! = n( n – 1 )! For n > 1. We define 0! = 1 so that n! = r(n - 1)! For n ≥ 1.

Note that definition P(n, r) = n (n - 1) … (n – r + 1) can be applied to any real number n and natural
number r (although we only have a physical interpretation for natural numbers n and r). for example, P(-1,
0) = 1 and P (2,3) = 0.

Proposition 2-3. The number of r-combinations from n objects is

P(n, r) / r!.

We denote the letter expression by C(n, r) or (n/r) is called a binominal cooficient.

Proof. If r > n, then C(n, r) = 0, agreeing with the fact that there are no r-combinations when r > n. it
remains to consider the case n ≥ r. Let’s consider a specific example. If n = 3 and r = 2, then we have
already seen that there are six 2-permutations.

It’s clear that the permutations have included 2 arrangements for each combination. In general, the
permutation will include r! arrangement for each r-combination because the r elements in the combination
can be arranged in r! ways. To compensate, the formula for P (n, r) must be divided by r!, and hence there
are P(n, r)/ r! r-combinations from n objects. Q.E.D.

Note that the definition C(n,r) =(n/r) = can be applied to any real number n and natural numbers n and
r. for example

Preposition 2-4 . the number of r-multisets from n objects is (n-1+r).

Proof. If n=0 and r=0, then c(n-1+r,r) = c(-1,0)=1, agreeing with our convention that there is exactly one
0-multiset. If n=0 and r>0, c(n-1+r,r) =0, agreing with the fact that there is no way to choose an
assortment of r>0 object from n=0 objects. It remains to consider the case n>0. We can think of an r-
multiset in terms of a menu. Our menu will have n colums labeled x1,x2, … , xn. To construct a multiset,
we place r stars into the colums. Since we allow repetition, we may place more than one star in a column.
Since we allow repetition, we may place more than one star in a colum. Since we do not consider order,
the stars are identical. For example, if n=2 and r=4, then the menu corresponding to the multiset
consisting of three x1’s and one x2 is given in figure 2-5(a).
Conversely, the multiset corresponding to the menu given in Figure 2-5 (b) consist of four X2’s

Clearly, there is a one correspondence between the menus containing r stars ad the collection of r-
multisets, and hence our problem has been reduced to determining the number of such menus. If we make
the convention that the first colum stands for x1, the second for x2, and so on, then we may eliminate the
column labels and the cross line. For example, the menu given in Figure 2-5 © I represented by the
arrangement of stars and colum bars given in Figure 2-5(d).

Since we need n-1 column bars to form n columns and r stars to denote r object, the problem has been
reduced to determining the number of arrangements or r identical stars and n-1 identical bars. Imagine a
row of n-1+r spaces.into the spaces we wish to place r stars and n-1 bars, one object per space. We divide
this placement into two stages: first we place the stars; and then we place the bars. The stars are identical
so their placement is equivalent to picking the r space into which they will be placed. By the previous
proposition, this can be done in C(n-1+r,r) ways. Now the bars are identical so their placement is
equivalent to picking the n-1 spaces into which they will be placed. But at the second stage there are only
n-1 spaces left, and thus there is one way of choosing the spaces for the bars. By the rule of product, there
are C(n-1+r,r) menus with r stars and n colums, and hence C(n-1+r,r) r-multisets from n object. Q.E.D

The factorial notationsprovides compact factorial representations for the formulas for r-permutations and
r-combination. For natural numbers ______. It follows imaditely that for natural numbers ______. Notice
that the special cases ______ make use of the definition ____. For the most part, we will be using the
expressions __ and __ when n and r are natural numbers with __.

In the proof of the preposition 2-4, we could have chosen the spaces for the bars first. This yields an
answer of ____ , and hence _____. The letter equation is a special case of the following combinatorial
identity.

Proposition 2-5 ____

Proof. We can, of course, appreal to the factorial representations, but we wish to encourage the use of
combinatorial reasoning. Suppose we have n people. The left-hand side is the number of different groups
with r people, and the right-hand side is the number of different groups with n – r people. But these two
collections of groups can be placed into one-one correspondence by letting a group with r people
correspond to the group containing the other n – r people.Q.E.D.

We will study combinatorial identities later. We finish this section with a few simple examples involving
our formulas.
2.3.2. The Distribution Model of Counting

In this section, we present another view of the four basic problems introduced in the last section. Suppose
that we have r balls to be distributed into n distinct cells (we consider identical cells later). In how many
ways can this be done? This distribution problem is also known as the occupancy problem or allocation
problem. As stated the problem is not completely specified, in particular, the phrase r balls to be
distributed is ambiguous.

1. Do we consider the balls to be distinct or identical ?

2. Do we allow any number of balls per cell (nonexclusive occupancy), or do we allow at most one
ball per cell (exclusive occupancy)?

Since there are two answers to each questions, the rule of product says that our original problem is
actually made up of four different problems.

1) How many ways are there to distribute r distinct balls into n distinct cells with any number of
balls per cell?
2) How many ways are there to distribute r distinct balls into n distinct cells with at most one ball
per cell ?
3) How many ways are there to distribute r identical balls into n distinct cells with at most one ball
per cell ?
4) How many ways are there to distribute r identical balls into n distinct cells with any number of
balls per cell?

Example 2.3.8

Figure 2-6 ilustrates the four different problems and their solutions for the case n = 3 and r = 2.

In the previous example, we use explicit enumeration to solve each of the four problems. Fortunately, it is
easy to derive formulas solving each of the problems; in fact, all the work was done in the last section.
Consider, for example, n=3 and r=2. We have two models of counting ; one involves distributing two
balls into three distinct cells and the other involves picking two objects from {x1, x2,x3}. It is easy to see
that the two models are equivalent. We let Xi correspond to the ith cell. If the balls are distinct, we think
of ball number one as corresponding to the first position in an arrangement and ball number one as
corresponding to the second position ; that is, placing ball number one into the ith cell corresponds to
placing xi in the first position of the arrangement and placing ball number two into the ith cell
corresponds to placing xi, in the second position of the arrangement. If the balls are identical, then there is
no position number and placing a ball in the ith cell corresponds to piking xi, without regard to order.
Clearly, the questions of exclusive occupancy refers to the questions of repetition. In particular, exclusive
occupancy corresponds to no repetition. The reader should carefully compare examples 2.3.1 and 2.3.8 to
see that the two model are equivalent.

Recall questions (i) and (ii) and problems (1)-(4) described in the last section. The reasoning of the
preceding paragraph shows that questions (i) and (i)’ are asking the same thing and similarliy for
questions (ii) and (ii). Also the answer to problems (i) and (i)’ are the same, and similarly for the other
problem. Consequently, we have the following propositions.
Propositions 2-6. There are nr ways to distributor r distinct balls into n distinct cells with any number of
balls per cell.

Propositions 2-7. There are P(n, r) ways to distribute r distinct balls into n distinct cells with at most one
ball per cell.

Propositions 2-8. There are (n/r) ways to distribute r identical balls into n distinct cells with at most one
balls per cell.

Propositions 2-9. There are ______ ways to distribute r identical balls into n distinct cells with any
number of balls per cell.

We finish the section with some examples.

Example 2.3.9

Problem. State an equivalent distribution version of the following : arrange two identical A’s, there
identical B’s, and four identical C’s.

Solution. One answer is : distribute nine distinct balls (one for each position in the arrangement) into three
distinct cells (one for each type of letter) with exactly two balls in the first cell, there balls in the second
cell, and four balls in third cell.

Another possibility is: distribute twi identical type A balls, three identical type B balls, and four identical
type C balls into nine distinct cells (one for each position in the arrangement) with exactly one ball per
cell.

Example 2.3.10

Problem. What is the probability that exactly one cell is empty if ten identical balls are distributed
randomly into five distinct cells?

Solution. There are C(5-1+10,10) ways to distribute ten identical balls into five distinct cells with any
number of ball per cell. Next we determine the number of ways to distribute ten identical balls into five
distinct cells with exactly one empty cell. We decompose the construction of such a distribution into three
stages. First we pick the empty cell in one of C (5,1) ways. Next we make sure that the remaining four
cells are nonempty by placing one ball into each of these cells. Since the balls are identical, this can be
done in only one way. Finally, we distribute the remaining six identical balls into the four distinct cells
with any number of balls per cell in one of C (4-1 + 6,6) ways. By the rule of product, there are 5x1xC(4-
1+6,6) ways to distribute ten identical balls into five distict cells with exactly one empty cell, and hence
the probability is 5 x C (4-1 + 6,6) / C (5-1 + 10,10) = 5 x 84 / 1001 = .491 …
Remember this trick of filling in the nonempty cells.
Example 2.3.11. The ‘Real World’

We have been regularly appliying our work to the real world. For the most part, it is easy to see wheter
problems involve sequences, permutations, combinations or multisets, but this in not always the case.

Problem : Consider a “real world” system in which r particles are distributed among n distinct states. A
configuration of the entire system is given by a distribution of particles among the various states. For
example, the particles may be the atoms or molecules of an ideal gas at a given temperature and the state
may be particular energy levels. As another example, the particles may be electrons and the states ay be
the energy levels in a given atom. As yet another example, the particles may be photons and the states
may be energy levels. How many configurations of the system are there?

Discussion. As stated, the problem is not well posed because we do not know wheter to consider the
particles to be identical or distinct, and wheter or not there can be more than one particles in a given state.
Don’t let the ambiguity of the English language undermine your understanding of the mathematical
concepts. It is good practice to consider different interpretations of an unclear problem. A major purpose
of this material is to learn how specify (combinatorial) problem precisely.

As we know, there are four possible answers depending on whether we are viewing the configuration as
sequences, permutations, combinations, or multisets. Physicists have specifically considered three of
these possibilities.

If the particles are distinct and any number of particles may have a given state, then there are nr
configurations. Systems statisfying this assumption are said to be described by Maxwell-Boltzmann
Statistics, and this corresponds to viewing the configurations as multisets.

If the particles are identical and any number of particles may have a given state, then there are __
configurations. System statisfying this assumption are said to be described by Bose-Einstein statistics, and
this corresponds to viewing the configurations as multisets.

If the particles are identical and at most one particle may have a given state, then there are __
configurations. System statisfying this assumption are said to be described by Ferni-Dirac Statistics, and
this corresponds to viewing the configurations as combinations.

Notice that phsycists have not given a name to the situation described by permutations.
Sometimes it is easy to see which assumption should be made, but it is important to realize that there may
not be any a priori reasons for closing one assumption over another. The correct choice in a given ‘real
world’ situation may depend on which assumptions correspond to empirical knowledge. For example, the
atoms or molecules of an ideal gas at a given temperature are best described by Maxwell-Boltzmann
statistics, the distributions of photons into energy levels obey Bose-Einstein statistics, and the
distributions of electrons into the energy levels of an atom is best described by Ferni-Dirac statistics.

In a given ‘real world’ problem the student must make a reasonable choice between alternatives
or, if no obvious choice is available, specifically describe aby assumptions being made.

At this point, the careful reader may wonder if any sense can be made out of the distribution of
balls into identical cells. Consider the distribution of distinct balls into identical cells. Now there are four
distributions of two distinct balls into two distinct cells with any number of balls per cell : ball one in cell
one and cell two in cell two; ball one in the cell two and ball two in cell one; both balls in the first cell;
and both balls in the second cell. By identical cells, we mean that the first two cases are indistinguishable
and the last two cases are indistinguishable; that is , there are two distributions of two distinct balls into
two identical cells: each ball in its own cell; both balls in the same cell. We can also view this in terms of
set decompositions. A decomositons of {x1, x2, …, xr} is a partition into subsets (remember that in a
partition the subsets are nonempty). For example, there are five decomositions of { x1, x2, x3 }: { x1, x2, x3
}; { x1}, { x2}, { x3}; { x1}, { x2, x3}; { x2}, { x1, x3}; and { x3}, { x1, x2}. We can view the distribution of r
distinct objects into n identical cells as the decomposition of {x1, x2, …, xr} into at most n subsets by
letting ball I represent xi, and viewing the balls in a given nonempty cell as a subset. For example, in the
case r = n = 2, the two distributions discussed above correspond to { x1}, { x2} and { x1, x2 }. Set
decompositions are discussed further in Section 3.5.

Next we consider the distributions of identical balls into identical cells. There are three
distributions of three identical balls into three identical cells: all balls in a single cell; two balls in one cell
and one ball in another ; and each ball in its own cell. The distributions of identical balls into identical cell
can be viewed in terms of the partitions of an integer. A partition of a positive integer r is a way of
writing r as a sum of positive integers (called parts) in decreasing order. For example, there are three
partitions of 3:3; 2 + 1; 1 + 1 + 1. Now the distributions of r ≥ 1 identical balls into n ≥ 1 identical cells,
may be viewed as a partition of r into at most n parts by letting the number of balls in a given nonempty
cell correspond to a part. For example with r = n = 3, the three distributions discussed above correspond
to the partitions of 3. Partitions are discussed further in sections 3.6.

At this point, we remind the reader of the six interpetations of the distribution problem.
Distribution of distinct balls into distinct cells with any number of balls per cell correspond to sequences.
Distributions of distinct balls into distinct cells with at most one ball per cell correspond to permutations.
Distributions of identical balls into distinct cells with at most one ball per cell correspond to
combinations. Distributions of identical balls into distinct cell with any number of balls per cell
correspond to multisets. Distribution of distinct balls into identical cells correspond to set decompositions.
Distributions of identical balls into identical cells correspond to pastitions of integers.
Terjemahan :

Therminologi ini, meskipun tepat biasanya tidak digunakan dalam pernyataan masalah, dan siswa harus
membaca masalah dengan hati-hati untuk memutuskan jenis mana yang terlibat. Kami juga mencatat
bahwa beberapa penulis lebih menyukai therminology lain. Sebagai contoh, r-kombinasi sering disebut r-
set, dan r-multiset sering disebut r-assortment. Sekali lagi, kami menekankan bahwa tujuan penalaran
kombinatorial adalah untuk menemukan korespondensi antara masalah yang sedang dipertimbangkan dan
beberapa masalah lainnya. Secara khusus, kami sering mencoba untuk mengurangi masalah menjadi satu
atau lebih dari empat masalah yang dijelaskan di atas.

Contoh 2.3.1

Kami mengambil sampel dua objek dari {x1, x2, x3}; yaitu, n = 3 dan r = 2. Gambar 2-4 menggambarkan
empat masalah berbeda dan solusinya. Perhatikan bahwa urutan dan permutasi diberikan dengan
membuat daftar elemen dalam urutan yang benar, dan kombinasi dan multiset menggunakan notasi
braket.

Pada titik ini, pembaca yang cermat sering bertanya tentang kasus r = 0. Bagaimana sikap kita tentang
sampel ukuran 0? Seperti yang telah disebutkan, r-kombinasi dapat dilihat sebagai set kosong. Karena
hanya ada satu set kosong, kita katakan bahwa hanya ada satu kombinasi 0. Matematikawan juga
mengatakan bahwa ada tepat satu 0-urutan, satu 0-permutasi, dan satu 0-multiset. Sementara kasus
terakhir mungkin tampak kurang intuitif daripada kasus untuk kombinasi, mereka memberikan
keseragaman.

Dalam contoh sebelumnya, kami menentukan jumlah solusi untuk masing-masing dari empat masalah
kami dengan penghitungan eksplisit. Kami sekarang mengembangkan formula yang memberikan jumlah
solusi untuk setiap masalah.

Proposisi 2-1. Jumlah r-urutan dari objek n adalah nr.

Bukti. Jika r = 0, maka nr = 1, menyetujui dengan konvensi kami bahwa ada tepat satu permutasi-0. Jika
r> n, maka P (n, r) = 0, sesuai dengan fakta bahwa tidak ada cara untuk mengambil r objek yang berbeda
dari n <r objek. Masih mempertimbangkan kasus di mana n ≥ 1. Heuristik penting menghitung adalah
membayangkan konstruksi urutan-r menjadi tahap-r - kita memilih objek pertama dan kemudian yang
kedua, dan seterusnya. Pada setiap tahap kami memiliki n pilihan, dan karenanya aturan produk
mengatakan bahwa konstruksi ini dapat dilakukan dengan cara baru. P.E.

Proposisi 2-2. Jumlah r-permutasi dari objek n adalah n (n - 1) (n - 2) ... (n - r + 1).

Kami menunjukkan ekspresi terakhir dengan P (n, r). Jika r = 0, maka P (n, r) adalah produk hampa, yang
merupakan definisi satu.

Bukti. Jika r = 0, maka P (n, r) = 1, sesuai dengan konvensi kami bahwa hanya ada satu permutasi-0. Jika
r> n, maka P (n, r) = 0, setuju dengan fakta bahwa tidak ada cara untuk mengambil r objek yang berbeda
dari n <r objek. Masih mempertimbangkan kasus di mana n ≥ r ≥ 1. Kita dapat menguraikan konstruksi
permutasi-r menjadi tahap r - kita memilih objek pertama dan kemudian objek kedua BERBEDA, dan
seterusnya. Kami memiliki n pilihan di tahap pertama, n - 1 pilihan di tahap kedua, ..., dan n - r + 1
pilihan di tahap ke - r. Karenanya aturan produk mengatakan bahwa konstruksi ini dapat dilakukan
dengan cara n (n -1) (n - 2) ... (n - r + 1). P.E.

Ketika r = n, kami memiliki sejumlah cara untuk mengatur n objek yang berbeda dalam satu baris. Kami
merujuk pada pengaturan seperti permutasi serta permutasi-n. Secara khusus, jumlah cara untuk mengatur
n orang yang berbeda secara berurutan adalah n (n - 1) ... 1. Ungkapan terakhir ini muncul begitu sering
sehingga menerima nama khusus, n! disebut n faktorial. Misalnya, 6 orang dapat diatur dalam 6! = 6 x 5 x
4 x 3 x 2 x 1 = 720 cara. Perhatikan bahwa n! = n (n - 1)! Untuk n> 1. Kami mendefinisikan 0! = 1
sehingga n! = r (n - 1)! Untuk n ≥ 1.

Perhatikan bahwa definisi P (n, r) = n (n - 1) ... (n - r + 1) dapat diterapkan pada bilangan real n dan
bilangan r alami (walaupun kita hanya memiliki interpretasi fisik untuk bilangan asli n dan r ). misalnya,
P (-1, 0) = 1 dan P (2,3) = 0.

Proposisi 2-3. Jumlah r-kombinasi dari n objek adalah

P (n, r) / r !.

Kami menunjukkan ekspresi huruf dengan C (n, r) atau (n / r) disebut koofisiensi binominal.

Bukti. Jika r> n, maka C (n, r) = 0, setuju dengan fakta bahwa tidak ada r-kombinasi ketika r> n. tetap
mempertimbangkan kasus n ≥ r. Mari kita pertimbangkan contoh khusus. Jika n = 3 dan r = 2, maka kita
telah melihat bahwa ada enam permutasi-2.

Sudah jelas bahwa permutasi telah menyertakan 2 pengaturan untuk setiap kombinasi. Secara umum,
permutasi akan mencakup r! pengaturan untuk setiap r-kombinasi karena elemen r dalam kombinasi dapat
diatur dalam r! cara. Untuk mengkompensasi, rumus untuk P (n, r) harus dibagi dengan r !, dan karenanya
ada P (n, r) / r! r-kombinasi dari n objek. P.E.

Perhatikan bahwa definisi C (n, r) = (n / r) = dapat diterapkan ke bilangan real n dan bilangan asli n dan r.
sebagai contoh

Preposisi 2-4. jumlah r-multiset dari n objek adalah (n-1 + r).

Bukti. Jika n = 0 dan r = 0, maka c (n-1 + r, r) = c (-1,0) = 1, setuju dengan konvensi kami bahwa hanya
ada satu 0-multiset. Jika n = 0 dan r> 0, c (n-1 + r, r) = 0, setuju dengan kenyataan bahwa tidak ada cara
untuk memilih bermacam-macam objek r> 0 dari n = 0 objek. Masih mempertimbangkan kasus n> 0. Kita
dapat memikirkan r-multiset dalam hal menu. Menu kami akan memiliki n kolom yang berlabel x1,
x2,…, xn. Untuk membangun multiset, kami menempatkan r bintang ke dalam kolom. Karena kami
mengizinkan pengulangan, kami dapat menempatkan lebih dari satu bintang di kolom. Karena kami
mengizinkan pengulangan, kami dapat menempatkan lebih dari satu bintang di sebuah kolom. Karena
kami tidak mempertimbangkan keteraturan, bintang-bintang itu identik. Misalnya, jika n = 2 dan r = 4,
maka menu yang sesuai dengan multiset yang terdiri dari tiga x1 dan satu x2 diberikan pada Gambar 2-5
(a).

Sebaliknya, multiset yang sesuai dengan menu yang diberikan pada Gambar 2-5 (b) terdiri dari empat X2
Jelas, ada satu korespondensi antara menu yang berisi r bintang dan koleksi r-multiset, dan karenanya
masalah kami telah berkurang untuk menentukan jumlah menu tersebut. Jika kita membuat konvensi
bahwa colum pertama adalah singkatan dari x1, yang kedua untuk x2, dan seterusnya, maka kita dapat
menghilangkan label kolom dan garis silang. Sebagai contoh, menu yang diberikan pada Gambar 2-5 ©
saya diwakili oleh susunan bintang dan bar colum yang diberikan pada Gambar 2-5 (d).

Karena kita membutuhkan n-1 kolom kolom untuk membentuk n kolom dan r bintang untuk
menunjukkan r objek, masalahnya telah dikurangi untuk menentukan jumlah pengaturan atau r bintang
identik dan n-1 bar identik. Bayangkan deretan ruang n-1 + r. Ke dalam ruang yang ingin kita tempatkan
bintang r dan b-1, satu objek per ruang. Kami membagi penempatan ini menjadi dua tahap: pertama-tama
kita menempatkan bintang-bintang; dan kemudian kita menempatkan jeruji. Bintang-bintang itu identik
sehingga penempatannya setara dengan memilih r ruang di mana mereka akan ditempatkan. Dengan
proposisi sebelumnya, ini dapat dilakukan dengan cara C (n-1 + r, r). Sekarang bilah identik sehingga
penempatannya setara dengan memilih ruang n-1 di mana mereka akan ditempatkan. Tetapi pada tahap
kedua hanya ada n-1 ruang yang tersisa, dan dengan demikian ada satu cara untuk memilih ruang untuk
bar. Sesuai aturan produk, ada menu C (n-1 + r, r) dengan r bintang dan n kolom, dan karenanya C (n-1 +
r, r) r-multiset dari n objek. P.E.

Notasi faktorial menyediakan representasi faktorial ringkas untuk rumus untuk r-permutasi dan r-
kombinasi. Untuk bilangan asli ______. Ini mengikuti bahwa untuk bilangan alami _______. Perhatikan
bahwa kasus khusus _______ menggunakan definisi ____. Untuk sebagian besar, kita akan menggunakan
ekspresi __ dan __ ketika n dan r adalah bilangan asli dengan __.

Dalam bukti preposisi 2-4, kita bisa memilih spasi untuk bar terlebih dahulu. Ini menghasilkan jawaban
____, dan karenanya _____. Persamaan huruf adalah kasus khusus dari identitas kombinatorial berikut.

Proposisi 2-5 ____

Bukti. Kita bisa, tentu saja, cocok dengan representasi faktorial, tetapi kami ingin mendorong penggunaan
alasan kombinatorial. Misalkan kita memiliki n orang. Sisi kiri adalah jumlah kelompok yang berbeda
dengan r orang, dan sisi kanan adalah jumlah kelompok yang berbeda dengan n - r orang. Tetapi dua
kumpulan kelompok ini dapat ditempatkan ke dalam korespondensi satu-satu dengan membiarkan grup
dengan r orang-orang sesuai dengan grup yang berisi n-r orang lain. Q.E.D.

Kami akan mempelajari identitas kombinatorial nanti. Kami menyelesaikan bagian ini dengan beberapa
contoh sederhana yang melibatkan formula kami.
2.3.2. Model Distribusi Menghitung

Di bagian ini, kami menyajikan pandangan lain tentang empat masalah dasar yang diperkenalkan di
bagian terakhir. Misalkan kita memiliki bola r untuk didistribusikan ke dalam n sel yang berbeda (kita
anggap sel identik nanti). Dalam berapa banyak cara ini bisa dilakukan? Masalah distribusi ini juga
dikenal sebagai masalah hunian atau masalah alokasi. Seperti yang dinyatakan masalah tidak sepenuhnya
ditentukan, khususnya, frasa r bola yang akan didistribusikan adalah ambigu.

1. Apakah kita menganggap bola itu berbeda atau identik?

2. Apakah kita mengizinkan jumlah bola per sel (hunian non-eksklusif), atau apakah kita mengizinkan
paling banyak satu bola per sel (hunian eksklusif)?

Karena ada dua jawaban untuk setiap pertanyaan, aturan produk mengatakan bahwa masalah awal kami
sebenarnya terdiri dari empat masalah yang berbeda.

1) Berapa banyak cara yang ada untuk mendistribusikan r bola berbeda ke dalam n sel yang berbeda
dengan jumlah bola per sel?

2) Berapa banyak cara yang ada untuk mendistribusikan r bola yang berbeda ke dalam n sel yang berbeda
dengan paling banyak satu bola per sel?

3) Berapa banyak cara yang ada untuk mendistribusikan bola identik ke dalam n sel berbeda dengan
paling banyak satu bola per sel?

4) Berapa banyak cara yang ada untuk mendistribusikan r bola identik ke dalam n sel yang berbeda
dengan jumlah bola per sel?

Contoh 2.3.8

Gambar 2-6 mengilustrasikan empat masalah yang berbeda dan solusinya untuk kasus n = 3 dan r = 2.

Pada contoh sebelumnya, kami menggunakan enumerasi eksplisit untuk menyelesaikan masing-masing
dari empat masalah. Untungnya, mudah untuk mendapatkan formula yang memecahkan setiap masalah;
pada kenyataannya, semua pekerjaan dilakukan di bagian terakhir. Pertimbangkan, misalnya, n = 3 dan r
= 2. Kami memiliki dua model penghitungan; yang satu melibatkan pendistribusian dua bola menjadi tiga
sel yang berbeda dan yang lainnya melibatkan pengambilan dua objek dari {x1, x2, x3}. Sangat mudah
untuk melihat bahwa kedua model itu setara. Kami membiarkan Xi sesuai dengan sel engan. Jika bola
berbeda, kami menganggap bola nomor satu sesuai dengan posisi pertama dalam suatu pengaturan dan
bola nomor satu sesuai dengan posisi kedua; yaitu, menempatkan bola nomor satu ke dalam sel ith sesuai
dengan menempatkan xi di posisi pertama pengaturan dan menempatkan bola nomor dua ke dalam sel ith
sesuai dengan menempatkan xi, di posisi kedua pengaturan. Jika bola identik, maka tidak ada nomor
posisi dan menempatkan bola di sel ih sesuai dengan piking xi, tanpa memperhatikan urutan. Jelas,
pertanyaan tentang hunian eksklusif mengacu pada pertanyaan tentang pengulangan. Secara khusus,
hunian eksklusif sesuai dengan tidak ada pengulangan. Pembaca harus hati-hati membandingkan contoh
2.3.1 dan 2.3.8 untuk melihat bahwa kedua model itu setara.
2.3.2. Model Distribusi Menghitung

Di bagian ini, kami menyajikan pandangan lain tentang empat masalah dasar yang diperkenalkan di
bagian terakhir. Misalkan kita memiliki bola r untuk didistribusikan ke dalam n sel yang berbeda (kita
anggap sel identik nanti). Dalam berapa banyak cara ini bisa dilakukan? Masalah distribusi ini juga
dikenal sebagai masalah hunian atau masalah alokasi. Seperti yang dinyatakan masalah tidak sepenuhnya
ditentukan, khususnya, frasa r bola yang akan didistribusikan adalah ambigu.

1. Apakah kita menganggap bola itu berbeda atau identik?

2. Apakah kita mengizinkan jumlah bola per sel (hunian non-eksklusif), atau apakah kita mengizinkan
paling banyak satu bola per sel (hunian eksklusif)?

Karena ada dua jawaban untuk setiap pertanyaan, aturan produk mengatakan bahwa masalah awal kami
sebenarnya terdiri dari empat masalah yang berbeda.

1) Berapa banyak cara yang ada untuk mendistribusikan r bola berbeda ke dalam n sel yang berbeda
dengan jumlah bola per sel?

2) Berapa banyak cara yang ada untuk mendistribusikan r bola yang berbeda ke dalam n sel yang berbeda
dengan paling banyak satu bola per sel?

3) Berapa banyak cara yang ada untuk mendistribusikan bola identik ke dalam n sel berbeda dengan
paling banyak satu bola per sel?

4) Berapa banyak cara yang ada untuk mendistribusikan r bola identik ke dalam n sel yang berbeda
dengan jumlah bola per sel?

Contoh 2.3.8

Gambar 2-6 mengilustrasikan empat masalah yang berbeda dan solusinya untuk kasus n = 3 dan r = 2.

Ingat pertanyaan (i) dan (ii) dan masalah (1) - (4) yang dijelaskan di bagian terakhir. Penalaran paragraf
sebelumnya menunjukkan bahwa pertanyaan (i) dan (i) 'menanyakan hal yang sama dan juga untuk
pertanyaan (ii) dan (ii). Juga jawaban untuk masalah (i) dan (i) 'sama, dan sama untuk masalah lainnya.
Akibatnya, kami memiliki proposisi berikut.

Proposisi 2-6. Ada cara-cara baru untuk mendistribusikan r bola yang berbeda ke dalam sel yang berbeda
dengan jumlah bola per sel.

Proposisi 2-7. Ada P (n, r) cara untuk mendistribusikan r bola yang berbeda ke dalam n sel yang berbeda
dengan paling banyak satu bola per sel.

Proposisi 2-8. Ada (n / r) cara untuk mendistribusikan r bola identik ke dalam n sel berbeda dengan paling
banyak satu bola per sel.

Proposisi 2-9. Ada banyak cara untuk mendistribusikan r bola identik ke dalam n sel berbeda dengan
jumlah bola per sel.
Kami menyelesaikan bagian ini dengan beberapa contoh.

Contoh 2.3.9

Masalah. Nyatakan versi distribusi yang setara dari yang berikut: atur dua A identik, ada B identik, dan
empat C identik.

Larutan. Satu jawaban adalah: mendistribusikan sembilan bola berbeda (satu untuk setiap posisi dalam
pengaturan) menjadi tiga sel berbeda (satu untuk setiap jenis huruf) dengan tepat dua bola di sel pertama,
ada bola di sel kedua, dan empat bola di ketiga sel.

Kemungkinan lain adalah: mendistribusikan bola tipe A yang identik, tiga bola tipe B yang identik, dan
empat bola tipe C yang identik ke dalam sembilan sel berbeda (satu untuk setiap posisi dalam pengaturan)
dengan tepat satu bola per sel.

Contoh 2.3.10

Masalah. Berapa probabilitas bahwa tepat satu sel kosong jika sepuluh bola identik didistribusikan secara
acak ke dalam lima sel yang berbeda?

Larutan. Ada C (5-1 + 10,10) cara untuk mendistribusikan sepuluh bola identik menjadi lima sel yang
berbeda dengan jumlah bola per sel. Selanjutnya kita menentukan jumlah cara untuk mendistribusikan
sepuluh bola identik menjadi lima sel berbeda dengan tepat satu sel kosong. Kami menguraikan
konstruksi distribusi tersebut menjadi tiga tahap. Pertama-tama kita memilih sel kosong dengan salah satu
cara C (5,1). Selanjutnya kita memastikan bahwa empat sel yang tersisa adalah kosong dengan
menempatkan satu bola ke masing-masing sel ini. Karena bola identik, ini bisa dilakukan hanya dengan
satu cara. Akhirnya, kami mendistribusikan enam bola identik yang tersisa ke dalam empat sel berbeda
dengan jumlah bola per sel dalam salah satu cara C (4-1 + 6,6). Menurut aturan produk, ada 5x1xC (4-1 +
6,6) cara untuk mendistribusikan sepuluh bola identik menjadi lima sel pembeda dengan tepat satu sel
kosong, dan karenanya probabilitasnya adalah 5 x C (4-1 + 6,6) ) / C (5-1 + 10.10) = 5 x 84/1001 =
.491…

Ingat trik mengisi sel tidak kosong ini.

Contoh 2.3.11. Dunia nyata'

Kami telah secara teratur mengaplikasikan pekerjaan kami ke dunia nyata. Untuk sebagian besar, mudah
untuk melihat apakah masalah melibatkan urutan, permutasi, kombinasi atau multiset, tetapi ini tidak
selalu terjadi.

Masalah: Pertimbangkan sistem "dunia nyata" di mana r partikel didistribusikan di antara n keadaan yang
berbeda. Konfigurasi seluruh sistem diberikan oleh distribusi partikel di antara berbagai keadaan. Sebagai
contoh, partikel dapat berupa atom atau molekul gas ideal pada suhu tertentu dan keadaannya mungkin
tingkat energi tertentu. Sebagai contoh lain, partikel-partikelnya mungkin elektron dan keadaannya adalah
tingkat energi dalam atom yang diberikan. Sebagai contoh lain, partikel mungkin foton dan negara
mungkin tingkat energi. Berapa banyak konfigurasi sistem yang ada?

Diskusi. Seperti yang dinyatakan, masalahnya tidak diajukan dengan baik karena kita tidak tahu apakah
menganggap partikel itu identik atau berbeda, dan apakah ada lebih dari satu partikel dalam keadaan
tertentu. Jangan biarkan ambiguitas bahasa Inggris merusak pemahaman Anda tentang konsep
matematika. Merupakan praktik yang baik untuk mempertimbangkan interpretasi yang berbeda dari
masalah yang tidak jelas. Tujuan utama dari materi ini adalah untuk mempelajari bagaimana menentukan
masalah (kombinatorial) secara tepat.

Seperti yang kita ketahui, ada empat kemungkinan jawaban tergantung pada apakah kita melihat
konfigurasi sebagai urutan, permutasi, kombinasi, atau multiset. Fisikawan telah secara khusus
mempertimbangkan tiga kemungkinan ini.

Jika partikelnya berbeda dan sejumlah partikel mungkin memiliki keadaan tertentu, maka ada konfigurasi
nr. Sistem yang memenuhi asumsi ini dikatakan dijelaskan oleh Maxwell-Boltzmann Statistics, dan ini
sesuai dengan melihat konfigurasi sebagai multiset.

Jika partikel identik dan sejumlah partikel mungkin memiliki keadaan tertentu, maka ada konfigurasi __.
Sistem yang memenuhi asumsi ini dikatakan dijelaskan oleh statistik Bose-Einstein, dan ini sesuai dengan
melihat konfigurasi sebagai multiset.

Jika partikel identik dan paling banyak satu partikel mungkin memiliki keadaan tertentu, maka ada
konfigurasi __. Sistem yang memenuhi asumsi ini dikatakan dijelaskan oleh Ferni-Dirac Statistics, dan ini
sesuai dengan melihat konfigurasi sebagai kombinasi.

Perhatikan bahwa ahli fisika belum memberi nama pada situasi yang dijelaskan dengan permutasi.
Terkadang mudah untuk melihat asumsi mana yang harus dibuat, tetapi penting untuk menyadari bahwa
mungkin tidak ada alasan apriori untuk menutup satu asumsi di atas asumsi lainnya. Pilihan yang benar
dalam situasi 'dunia nyata' tertentu dapat bergantung pada asumsi mana yang sesuai dengan pengetahuan
empiris. Sebagai contoh, atom atau molekul gas ideal pada suhu tertentu paling baik dijelaskan oleh
statistik Maxwell-Boltzmann, distribusi foton ke tingkat energi mematuhi statistik Bose-Einstein, dan
distribusi elektron ke tingkat energi atom adalah paling baik dijelaskan oleh statistik Ferni-Dirac.

Dalam masalah 'dunia nyata' yang diberikan, siswa harus membuat pilihan yang masuk akal di antara
alternatif atau, jika tidak ada pilihan yang jelas tersedia, jelaskan secara khusus asumsi yang dibuat.

Pada titik ini, pembaca yang cermat mungkin bertanya-tanya apakah ada akal yang dapat dibuat dari
distribusi bola ke dalam sel yang identik. Pertimbangkan distribusi bola yang berbeda ke dalam sel yang
identik. Sekarang ada empat distribusi dari dua bola yang berbeda menjadi dua sel yang berbeda dengan
jumlah bola per sel: bola satu di sel satu dan sel dua di sel dua; bola satu di sel dua dan bola dua di sel
satu; kedua bola di sel pertama; dan kedua bola di sel kedua. Dengan sel identik, kami maksudkan bahwa
dua kasus pertama tidak dapat dibedakan dan dua kasus terakhir tidak dapat dibedakan; yaitu, ada dua
distribusi dari dua bola yang berbeda menjadi dua sel yang identik: masing-masing bola di selnya sendiri;
kedua bola di sel yang sama. Kami juga dapat melihat ini dalam hal dekomposisi yang ditetapkan.
Decomositons dari {x1, x2, ..., xr} adalah partisi menjadi himpunan bagian (ingat bahwa dalam suatu
partisi himpunan bagian adalah kosong). Misalnya, ada lima dekomosisi {x1, x2, x3}: {x1, x2, x3}; {x1},
{x2}, {x3}; {x1}, {x2, x3}; {x2}, {x1, x3}; dan {x3}, {x1, x2}. Kita dapat melihat distribusi r objek
yang berbeda menjadi n sel identik sebagai dekomposisi {x1, x2, ..., xr} ke dalam paling banyak n
himpunan bagian dengan membiarkan bola yang saya wakili xi, dan melihat bola di sel yang kosong
sebagai subset . Misalnya, dalam kasus r = n = 2, dua distribusi yang dibahas di atas sesuai dengan {x1},
{x2} dan {x1, x2}. Kumpulan dekomposisi dibahas lebih lanjut dalam Bagian 3.5.

Selanjutnya kita mempertimbangkan distribusi bola identik ke dalam sel identik. Ada tiga distribusi dari
tiga bola identik menjadi tiga sel identik: semua bola dalam satu sel; dua bola di satu sel dan satu bola di
yang lain; dan setiap bola di selnya sendiri. Distribusi bola identik ke dalam sel identik dapat dilihat dari
segi partisi integer. Partisi dari bilangan bulat positif r adalah cara penulisan r sebagai jumlah dari
bilangan bulat positif (disebut bagian) dalam urutan menurun. Sebagai contoh, ada tiga partisi 3: 3; 2 +1;
1 + 1 + 1. Sekarang distribusi r ≥ 1 bola identik ke n ≥ 1 sel identik, dapat dilihat sebagai partisi r menjadi
paling banyak n bagian dengan membiarkan jumlah bola dalam sel kosong yang diberikan sesuai dengan
bagian . Misalnya dengan r = n = 3, tiga distribusi yang dibahas di atas sesuai dengan partisi 3. Partisi
dibahas lebih lanjut di bagian 3.6.

Pada titik ini, kami mengingatkan pembaca akan enam interpetasi dari masalah distribusi. Distribusi bola
berbeda menjadi sel berbeda dengan jumlah bola per sel sesuai dengan urutan. Distribusi bola yang
berbeda ke dalam sel yang berbeda dengan paling banyak satu bola per sel sesuai dengan permutasi.
Distribusi bola identik ke dalam sel berbeda dengan paling banyak satu bola per sel sesuai dengan
kombinasi. Distribusi bola identik ke dalam sel berbeda dengan jumlah bola per sel sesuai dengan
multiset. Distribusi bola yang berbeda ke dalam sel yang identik sesuai dengan mengatur dekomposisi.
Distribusi bola identik ke dalam sel identik berhubungan dengan pastor bilangan bulat.