Global ETD Search

1	Combinatorial methods for counting pattern occurrences in a Markovian text Yucong Zhang (9518483) 16 December 2020 (has links) In this dissertation, we provide combinatorial methods to obtain the probabilistic mul-tivariate generating function that counts the occurrences of patterns in a text generated by a Markovian source. The generating function can then be expanded into the Taylor series in which the power of a term gives the size of a text and the coeÿcient provides the proba-bilities of all possible pattern occurrences with the text size. The analysis is on the basis of the inclusion-exclusion principle to pattern counting (Goulden and Jackson, 1979 and 1983) and its application that Bassino et al. (2012) used for obtaining the generating function in the context of the Bernoulli text source. We followed the notations and concepts created by Bassino et al. in the discussion of distinguished patterns and non-reduced pattern sets, with modifications to the Markovian dependence. Our result is derived in the form of a linear matrix equation in which the number of linear equations depends on the size of the alphabet. In addition, we compute the moments of pattern occurrences and discuss the impact of a Markovian text to the moments comparing to the Bernoulli case. The methodology that we use involves the inclusion-exclusion principle, stochastic recurrences, and combinatorics on words including probabilistic multivariate generating functions and moment generating functions.<br> Statistics Combinatorics on Words Pattern matching Stochastic recurrence inclusion-exclusion principle
2	Inclusion-exclusion and pigeonhole principles Hung, Wei-cheng 25 June 2009 (has links) In this paper, we will review two fundamental counting methods: inclusionexclusion and pigeonhole principles. The inclusion-exclusion principle considers the elements of the sets satisfied some conditions, and avoids repeat counting by disjoint sets. We also use the inclusion-exclusion principle to solve the problems of Euler phi function and the number of onto functions in number theory, and derangement and the number of nonnegative integer solutions of equations in combinatorics. We derive the closed-form formula to those problems. For the forbidden positions problems, we use the rook polynomials to simplify the counting process. We also show the form of the inclusion-exclusion principle in probability, and use it to solve some probability problems. The pigeonhole principle is an easy concept. We can establish some sets and use the pigeonhole principle to discuss the extreme value about the number of elements. Choose the pigeons and pigeonholes, properly, and solve problems by the concept of the pigeonhole principle. We also introduce the Ramsey theorem which is an important application of the pigeonhole principle. This theorem provides a method to solve problems by complete graph. Finally, we give some contest problems about the inclusion-exclusion and pigeonhole principles to show how those principles are used. pigeonhole principle Ramsey theorem derangement inclusion-exclusion principle consecutive permutation Euler¡¦s phi function complete graph combinations with repetition onto function rook polynomial nonnegative integer solutions
3	Kombinatorické principy ve školské matematice / Combinatorial principles in school mathematics BŘEZINOVÁ, Jiřina January 2010 (has links) The thesis includes delatiled explanation of combinatorial principles used in school mathematics. The single principles are explained in details and practicised. The tasks at the end of the chapter serve readers for testing acquired knoledge.
4	Introduction to Probability Theory Chen, Yong-Yuan 25 May 2010 (has links) In this paper, we first present the basic principles of set theory and combinatorial analysis which are the most useful tools in computing probabilities. Then, we show some important properties derived from axioms of probability. Conditional probabilities come into play not only when some partial information is available, but also as a tool to compute probabilities more easily, even when partial information is unavailable. Then, the concept of random variable and its some related properties are introduced. For univariate random variables, we introduce the basic properties of some common discrete and continuous distributions. The important properties of jointly distributed random variables are also considered. Some inequalities, the law of large numbers and the central limit theorem are discussed. Finally, we introduce additional topics the Poisson process. Chebyshev¡¦s inequality central limit theorem Poisson process Markov¡¦s inequality multivariate normal distribution multinomial distribution F distribution t distribution chi-square distribution lognormal distribution Beta distribution Cauchy distribution Weibull distribution gamma distribution exponential distribution normal distribution discrete uniform distribution uniform distribution hypergeometric distribution geometric distribution negative binomial distribution Poisson distribution binomial distribution Bernoulli distribution Bayes theorem theorem of total probability axioms of probability multinomial theorem inclusion-exclusion principle set

1

Page generated in 0.1002 seconds