Подмножества натурального ряда

Профессор Снэйп · 18/12/07 8774 Новосибирск

Считаем, что $0$ - натуральное число.

Пусть $A \subseteq \mathbb{N}$ . Для каждого $n \in \mathbb{N}$ пусть $A_n = \{ x \in \mathbb{N}: n + x \in A \}$ . Скажем, что $A$ является $k$ -множеством, если семейство $\{ A_n : n \in \mathbb{N} \}$ подмножеств натурального ряда состоит ровно из $k$ элементов.

Примеры: множество чётных чисел и множество $\{ 0 \}$ являются $2$ -множествами, множество чисел, кратных трём, есть $3$ -множество, пустое множество и всё $\mathbb{N}$ есть $1$ -множества.

1) Доказать, что для каждого $k$ количество $k$ -множеств конечно.
2) Для каждого $k$ найти количество $k$ -множеств.

arseniiv · 27/04/09 28128

Каждому $A$ поставим для моего удобства в соответствие двоичную последовательность. $A$ — $k$ -множество, если у этой последовательности $k$ различных сдвигов к началу [влево в используемой форме записи].

(0) Видно, что существуют не- $k$ -множества, получаемые, напр., приписыванием нулей в начало к последовательности $101001000100001\ldots$ , но это тут ни при чём.

(1) Подумаем… Последовательность с «периодом» имеет катость не меньше его длины. Если оно начинается сразу с периода, как чётные, — это (длина-периода)-множество. Иначе добавляется количество символов, предшествующих ему. Непериодическая последовательность не соответствует никакому $k$ -множеству. Остаётся доказать, что, кроме этих множеств, других нет. Вроде бы, это так. Тогда каждому $k$ -множеству соответствует последовательность с периодом, притом либо периодом длины $k$ , начинающемся с начала, либо периодом длины $k-1$ , предварённым одним символом, …, либо периолом длины 1, перед которым $k-1$ символов.
Количество последовательностей формы $(k, 0)$ [ $k$ в периоде и 0 перед] нестрого ограничено сверху $2^k$ , формы $(k-1, 1)$ — $2^{k-1}\cdot2 = 2^k$ , …, формы $(1, k-1)$ — снова $2^k$ . Итого, кол-во последовательностей, соответствующих $k$ -множествам, не больше $2^k k$ , которое для каждого $k\in\mathbb N$ конечно. Поправьте оплошности, пожалуйста. (И как попроще доказать опущеное.)

(2) Из предыдущего ясно, что это $a_k \leqslant 2^k k$ . Для 1 даже равно (указанные вами единственные примеры $000\ldots$ и $111\ldots$ ), для 2 уже многовато, т. к. повторно посчитались и множества с катостью-делителем двух (т. е. 1). Это, наверно, даже намёк на результат, но пойду спать (ещё вернусь). Спасибо за задачу!

chessar · 03/12/08 351 Букачача

Профессор Снэйп в сообщении #618184 писал(а):

2) Для каждого $k$ найти количество $k$ -множеств.

Может быть искомое
$N(k)=\begin{cases}2,&k=1\\k+2^{k-2},&k\geqslant2\end{cases}$ Где $2^{k-2}$ - число конечных $k$ -множеств - это все конечные подмножества $\mathbb{N}\cup\{0\}$ , у которых максимальный элемент равен $k-2$ ; $k$ - число бесконечных $k$ -множеств, каждое, из которых является классом вычетов по модулю $k$ .

Профессор Снэйп · 18/12/07 8774 Новосибирск

arseniiv в сообщении #618487 писал(а):

Итого, кол-во последовательностей, соответствующих $k$ -множествам, не больше $2^k k$ ...

В рассуждения пока не вчитывался, но с оценкой согласен. У меня она точно такая же. Причём полученная совершенно другим путём.

-- Пт сен 14, 2012 07:30:47 --

chessar в сообщении #618507 писал(а):

Может быть искомое...

Не знаю пока.

У меня ответ получен в виде $\sum_{i=1}^k f(i,k)$ , где $f$ - некоторое арифметическое выражение. При малых $k$ моя сумма не совпадает с Вашим ответом, но я выводил свой в уме, пока ехал в маршрутке, и не уверен, что в выражение $f$ не вкралась ошибка. Сейчас мне на работу через 20 минут бежать, а к вечеру вернусь и в спокойной обстановке всё перепроверю.

-- Пт сен 14, 2012 07:34:00 --

arseniiv в сообщении #618487 писал(а):

Последовательность с «периодом» имеет катость не меньше его длины.

Не меньше длины минимального периода :-)

-- Пт сен 14, 2012 07:40:43 --

arseniiv в сообщении #618487 писал(а):

Видно, что существуют не $k$ -множества...

$k$ -множеств счётное число, всех подмножеств $\mathbb{N}$ континуум

arseniiv · 27/04/09 28128

Профессор Снэйп в сообщении #618532 писал(а):

Не меньше длины минимального периода :-)

Да, про минимальные я вспомнил уже ко второму пункту, да и оценку это не меняет. :roll:

Попробую через несколько часов додумать.

Профессор Снэйп · 18/12/07 8774 Новосибирск

У меня с моей суммой, кажется, облом вышел. То есть в правильном ответе опять-таки сумма, но более сложная, двойная, по всем делителям числа, которое меняется в первой сумме. И там функция Мёбиуса ещё...

А вот, может, кто-нибудь знает, сколькими способами можно непериодически рассадить на $n$ стоящих в ряд стульев мужчин и женщин. "Непериодически" означает, что данная рассадка непериодична ни с каким периодом $m$ , являющимся делителем $n$ .

Вот через это число способов рассадки ответ легко выражается.

arseniiv · 27/04/09 28128

То есть, не является сцеплением нескольких одинаковых рассадок?

ИСН · 18/05/06 13438 с Территории

Так это она и выходит: хорошие способы - это все вообще способы (простое выражение) минус те, которые периодичны с меньшим периодом. То есть минус $n/2$ -периодические (такое же простое выражение, только от $n/2$ ), минус оно же от $n/3$ и... Ох чёрт, но это мы дважды вычеркнули период $n/6$ - надо добавить его обратно. Э, так это же и есть функция Мёбиуса!

Профессор Снэйп · 18/12/07 8774 Новосибирск

arseniiv в сообщении #618690 писал(а):

То есть, не является сцеплением нескольких одинаковых рассадок?

Если я правильно понял Ваши слова про "сцепление одинаковых рассадок", то да.

-- Пт сен 14, 2012 20:23:12 --

ИСН в сообщении #618691 писал(а):

Так это она и выходит... Э, так это же и есть функция Мёбиуса!

Вот и я про то же!

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

Вот если бы maxal своё веское слово молвил...

(Некий спойлер)

Я рассуждал так. Множество является $k$ -множеством, если язык односимвольного алфавита, длины слов которого есть, в точности, элементы нашего множества, распознаётся минимальным детерминированным конечным автоматом с $k$ состояниями. ДКА в односимвольном алфавите устроены просто: прямое начало и хвостик-цикл. И для минимальности вот в этом самом циклическом хвостике должна присутствовать "рассадка без сцеплений". Плюс последнее состояние "прямого начала" должно отличаться от последнего состояния "циклического хвостика". Всё хорошо, осталось найти количество способов "рассадки без сцеплений"...

Отсюда же полученная оценка сверху: существует ровно $k \cdot 2^k$ детерминированных конечных автоматов односимвольного алфавита с $k$ состояниями.

Руст · 09/02/06 4401 Москва

Снимаю свой личный бан к постам профессора Снейп и поучаствую в приглянувшихся. Вообще то задача уже почти решена ИСН ом и arseniv ом.

Сопоставим подмножествам А натурального ряда действительное число из интервала [0,1]-х(А) по правилу $x(A)=0,a_1a_2....$ , где $a_i=1$ если $i\in A$ , иначе 0 (число соответствующее характеристической функцией подмножества). Тогда соответствие взаимно однозначное и $x(A_n)=\{2^nx(A)\}$ . Поэтому $k$ множествами являются только те, для которых $x(A)$ - рациональное с длиной периода не больше k. Число соответствующее периоду l представляется в виде дроби $\frac{m}{2^l-1}$ . Надо исключить повторы. Число определяется своим предпериодом длины $l=0,1,...,k-1$ и длиной периода $k-l\ge 1.$ Количество чистых периодов длины n равно $f(n)=\sum_{d|n}\mu (d)2^{n/d}$ , поэтому требуемое количество вычисляется по формуле:
$F(k)=f(k)+\sum_{l=1}^{k-1}2^{l-1}f(k-l).$
В частности $$f(1)=2,f(2)=2,f(3)=6,f(4)=12,f(5)=30,...,F(1)=2,F(2)=4,F(3)=12,F(4)=30,...$

Оценка. Запишем $f(n)=2^n-g(n)$ . При $n>1$ $2\le g(n)\le 2^{n/2 +1}$ , соответственно $F(k)=f(k)+f(k-1)+2*f(k-2)+...+2^{k-2}*2=2^k+2^{k-1}*(k-1)-g(k)-g(k-1)-2*g(k-2)-...-2^{k-3}g(2)=(k+1)2^{k-1}-g(k-1)-2*g(k-2)-...-2^{k-3}g(2)$ .
Отсюда получается $F(k)\le k*2^{k-1},k>1$ и $k*2^{k-1}-F(k)=(g(k)-2)+(g(k-1)-2)+....+2^{k-5)g(4)$ .
Главный член остатка $2^{k-5}g(4)=2^{k-4}$ появляется только при $k\ge 4$ и вообще сумма остатков не превосходит $2^{k-1}$ .