2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Неожиданное количество последовательностей
Сообщение21.11.2018, 09:10 
Заслуженный участник


28/04/09
1933
Найти количество последовательностей из $n$ чисел $\alpha_i\in\{0^{-},0^{+},-1,+1\}$ (где $0^{-}=0^{+}=0$), удовлетворяющих условиям $$\begin{cases}\sum\limits_{i=1}^n\alpha_i=0\\ \sum\limits_{i=1}^k\alpha_i\ne 0,\ \forall k\colon 1\leqslant k< n\end{cases}$$...и объяснить его неожиданность.

 Профиль  
                  
 
 Re: Неожиданное количество последовательностей
Сообщение21.11.2018, 14:38 
Заслуженный участник


31/12/05
1424
Закодируем каждый член последовательности двумя битами:

\begin{aligned}+1 \to ++ \\ -1 \to -- \\ 0^+ \to +- \\ 0^- \to -+\end{aligned}

Получится биекция с хорошо известной задачей, имеющей простой и красивый результат.

 Профиль  
                  
 
 Re: Неожиданное количество последовательностей
Сообщение21.11.2018, 14:54 
Заслуженный участник


20/08/14
11071
Россия, Москва
Либо я чего-то не понял, либо подходят два класса: $(+1, 0^\pm, \ldots, 0^\pm, -1)$ и $(-1, 0^\pm, \ldots, 0^\pm, +1)$ - количество нулей в середине $n-2$, нули в каждой позиции можно ставить любой из двух, соответственно общее количество легко считается по количеству комбинаций нулей. Зачем здесь битовое кодирование не понял.

 Профиль  
                  
 
 Re: Неожиданное количество последовательностей
Сообщение21.11.2018, 14:58 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Dmitriy40 в сообщении #1355640 писал(а):
$(+1, 0^\pm, \ldots, 0^\pm, -1)$ и $(-1, 0^\pm, \ldots, 0^\pm, +1)$ - количество нулей в середине $n-2$,
Ещё $(+1, +1, 0^\pm, \ldots, 0^\pm, -1, -1)$ - количество нулей в середине $n-4$ и т.п.

 Профиль  
                  
 
 Re: Неожиданное количество последовательностей
Сообщение21.11.2018, 15:07 


30/03/08
196
St.Peterburg
$2K_{n-1}$ ( $ K_n-$ число Каталана)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group