Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Доведення. Застосуємо метод математичної індукції по кількості символів n



Застосуємо метод математичної індукції по кількості символів n.

При це очевидно: 1,2;

2,1.

Зробимо індуктивне припущення: вважатимемо правильним дане твердження при . Доведемо справедливість твердження при . Запишемо всі перестановки, що починаються з 1.

1, 2, 3,..., ,

1,...

Розглянувши останні символів бачимо, що для цих перестановок діє індуктивне припущення. Тоді ці перестановки можна записати потрібним списком. Аналогічні міркування застосуємо для тих перестановок, що починаються з 2, 3,..., .

На стикуванні отриманих груп перестановок першу перестановку наступної групи отримаємо з останньої за рахунок транспозиції символів, що є першими у цих групах.





Дата публикования: 2014-11-18; Прочитано: 410 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.007 с)...