Random combinatorial objects
type: Item
instance of: scholarly article
title: Random combinatorial objects
zbMATH Open document ID: 1210.05012
author: G. I. Ivchenko
author: Yu. I. Medvedev
published in: Doklady Mathematics
publication date: 2007-06-27T00:00:00Z
review text: The authors study combinatorial objects that are decomposable into separate components. Let \(\mathcal K_n\) be a set of decomposable objects with weight \(n\), and \(c_i(n)\) the number of components of an object \(K\in \mathcal K_n\) with weight \(i\), \(i=1,\dots, n\). The sequence \(c(n)=(c_1(n), \dots, c_n(n))\) is called the structure of \(K\). The number of objects from \(\mathcal K_n\) with structure \(c(n)\) is denoted \(N(n,c(n))\). Then a probability measure can be introduced for any \(K\in\mathcal K_n\) with structure \(c(n)=a=(a_1,\dots,a_n)\): \[ P_{\theta}(K)=I \left(\sum_{i=1}^n ia_i=n\right)\frac{\prod_{i=1}^n\theta_i^{a_i}}{H_n(\theta)}, \] where \(\theta=(\theta_1,\dots,\theta_n)\), \(\theta_i\geq 0\), \(I(\cdot)\) is the indicator function and \(H_n(\theta)\) is a normalizing factor, which is defined as \(H_n(\theta)=\sum_ {\left\{a: \sum ia_i=n\right\}}N(n,a)\prod_{i=1}^n\theta_i^{a_i}\). A number of examples are presented.
Mathematics Subject Classification ID: 05A17
Mathematics Subject Classification ID: 05A18
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 5168083
zbMATH Keywords: combinatorial objects
zbMATH Keywords: decomposability into separate components
zbMATH Keywords: probability measure
reviewed by: Olaf Ninnemann
MaRDI profile type: Publication
Recommended article: Generating random combinatorial objects
Recommended article: Q4263659
Recommended article: Random generation of trees and other combinatorial objects
Recommended article: Random generation of combinatorial structures from a uniform distribution
Recommended article: Q3742718
Recommended article: Q3070020
Recommended article: Random permutations and related topics
Recommended article: Random permutations of countable sets
Recommended article: Combinatorial theorems relative to a random set
description: scientific article; zbMATH DE number 5168083