М1881- (10)

М1885

Автомобильная стоянка представляет собой ряд из n мест, занумерованных слева направо числами от 1 до n, а въезд на стоянку находится справа. У въезда скопились n машин, и теперь они по очереди заезжают на стоянку. Каждый водитель сначала подъезжает к своему любимому месту. Если оно свободно, ставит туда машину, а если занято, то едет вперёд до ближайшего свободного места (назад поворачивать нельзя). Обозначим а_i, где 1 £ i £ n, номер любимого места водителя i-ой в очереди машины. Будем говорить, что последовательность a₁, ..., a_n бесконфликтна, если удаётся поставить машины на стоянку, соблюдая указанные выше правила. Например, при n = 2 последовательности (1, 2), (2, 1) и (2, 2) бесконфликтны, а последовательность (1, 1) конфликтна.

а) Докажите, что последовательность натуральных чисел a₁, ..., a_n бесконфликтна тогда и только тогда, когда ни один её член не превосходит n и когда для любого натурального k, где k < n, количество членов последовательности, не превосходящих k, не превосходит k. Найдите количество

б*) бесконфликтных последовательностей длины n;

в*) бесконфликтных неубывающих последовательностей длины n.