Файл: Голенко Д.И. Статистические модели в управлении производством.pdf

2. Если l>k,

то

разбиение 1-го

порядка

представляет

собой измельчение разбиения k-ro

порядка,

т. е. при/>'г

любые элементы

ял

и Я в из одного класса

1-го порядка

обязательно входят

в один класс

k-ro порядка.

3. Все классы одного порядка

содержат

одинаковое

состоит

из (п—1)!

перестановок;

с другой

стороны, каж­

дый класс 1-го порядка содержит (п—1)

классов 2-го по­

рядка, состоящих из (п—2)!

перестановок и т. д., нако­

нец, имеется п\

классов

(п—1)

порядка, каждый

из кото­

рых содержит ровно одну перестановку.

Внутри каждого класса k-ro порядка классы

(/г+1)-го

порядка

можно

перенумеровать

следующим

образом.

Первым

классом

(&+1)-го

порядка назовем класс с наи­

меньшим

элементом на

(k+l)

месте; вторым

назовем

класс

со

следующим

по

возрастанию

элементом

на

{k+1)

-м месте и т. д.

Для нумерации всех перестановок используются чис­

ла

от

1 до п!; причем

первые

(я—1)! чисел используют­

ся

для

нумерации

перестановок

1-го класса 1-го поряд­

ка;

следующие

(п

1)!

чисел — для нумерации

переста­

новок 2-го класса

1-го

порядка

и т. д., наконец, последние

{п

1)!

чисел используем—

для

нумерации

последнего

п-го

класса 1-го порядка. Далее внутри каждого класса

1-го

порядка—

производим разбиение

на классы

2-го

порядка

и распределяем между ними имеющиеся

(п

1)!

номеров.

Продолжая эти рассуждения, получим общую фор­

мулу

для

выражения

номера

перестановки—в зависимос­

то номер перестановки в общем ряду п\ перестановок оп­

ределится формулой:

—

N(n)

= {h-\)

( я - 1 ) ! + ( / 2 - 1 ) ( я - 2 ) ! + -

•••-t-(Zf t

-l) (n-k)l+

••• + ( / „ - 2 - 1 ) 2 ! + ( Z n - i - l ) + 1 -

приведенной формулой.

Пусть я = ( 1 , 4, 2, 3, 5),

тогда /і = 1, так как

в ряду

1, 2, 3, 4, 5 этот объект занимает первое место; на

втором

шаге, вычеркнув 1, получим

последовательность 2, 3, 4, 5

чим

последовательность 3, 5 и соответственно определим

/ 4 = 1 . По

формуле определяем

Л^(я) = (1—1)4!+ (3—

— 1)3!+(1 — 1)2! + (1 —1)11 + 1 = 13.

Для

я = ( 4 ,

2, 1, 3),

Л »

= (4—1)3!+ (2—1)2! + ( 1 — 1) +

1=21.

Можно также предложить и другой способ определе­

ния

4. Легко проверить, ЧТО ДЛЯ

Я = (і'ь

І% . . .,

ih, • • ., Іп)

lh = ik—zh,

где 2ft — число элементов в

перестановке я,

гими словами,

определяется

как

число элементов мно­

жества

{ij

• j < k,

ij <

Іи).

Покажем теперь, как найти перестановку я по задан­

ному Л''(я) и числу элементов

перестановки п.

Применяя

к выражению

N (л)

метод последовательного

деления,

получим:

qn-3=

( / п - 2 - 1 ) 2 !

+<7п-

оп-г

= [In-i —

1) •

— l

Здесь qx—

остаток отделения

N(n)

на (п— 1)!,

a q%

(2^i^n—2)

—остаток от деления

qt-i

на

(п—і')!.

Будем считать, что U—\=h—1=

• • • = ln-2—1=0,

если

TV (я) — К

(п— 1)!, <7!<(п—2)!,..., <7„_3<j2!

соответст­

зт=(іі, «г,..., in)

следующим

образом. Принимаем

i\ — U

и вычеркиваем

число i"i из

последовательности

чисел

1,2,

...,п, затем

определяем

U

как число, стоящее на

І2-м

месте в последовательности

с вычеркнутым ЧИСЛОМ І],

тельности 1, ... , п и определяем

із как число, стоящее на

/3 -м месте в последовательности

с вычеркнутыми

І\ и

і2

и т. д. На последнем

шаге определяется і п как

единствен­

ное незачеркнутое число последовательности

1, 2,...,

п.

Приведем несколько примеров.

1. М ( я ) = 3 8 ; я = 5

+ i= 2,

/ 1 =

r

3 8 - 1

"

<7i = 37-- 24=13,

-

4!

І2 =

"

13

+ i=

3,

<?2 = 13 - 2 X 6 = 1 ,

-

3!

-

h = К - ]

+ i=

1,

<7з = 1 -

0-2 = 1;

U =

(А, І2, /з, Ц) =

Итак, имеем

(2, З, I , 2).

і\=1\ = 2, последовательность

1, 2, 3, 4, 5 после

вычер­

кивания двойки имеет вид 1, 3, 4, 5;

і2 = 4, так

как на третьем

месте в последовательности

1, 3, 4, 5 стоит 4. После вычеркивания

четверки

имеем

последовательность

1, 3, 5;

і 3 = 1 , так

как первым членом в последней

последова­

ром месте стоит 5;

i 5 = 3 ,

так как

после вычеркивания в последователь­

ности 3,

5 пятерки

остается число ЗІ

Итак, я = (2, 4, 1, 5,

3).

2. Ы(я)=38,

п = 6

Г 38-1

1

=

1,

<7i =

37,

2,

(72

13;

3,

<7з

1;

1,

? 4

1,

/5 = (74 + 1=2.

соответственно

я = ' ( 1 ,

3, 5, 2, 6, 4).

с т станками и

В задаче календарного планирования

рестановку

я = (яь Яг

я т о ) , где перестановка

Я і ( І ^ і ^ т )

указывает последовательность обработки

N(m) и таким образом

каждому

плану А

будет

постав­

лена в соответствие целочисленная точка

X из т-мерно-

го эвклидова пространства Я. Эти преобразования

схема­

тически запишутся в виде

А

я

X

A^D

Я<=П

І Є Н