Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Protected Cells in Compositions

  • Published:
Mathematics in Computer Science Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  1. Blecher, A., Brennan, C., Knopfmacher, A.: The inner site-perimeter of compositions. Quaest Math. https://doi.org/10.2989/16073606.2018.1536088 (2018)

  2. Cakić, N., Mansour, T., Smith, R.: Elements protected by records in set partitions. J. Differ. Equ. Appl. 24(12), 1880–1893 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  3. Cheon, G.S., Shapiro, L.W.: Protected points in ordered trees. Appl. Math. Lett. 21, 516–520 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  4. Copenhaver, K.: \(k\)-protected vertices in unlabeled rooted plane trees. Graph Combin. 33(2), 347–355 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  5. Du, R., Prodinger, H.: Notes on protected nodes in digital search trees. Appl. Math. Lett. 25(6), 1025–1028 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  6. Heubach, S., Mansour, T.: Combinatorics of Compositions and Words, Discrete Mathematics and its Applications. CRC Press, Cambridge (2010)

    MATH  Google Scholar 

  7. Heuberger, C., Prodinger, H.: Protection number in plane trees. Appl. Anal. Discrete Math. 11(2), 314–326 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  8. Mansour, T.: Protected points in \(k\)-ary trees. Appl. Math. Lett. 24, 478–480 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  9. Mansour, T.: Border and tangent cells in bargraphs. Discrete Math. Lett. 1, 26–29 (2019)

    MathSciNet  MATH  Google Scholar 

  10. Mansour, T., Schork, M., Yaqubi, D.: Protected cells in bargraphs. Austral. J. Combin. 74(1), 169–178 (2019)

    MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of the Witwatersrand (Wits), Private Bag 3, Johannesburg, 2050, South Africa

    Margaret Archibald, Aubrey Blecher, Charlotte Brennan & Arnold Knopfmacher

Authors
  1. Margaret Archibald
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Aubrey Blecher
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Charlotte Brennan
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Arnold Knopfmacher
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Charlotte Brennan.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This material is based upon work supported by the National Research Foundation under Grant Numbers 89147, 86329, 81021 respectively.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Archibald, M., Blecher, A., Brennan, C. et al. Protected Cells in Compositions. Math.Comput.Sci. 16, 1 (2022). https://doi.org/10.1007/s11786-021-00519-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11786-021-00519-y

Keywords

Mathematics Subject Classification

Search

Navigation