Generalization of binomial coefficients to numbers on the nodes of graphs

Anna Borisovna Khmelnitskaya, Gerard van der Laan, Dolf Talman

Research output: Book/ReportReport

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.
LanguageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages25
StatePublished - Feb 2016

Publication series

NameMemorandum
PublisherUniversity of Twente, Department of Applied Mathematics
No.2054
ISSN (Print)1874-4850
ISSN (Electronic)1874-4850

Keywords

  • Markov process
  • Pascal's triangle
  • EWI-26853
  • C71
  • Graph
  • IR-99670
  • centrality measure
  • METIS-316840
  • binomial coefficient

Cite this

Khmelnitskaya, A. B., van der Laan, G., & Talman, D. (2016). Generalization of binomial coefficients to numbers on the nodes of graphs. (Memorandum; No. 2054). Enschede: University of Twente, Department of Applied Mathematics.
Khmelnitskaya, Anna Borisovna ; van der Laan, Gerard ; Talman, Dolf. / Generalization of binomial coefficients to numbers on the nodes of graphs. Enschede : University of Twente, Department of Applied Mathematics, 2016. 25 p. (Memorandum; 2054).
@book{eb6dc579d78b4a1fb6e486d4c09d9f05,
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'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.",
keywords = "Markov process, Pascal's triangle, EWI-26853, C71, Graph, IR-99670, centrality measure, METIS-316840, binomial coefficient",
author = "Khmelnitskaya, {Anna Borisovna} and {van der Laan}, Gerard and Dolf Talman",
note = "eemcs-eprint-26853",
year = "2016",
month = "2",
language = "Undefined",
series = "Memorandum",
publisher = "University of Twente, Department of Applied Mathematics",
number = "2054",

}

Khmelnitskaya, AB, van der Laan, G & Talman, D 2016, Generalization of binomial coefficients to numbers on the nodes of graphs. Memorandum, no. 2054, University of Twente, Department of Applied Mathematics, Enschede.

Generalization of binomial coefficients to numbers on the nodes of graphs. / Khmelnitskaya, Anna Borisovna; van der Laan, Gerard; Talman, Dolf.

Enschede : University of Twente, Department of Applied Mathematics, 2016. 25 p. (Memorandum; No. 2054).

Research output: Book/ReportReport

TY - BOOK

T1 - Generalization of binomial coefficients to numbers on the nodes of graphs

AU - Khmelnitskaya,Anna Borisovna

AU - van der Laan,Gerard

AU - Talman,Dolf

N1 - eemcs-eprint-26853

PY - 2016/2

Y1 - 2016/2

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'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.

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'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.

KW - Markov process

KW - Pascal's triangle

KW - EWI-26853

KW - C71

KW - Graph

KW - IR-99670

KW - centrality measure

KW - METIS-316840

KW - binomial coefficient

M3 - Report

T3 - Memorandum

BT - Generalization of binomial coefficients to numbers on the nodes of graphs

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Khmelnitskaya AB, van der Laan G, Talman D. Generalization of binomial coefficients to numbers on the nodes of graphs. Enschede: University of Twente, Department of Applied Mathematics, 2016. 25 p. (Memorandum; 2054).