Рассмотрим функцию $%s(n)$% из этого вопроса math.hashcode.ru/questions/185442/

Как доказать, что она сюръективна?

И есть ли какой-то формальный способ её определения (на картинке дано определение для первых нескольких чисел, а дальше "по аналогии")

задан 14 Окт '19 3:26

По картинкам виден способ построения. Для каждого n рассматриваем все 2^n слов в 2-буквенном алфавите -- например, {a,b}. Упорядочиваем их словарно. Потом выписываем друг за другом списки таких слов при n>=0. Получается eps (пустое), a, b, aa, ab, ba, bb, aaa, ... . Нумеруем элементы списка числами 0, 1, 2, ... . Это биекция по построению. Значит, она сюръективна -- никакого нетривиального факта за этим нет.

Здесь a:=#, b:=1.

(14 Окт '19 3:38) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×700

задан
14 Окт '19 3:26

показан
736 раз

обновлен
14 Окт '19 3:38

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru