ВУЗ:
Составители:
Рубрика:
22
что первые )1( −
k
покупателей подали в кассу одинаковое количество полтинников
и рублей ),0(
1
=
−k
s а следующий покупатель подал рубль и вынужден ожидать сда-
чу. Определим число траекторий, имеющих общую точку с прямой 1−=y . Поста-
вим в соответствие каждой траектории ,
T
имеющей с прямой 1−=y хотя бы одну
общую точку, ломаную
T
′
по следующему правилу. До первой общей точки с прямой
1−=y ломаная
T
′
совпадает с ,
T
а далее является симметричным отображением
T
относительно прямой 1−=y . Все ломаные
T
′
заканчиваются в точке
)2;( −−+
′
+
nmmnA
mn
, являющейся симметричным отображением точки
mn
A
+
от-
носительно прямой 1−=y . Установленное соответствие является взаимно одно-
значным. Число ломаных типа
T
′
, равно числу ломаных, соединяющих точки O и
mn
A
+
′
. Это число легко подсчитать. Если ломаная
T
′
состоит из y отрезков, на-
правленных вниз, и
x
отрезков, направленных вверх, то
⎩
⎨
⎧
−+=−
+
=
+
,2
,
mnxy
nmyx
откуда получаем .1,1
+
=−= nymx Таким образом, число траекторий, имеющих
общую точку с прямой ,1−=y равно
.
1
+
+
n
mn
C
Следовательно, искомое число траекто-
рий, соответствующих тем способам размещения покупателей, при которых ни один
покупатель не ждет сдачи, равно
.
1
1
1
1
!!
)!(
)!1()!1(
)!(
!!
)!(
1
+
−+
⋅=
⎟
⎠
⎞
⎜
⎝
⎛
+
−
⋅
+
=
−⋅+
+
−
⋅
+
=−
+
−
++
n
mn
C
n
m
mn
mn
mn
mn
mn
mn
CC
m
mn
n
mn
n
mn
Учебное издание
СЕМЕНОВ Алексей Степанович
Четыре лекции по комбинаторике
Методические указания
Редактор Н. А. Евдокимова
Подписано в печать 28.03.2005. Формат 60х84/16.
Печать трафаретная. Бумага офсетная. Ус. печ. л. 1,16.
Уч. – изд. л. 1,00. Тираж 150 экз. Заказ
Ульяновский государственный технический университет
432027, г. Ульяновск, ул. Сев. Венец, д. 32
Типография УлГТУ, 432027, г. Ульяновск, ул. Сев. Венец, д, 32.
