IDEAS home Printed from https://ideas.repec.org/p/tiu/tiucen/b5401f7f-fa00-4bc2-9fe6-7af0b2956ad9.html
   My bibliography  Save this paper

Generalization of Binomial Coefficients to Numbers on the Nodes of Graphs

Author

Listed:
  • Khmelnitskaya, A.
  • van der Laan, G.

    (Tilburg University, Center For Economic Research)

  • Talman, Dolf

    (Tilburg University, Center For Economic Research)

Abstract

The triangular array of binomial coefficients, or Pascal's triangle, is formed by starting with an apex of 1. Every row of Pascal's triangle can be seen as a line-graph, to each node of which the corresponding binomial coefficient is assigned. We show that the binomial coefficient of a node is equal to the number of ways the line-graph can be constructed when starting with this node and adding subsequently neighboring nodes one by one. Using this interpretation we generalize the sequences of binomial coefficients on each row of Pascal's triangle to so-called Pascal graph numbers assigned to the nodes of an arbitrary (connected) graph. We show that on the class of connected cycle-free graphs the Pascal graph numbers have properties that are very similar to the properties of binomial co-efficients. We also show that for a given connected cycle-free graph the Pascal graph numbers, when normalized to sum up to one, are equal to the steady state probabilities of some Markov process on the nodes. Properties of the Pascal graph numbers for arbitrary connected graphs are also discussed. Because the Pascal graph number of a node in a connected graph is defined as the number of ways the graph can be constructed by a sequence of increasing connected subgraphs starting from this node, the Pascal graph numbers can be seen as a measure of centrality in the graph.
(This abstract was borrowed from another version of this item.)
(This abstract was borrowed from another version of this item.)
(This abstract was borrowed from another version of this item.)
(This abstract was borrowed from another version of this item.)
(This abstract was borrowed from another version of this item.)
(This abstract was borrowed from another version of this item.)
(This abstract was borrowed from another version of this item.)

Suggested Citation

  • Khmelnitskaya, A. & van der Laan, G. & Talman, Dolf, 2016. "Generalization of Binomial Coefficients to Numbers on the Nodes of Graphs," Discussion Paper 2016-007, Tilburg University, Center for Economic Research.
  • Handle: RePEc:tiu:tiucen:b5401f7f-fa00-4bc2-9fe6-7af0b2956ad9
    as

    Download full text from publisher

    File URL: https://pure.uvt.nl/ws/portalfiles/portal/10080270/2016_007.pdf
    Download Restriction: no
    ---><---

    Other versions of this item:

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Anna Khmelnitskaya & Gerard van der Laan & Dolf Talman, 2016. "Centrality Rewarding Shapley and Myerson Values for Undirected Graph Games," Tinbergen Institute Discussion Papers 16-070/II, Tinbergen Institute.
    2. Mágó, Mánuel, 2018. "Power values and framing in game theory," Other publications TiSEM e7822a6b-a2db-4ce9-bd08-b, Tilburg University, School of Economics and Management.

    More about this item

    Keywords

    binomal coefficient; Pascal's triangle; graph; Markov process; centrality measure;
    All these keywords.

    JEL classification:

    • C00 - Mathematical and Quantitative Methods - - General - - - General

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:tiu:tiucen:b5401f7f-fa00-4bc2-9fe6-7af0b2956ad9. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Richard Broekman (email available below). General contact details of provider: http://center.uvt.nl .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.