2014 dxdy logo

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

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




 
 Число циклических двоичных последовательностей длины n
Сообщение10.01.2015, 14:57 
Подскажите, пожалуйста, где найти (как получить) формулу для числа циклических двоичных последовательностей длины $ n. $
Пусть $ G^n $ – множество дфоичных последовательностей длины $ n $, в котором последовательности, отличающиеся лишь циклическим сдвигом, считаются одинаковыми.
Чему равно $ g(n)=|G^n| $? Или более детально, чему равно $ g(w,n)=|G^n(w)|,$ где $ w $ – число единиц в последовательности? (Очевидно, $ g (n-i,n)= g (i,n)=1 $).
Примеры: $ g (0,n) =1 $, $ g(1,n) =1,$ $ g(2,n)=[n/2],$ для простых $   n: g(n)=(2^n-2)/n+2. $

 
 
 
 Re: Число циклических двоичных последовательностей длины n
Сообщение10.01.2015, 15:24 
Iam в сообщении #959487 писал(а):
для простых $   n: g(n)=(2^n-2)/n+2. $
Это не целое число. Не смущает? Ересь.
Лемма Бёрнсайда и теорема Редфилда — Пойа.

 
 
 
 Re: Число циклических двоичных последовательностей длины n
Сообщение10.01.2015, 15:43 
Nemiroff в сообщении #959496 писал(а):
Это не целое число.
Вполне себе целое.

 
 
 
 Re: Число циклических двоичных последовательностей длины n
Сообщение10.01.2015, 15:44 
Nemiroff в сообщении #959496 писал(а):
Iam в сообщении #959487 писал(а):
для простых $   n: g(n)=(2^n-2)/n+2. $
Это не целое число. Не смущает?
Целое. Либо укажите простое $n$ такое, что указанное выражение нецелое.

З.Ы. Не успел.

 
 
 
 Re: Число циклических двоичных последовательностей длины n
Сообщение10.01.2015, 15:52 
А, да, целое. Ну ладно. :mrgreen: Это даже, кажется, правильный ответ.

Где-то ещё в праздниках… мда…

 
 
 
 Re: Число циклических двоичных последовательностей длины n
Сообщение10.01.2015, 16:51 
Спасибо, за ориентацию (на теорему Редфилда—Пойа) и внимание. Разобрался.

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group