Integer compositions

Loading...

來自 National Research University Higher School of Economics 的課程

Introduction to Enumerative Combinatorics

63 個評分

National Research University Higher School of Economics

Introduction to Enumerative Combinatorics

63 個評分

Enumerative combinatorics deals with finite sets and their cardinalities. In other words, a typical problem of enumerative combinatorics is to find the number of ways a certain pattern can be formed. In the first part of our course we will be dealing with elementary combinatorial objects and notions: permutations, combinations, compositions, Fibonacci and Catalan numbers etc. In the second part of the course we introduce the notion of generating functions and use it to study recurrence relations and partition numbers. The course is mostly self-contained. However, some acquaintance with basic linear algebra and analysis (including Taylor series expansion) may be very helpful.

從本節課中

Binomial coefficients, continued. Inclusion and exclusion formula.

In the first part of this lecture we will see more applications of binomial coefficients, in particular, their appearance in counting multisets. The second part is devoted to the principle of inclusion and exclusion: a technique which allows us to find the number of elements in the union of several sets, given the cardinalities of all of their intersections. We discuss its applications to various combinatorial problem, including the computation of the number of permutations without fixed points (the derangement problem).

The cab driver problem17:26

Balls in boxes and multisets 110:20

Balls in boxes and multisets 26:04

Integer compositions11:21

Principle of inclusion and exclusion: two examples12:36

Principle of inclusion and exclusion: general statement9:59

The derangement problem19:22

與講師見面

Evgeny Smirnov
Associate Professor
Faculty of Mathematics

[MUSIC]

Another problem closely related to the previous one is the problem of counting

integer compositions.

We define integer composition,

An integer composition,

of n.

Is a presentation of n as an ordered sum of

positive integers is a presentation,

Of n as an ordered,

Sum.

n = n1 + n2 + etc.,

plus nk where all,

As an examples here are also positive integers,

let us list all the compositions of the numbers 1, 2, 3, and 4.

For any quote 1 there is nothing to decompose and

there is only one such composition.

2 can be presented in two different ways,

it is either 2 or 1 + 1.

3 is 2 + 1,

or 1 + 2.

I would like to emphasize once more that

the conversations are defined as ordered sums.

So 2 + 1 and 1 + 2 correspond to two different compositions.

Or 3 can be represented as the sum of three 1s.

We will be dealing unordered sums, later.

And these sums are called partitions as opposed to compositions.

But they will be discussed in lecture seven and they are somewhat more involved.

Okay, what about 4?

4 is, a 4 or a 3 + 1.

Or 1 + 3.

And there is another way of presenting it as the sum of two sums.

Label it 2 + 2, or

this is 2 + 1 + 1,

or it is 1 + 2 + 1,

or 1 + 1 + 2, or 4 x 1.

So we see that the number of

partitions is 1 in this case.

2 in this case.

4 in this case, and 8 in this case,

so it is a natural conjecture

that the number of compositions of

an integer k is a power of 2.

Namely, 2 to the power of k- 1.

And this will be one part of the theorem we are going to prove now.

Theorem, a,

the number of compositions,

Of n is 2 to

the power n- 1.

Part b, consider the number of

compositions with exactly k summands.

And this number is equal

to n- 1, choose k- 1.

(n- 1), which is (k- 1).

The proof we'll use the balls and

boxes construction.

So in this problem can be restated as follows.

Suppose we have n balls which correspond to the number n and

we want to put them into k boxes.

In such a way that all n i's are positive.

This means that no box is allowed to stay empty.

The compositions, Of,

n with the exactly k summands,

Correspond to configurations.

Of n balls inside,

k boxes.

Such that no box is empty.

Such that each box is not empty.

Why do you want to put n balls into k boxes?

So I start each box as non-empty.

This is the same as putting a ball into each box first.

So this last condition will be satisfied automatically.

And we're left with n minus k balls,

which we need to put into k boxes in an arbitrary way,

without other restrictions.

And so this is the same as

the number of configurations,

Of n- k balls.

In k boxes.

And this number, as we know

from the previous part,

is n- k + k- 1.

Choose the numbers of boxes minus 1.

So, choose k- 1, and

this nothing but n- 1 choose k- 1.

Okay, and this was part b and to show that to the total

number of compositions is 2 to the power n- 1.

We just need to sum up these values, For

all possible values of k so,

This was part b and part a, the total number of compositions.

Is, n-1

to 0 plus n-1 to 1 plus etc.,

plus the maximum number of summands

in an integer composition is equal to n well,

this corresponds to representation of n as 1.

So, we sum this up to k equal to n.

So this is, n- 1 choose n -1 and

in the previous lecture we have found the value of this sum.

This is the sum of entries in the n minus first row of the Pascal triangle.

So this is 2 to the power of n- 1.

This is the total number of compositions of a number.

[MUSIC]

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2019 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取