Generalization of Binomial Coefficients to Numbers on the Nodes of Graphs

A. Khmelnitskaya, G. van der Laan, Dolf Talman

Research output: Working paperDiscussion paperOther research output

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 coefficients.
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.
LanguageEnglish
Place of PublicationTilburg
PublisherCentER, Center for Economic Research
Number of pages26
Volume2016-007
StatePublished - 15 Feb 2016

Publication series

NameCentER Discussion Paper
Volume2016-007

Fingerprint

Binomial coefficient
Pascal
Graph in graph theory
Vertex of a graph
Pascal's triangle
Connected graph
Line Graph
Generalization
Cycle
Triangular Array
Centrality
Apex
Arbitrary
Markov Process
Subgraph
Generalise

Keywords

  • binomal coefficient
  • Pascal's triangle
  • graph
  • Markov process
  • centrality measure

Cite this

Khmelnitskaya, A., van der Laan, G., & Talman, D. (2016). Generalization of Binomial Coefficients to Numbers on the Nodes of Graphs. (CentER Discussion Paper; Vol. 2016-007). Tilburg: CentER, Center for Economic Research.
Khmelnitskaya, A. ; van der Laan, G. ; Talman, Dolf. / Generalization of Binomial Coefficients to Numbers on the Nodes of Graphs. Tilburg : CentER, Center for Economic Research, 2016. (CentER Discussion Paper).
@techreport{b5401f7ffa004bc29fe67af0b2956ad9,
title = "Generalization of Binomial Coefficients to Numbers on the Nodes of Graphs",
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'striangle 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 coefficients. 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 = "binomal coefficient, Pascal's triangle, graph, Markov process, centrality measure",
author = "A. Khmelnitskaya and {van der Laan}, G. and Dolf Talman",
year = "2016",
month = "2",
day = "15",
language = "English",
volume = "2016-007",
series = "CentER Discussion Paper",
publisher = "CentER, Center for Economic Research",
type = "WorkingPaper",
institution = "CentER, Center for Economic Research",

}

Khmelnitskaya, A, van der Laan, G & Talman, D 2016 'Generalization of Binomial Coefficients to Numbers on the Nodes of Graphs' CentER Discussion Paper, vol. 2016-007, CentER, Center for Economic Research, Tilburg.

Generalization of Binomial Coefficients to Numbers on the Nodes of Graphs. / Khmelnitskaya, A.; van der Laan, G.; Talman, Dolf.

Tilburg : CentER, Center for Economic Research, 2016. (CentER Discussion Paper; Vol. 2016-007).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - Generalization of Binomial Coefficients to Numbers on the Nodes of Graphs

AU - Khmelnitskaya,A.

AU - van der Laan,G.

AU - Talman,Dolf

PY - 2016/2/15

Y1 - 2016/2/15

N2 - 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'striangle 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 coefficients. 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.

AB - 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'striangle 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 coefficients. 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.

KW - binomal coefficient

KW - Pascal's triangle

KW - graph

KW - Markov process

KW - centrality measure

M3 - Discussion paper

VL - 2016-007

T3 - CentER Discussion Paper

BT - Generalization of Binomial Coefficients to Numbers on the Nodes of Graphs

PB - CentER, Center for Economic Research

CY - Tilburg

ER -

Khmelnitskaya A, van der Laan G, Talman D. Generalization of Binomial Coefficients to Numbers on the Nodes of Graphs. Tilburg: CentER, Center for Economic Research. 2016 Feb 15, (CentER Discussion Paper).