کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428621 686845 2011 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Counting extensional acyclic digraphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Counting extensional acyclic digraphs
چکیده انگلیسی

Transitive sets with n elements were counted by Peddicord in 1962, by the use of Ackermannʼs numeric encoding of a (hereditarily finite) set. In this paper we give a combinatorial interpretation of this number by counting extensional acyclic digraphs. In a similar constructive manner, we also obtain the number of weakly extensional acyclic digraphs with a given number of labeled sinks and a given number of sources, or with a given number of vertices of maximum rank.


► Counting transitive sets is equivalent to counting extensional acyclic digraphs.
► We give a recurrence formula for labeled extensional acyclic digraphs.
► We count (weakly) extensional acyclic digraphs by sources.
► We also count (weakly) extensional acyclic digraphs by vertices of maximum rank.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 111, Issue 16, 30 August 2011, Pages 787–791
نویسندگان
, ,