Protected Cells in Compositions

被引：0

作者：

Archibald, Margaret ^{[1
]}

Blecher, Aubrey ^{[1
]}

Brennan, Charlotte ^{[1
]}

Knopfmacher, Arnold ^{[1
]}

机构：

[1] Univ Witwatersrand Wits, John Knopfmacher Ctr Applicable Anal & Number The, Sch Math, Private Bag 3, ZA-2050 Johannesburg, South Africa

来源：

MATHEMATICS IN COMPUTER SCIENCE | 2022年 / 16卷 / 01期

基金：

新加坡国家研究基金会;

关键词：

Compositions; Protected cells; Bargraphs; Generating functions;

D O I：

10.1007/s11786-021-00519-y

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Compositions (ordered partitions) of n are finite sequences of positive integers that sum to n. We represent a composition of n as a bargraph with area n such that the height of the i-th column of the bargraph equals the size of the i-th part of the composition. We consider the concept of protected cells and protected columns in the bargraph representation of the composition. An r-protected cell is a cell in which the shortest path to the outside has at least r + 1 steps (up, down, left or right). We obtain the average number of r-protected cells and protected columns. Finally we study the total protection number of a composition and compute the mean of this quantity over all compositions of n. We define the total protection number of a composition pi to be the sum of the protection numbers of each individual cell in that composition.

引用

页数：8

共 10 条

[1] The inner site-perimeter of compositions [J].

Blecher, Aubrey ;

Brennan, Charlotte ;

Knopfmacher, Arnold .

QUAESTIONES MATHEMATICAE, 2020, 43 (01) :55-66

[2] Elements protected by records in set partitions [J].

Cakic, Nenad ;

Mansour, Toufik ;

Smith, Rebecca .

JOURNAL OF DIFFERENCE EQUATIONS AND APPLICATIONS, 2018, 24 (12) :1880-1893

[3] Protected points in ordered trees [J].

Cheon, Gi-Sang ;

Shapiro, Louis W. .

APPLIED MATHEMATICS LETTERS, 2008, 21 (05) :516-520

[4] k-Protected Vertices in Unlabeled Rooted Plane Trees [J].

Copenhaver, Keith .

GRAPHS AND COMBINATORICS, 2017, 33 (02) :347-355

[5] Notes on protected nodes in digital search trees [J].

Du, Rosena R. X. ;

Prodinger, Helmut .

APPLIED MATHEMATICS LETTERS, 2012, 25 (06) :1025-1028

[6]

HEUBACH S., 2010, Combinatorics of compositions and words, Discrete Mathematics and its applications

[7] PROTECTION NUMBER IN PLANE TREES [J].

Heuberger, Clemens ;

Prodinger, Helmut .

APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS, 2017, 11 (02) :314-326

[8]

Mansour T, 2019, DISCRETE MATH LETT, V1, P26

[9]

Mansour T, 2019, AUSTRALAS J COMB, V74, P169

[10] Protected points in k-ary trees [J].

Mansour, Toufik .

APPLIED MATHEMATICS LETTERS, 2011, 24 (04) :478-480

← 1 →