Том 18, номер 1, 2011 г., Стр. 15-19

УДК 519.2
Валюженич А. А.
Некоторые свойства основательных последовательностей

Аннотация:
Задача нахождения числа основательных последовательностей и существования биекции между этими обьектами и множествами, соответствующими последовательности A103580, поставлена С. В. Китаевым. Основательные последовательности определяют класс графов, для которых им перечислены независимые множества. В статье найдена требуемая биекция и показано, что число основательных последовательностей растёт как $\Theta(2^{n/2})$.
Библиогр. 5.

Ключевые слова: основательная последовательность, множество, свободное от сумм.

Валюженич Александр Андреевич ¹
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: graphkiper@mail.ru

Статья поступила 1 апреля 2010 г.
Исправленный вариант — 8 сентября 2010 г.

Литература

[1] Сапоженко А. А. Гипотеза Камерона — Эрдеша //Докл. РАН. — 2003. — Т. 393, № 6. — С. 749–752.

[2] Cameron P., Erdos P. On the number of sets of integers with various properties // Number theory (Banff, AB, 1988). — Berlin: de Gruyter, 1990. — P. 61–79.

[3] Green B. J. The Cameron — Erdos conjecture // Bull. London. Math. Soc. — 2004. — V. 36, N 6. — P. 769–778.

[4] Kitaev S. Counting independent sets on path-schemes // J. Integer Seq. — 2006. — V. 9, N 8. (Article 06.2.2.)

[5] Sloane N. J. The on-line encyclopedia of integer sequences // http://www.research.att.com/njas/sequences/.