Generalization of Binomial Coefficients to Numbers on the Nodes of Graphs

Anna Khmelnitskaya, Gerard van der Laan and Adolphus Talman
Additional contact information
Anna Khmelnitskaya: Saint-Petersburg State University, Russia

No 16-011/II, Tinbergen Institute Discussion Papers from Tinbergen Institute

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.

Keywords: binomial coefficient; Pascal's triangle; graph; Markov process; centrality measure (search for similar items in EconPapers)
JEL-codes: C00 (search for similar items in EconPapers)
Date: 2016-02-16
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://papers.tinbergen.nl/16011.pdf (application/pdf)

Related works:
Working Paper: Generalization of Binomial Coefficients to Numbers on the Nodes of Graphs (2016)
Working Paper: Generalization of Binomial Coefficients to Numbers on the Nodes of Graphs (2016)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:tin:wpaper:20160011

Access Statistics for this paper

More papers in Tinbergen Institute Discussion Papers from Tinbergen Institute Contact information at EDIRC.
Bibliographic data for series maintained by Tinbergen Office +31 (0)10-4088900 ().