Yulduzlar va chiziqlar - Resources

Bosh sahifa Kurslar Resurslar Masalalar Milliy olimpiada Musobaqalar Reyting

...

Bosh sahifa/Resources/Combinatorics/Yulduzlar va chiziqlar

Yulduzlar va chiziqlar

Introduction

Stars and Bars is a standard combinatorial technique used to count the number of ways to distribute identical objects into distinct containers.

It is especially useful in problems about integer solutions, grouping, and distributions.

Theorem

Problem Statement

Suppose we have $k$ identical objects and want to distribute them into $n$ distinguishable bins.

A convenient way to visualize this is to represent:

each object by a star *
each separator between bins by a bar |

So we arrange:

$k$ stars
$n - 1$ bars

For example, if we place $4$ identical objects into bins, some possible arrangements are:

External Problems

Solve these external problems (e.g., from Codeforces) to reinforce the lesson material:

CODEFORCESKyoya and Colored Balls

3

Each arrangement corresponds to exactly one distribution of the objects into the bins.

So the total number of ways is the number of ways to choose positions for the bars among all $k + n - 1$ positions:

\binom{k + n - 1}{n - 1}

For example, for $k = 4$ and $n = 3$ , the answer is:

\binom{4 + 3 - 1}{3 - 1} = \binom{6}{2} = 15

More General Formulas

The number of ways to distribute $k$ identical objects into $n$ bins is

\binom{n + k - 1}{n - 1}

The number of ways to distribute $k$ identical objects into $n$ bins, with at least one object in each bin, is

\binom{k - 1}{n - 1}

Example Problems

Number of Non-Negative Integer Solutions

Given the equation

x_1 + x_2 + \dots + x_k = n

where $x_i \ge 0$ , count the number of solutions.

We can interpret this as distributing $n$ identical objects into $k$ bins, where the value of $x_i$ is the number of objects placed into the $i$ -th bin.

For example, the solution

1 + 3 + 0 = 4

for $n = 4$ , $k = 3$ can be represented as

\bigstar \; | \; \bigstar \bigstar \bigstar \; |

So this is exactly a Stars and Bars problem.

Therefore, the number of solutions is

\binom{n + k - 1}{k - 1}

Number of Positive Integer Solutions

Given the equation

x_1 + x_2 + \dots + x_k = n

where $x_i \ge 1$ , count the number of solutions.

This version is more restrictive because every variable must be positive. That means every bin must contain at least one object.

Equivalently, in the Stars and Bars picture, we are not allowed to place two bars next to each other, because that would correspond to some $x_i = 0$ .

There are $n - 1$ gaps between the stars, and we need to choose $k - 1$ of them for the bars.

So the answer is

\binom{n - 1}{k - 1}