This paper is a compilation of results in combinatorics utilizing the probabilistic method. Below is a brief description of the results highlighted in each chapter. Chapter 1 provides basic definitions, lemmas, and theorems from graph theory, asymptotic analysis, and probability which will be used throughout the paper. Chapter 2 introduces the independent domination number. It is then shown that in the random graph model G(n,p) with probability tending to one, the independent domination number is one of two values. Also, the the number of independent dominating sets of given cardinality is analyzed statistically. Chapter 3 introduces the tree domination number. It is then shown that in the random graph model G(n,p) with probability tending to one, the tree domination number is one of two values. Additional related domination parameters are also discussed. Chapter 4 introduces a generalized rook polynomial first studied by J. Goldman et al. Central and local limit theorems are then proven for certain classes of the generalized rook polynomial. Special cases include known central and local limit theorems for the Stirling numbers of the first and second kind and additionally new limit theorems for the Lah numbers and certain classes of known generalized Stirling numbers. Chapter 5 introduces the Kneser Graph. The exact expected value and variance of the distance between [n] and a vertex chosen uniformly at random is given. An asymptotic formula for the expectation is found.

The topic of the diploma thesis is Concerning Chosen Translations of the Poem The Raven by E. A. Poe - an Attempt at a Comparison. The thesis deals with the comparison of Czech translations which have been written over the period of the last twenty years. The original text would be also dealt with, since there come up distinct shifts of meaning within the process of translation. However, the author will not omit different aesthetical qualities of the original and target language. An observation of schoolbooks for teaching literature at secondary and high schools will be added together with an attempt to determine the most frequently included translation which could therefore be considered as canonic. The output of the thesis should be an analysis evaluating whether including the translation in schoolbooks is appropriate and offering a constructive suggestion on an alternative one.

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.

Social intelligence is thought to have evolved as an adaptation to the complex situations group-living animals encounter in their daily lives. High levels of sociality provide individuals with opportunities to learn from one another. Social learning provides individuals with a relatively cheap and quick alternative to individual learning. This thesis investigated social learning in three corvid species: gregarious rooks (Corvus frugilegus) and jackdaws (Corvus monedula) and nongregarious, territorial Eurasian jays (Garrulus glandarius). In addition to that, the species' social structure was analysed and individual differences between members of each species were determined. Introducing the field of social learning research, I presented a new framework for investigating social learning, combining ecology, ethology and evolution. Experiments were conducted within that framework. I found that rooks and jackdaws develop social bonds and dominance hierarchies, whereas Eurasian jays do not. This is most likely related to their territoriality. In two experiments using two-action tasks, jackdaws learned socially. The underlying social learning mechanism was enhancement, which fits in with their feeding ecology. Rooks did not show social learning when presented with videos of conspecifics opening an apparatus. This might have been due to the difficulty of transferring information from videos or due to an ingrained 'affinity' to innovation and/or rapid trial-and-error learning overriding social learning processes. Individual differences along the bold/shy axis existed in all three species, but they were not stable across contexts. Thus, it seemed that the individuals perceived the two seemingly similar contexts that were designed to investigate neophobia and exploration (novel object in familiar environment; novel environment) as two different situations. The information may therefore have been processed by two distinct underlying mechanisms, which elicited different responses in each of the contexts. The implications of the findings of this thesis are discussed with regard to the new framework, integrating sociality, social learning and individual differences with the species' ecology.

Cette thèse se divise en deux grandes parties, la première traite la combinatoire associée à l’ordre normal des opérateurs non-commutatifs et la seconde aborde des distributions symétriques du nombre de croisements et du nombre d’emboîtements, respectivement k-croisements et k-emboîtements, dans des structures combinatoires (partitions, permutations, permutations colorées, …). La première partie étudie l’ordre normal des opérateurs en termes de placements de tours. Nous étudions la forme de l’ordre normal en connectant deux opérateurs non-commutatifs D et U, et des polynômes orthogonaux spéciaux, et établissons des bijonctions entre les coefficients de (D+U)n et le nombre de placements de tours sur un diagramme de Ferrers. Nous donnons également des preuves combinatoires à des conjectures quantiques posées par des physiciens. Dans la seconde partie, nous définissons des statistiques, comme emboîtements et k-emboîtements, sur l’ensemble des permutations du groupe de Coxeter de type B. Nous donnons également des extensions au type B des résultats sur les croisements et les emboîtements, respectivement k-croisements et k-emboîtements dans les permutations de type A, en termes de distributions symétriques. De plus, nous étudions le lien entre les opérateurs non-commutatifs et ces statistiques. D’autres extensions de la distribution de ces statistiques sur les ensembles de partitions colorées et de permutations colorées de types A et B sont ainsi établies / This thesis is divided into two parts, the first deals with the combinatorics associated to the normal ordering form of noncommutative operators and the second addresses the symmetric distributions of the crossing numbers and nesting numbers, respectively k-crossings and k-nestings, in combinatorial structures (partitions, permutations, colored permutations, …). The first part studies the normal order of operators in terms of rook placements. We study the normal ordering form connecting two noncommutative operators D and U, and some special orthogonal polynomials, and establish bijonctions between coefficients of (D+U)n and rook placements in Ferrers diagrams. We also give combinatorial proofs and alternatives to some quantum conjectures posed by physicists. In the second part, we define the notions of statistics, nestings and k-nestings, on the sets of permutations of the Coxeter group of type B. We also give extensions to type B of the results of the crossings and nestings, respectivelu k-crossings and K-nestings in the set of permutations of type A, in terms of symmetric distributions. Likewise, we study the link between non-commutative operators and these statistics. Other extensions of the distribution of these statistics on the sets of colored partitions and colored permutations of type A and B are established

This thesis deals with enumerative combinatorics applied to three different objects related to partition shapes, namely tableaux, restricted words, and Bruhat intervals. The main scientific contributions are the following. Paper I: Let the sign of a standard Young tableau be the sign of the permutation you get by reading it row by row from left to right, like a book. A conjecture by Richard Stanley says that the sum of the signs of all SYTs with n squares is 2^[n/2]. We prove a generalisation of this conjecture using the Robinson-Schensted correspondence and a new concept called chess tableaux. The proof is built on a remarkably simple relation between the sign of a permutation pi and the signs of its RS-corresponding tableaux P and Q, namely sgn(pi) = (−1)^v sgn(P)sgn(Q), where v is the number of disjoint vertical dominoes that fit in the partition shape of P and Q. The sign-imbalance of a partition shape is defined as the sum of the signs of all standard Young tableaux of that shape. As a further application of the sign-transferring formula above, we also prove a sharpening of another conjecture by Stanley concerning weighted sums of squares of sign-imbalances. Paper II: We generalise some of the results in paper I to skew tableaux. More precisely, we examine how the sign property is transferred by the skew Robinson-Schensted correspondence invented by Sagan and Stanley. The result is a surprisingly simple generalisation of the ordinary non-skew formula above. As an application, we find vanishing weighted sums of squares of sign-imbalances, thereby generalising a variant of Stanley’s second conjecture. Paper III: The following special case of a conjecture by Loehr and Warrington was proved by Ekhad, Vatter, and Zeilberger: There are 10^n zero-sum words of length 5n in the alphabet {+3,−2} such that no consecutive subword begins with +3, ends with −2, and sums to −2. We give a simple bijective proof of the conjecture in its original and more general setting where 3 and 2 are replaced by any relatively prime positive integers a and b, 10^n is replaced by ((a+b) choose a)^n, and 5n is replaced by (a+b)n. To do this we reformulate the problem in terms of cylindrical lattice walks which can be interpreted as the south-east border of certain partition shapes. Paper IV: We characterise the permutations pi such that the elements in the closed lower Bruhat interval [id,pi] of the symmetric group correspond to non-capturing rook configurations on a skew Ferrers board. These intervals turn out to be exactly those whose flag manifolds are defined by inclusions, as defined by Gasharov and Reiner. The characterisation connects Poincaré polynomials (rank-generating functions) of Bruhat intervals with q-rook polynomials, and we are able to compute the Poincaré polynomial of some particularly interesting intervals in the finite Weyl groups A_n and B_n. The expressions involve q-Stirling numbers of the second kind, and for the group A_n putting q = 1 yields the poly-Bernoulli numbers defined by Kaneko. / Ämnet för denna avhandling är enumerativ kombinatorik tillämpad på tre olika objekt med anknytning till partitionsformer, nämligen tablåer, begränsade ord och bruhatintervall. Dom viktigaste vetenskapliga bidragen är följande. Artikel I: Låt tecknet av en standardtablå vara tecknet hos permutationen man får om man läser tablån rad för rad från vänster till höger, som en bok. En förmodan av Richard Stanley säjer att teckensumman av alla standardtablåer med n rutor är 2^[n/2]. Vi visar en generalisering av denna förmodan med hjälp av Robinson-Schensted-korrespondensen och ett nytt begrepp som vi kallar schacktablåer. Beviset bygger på ett anmärkningsvärt enkelt samband mellan tecknet hos en permutation pi och tecknen hos dess RS-motsvarande tablåer P och Q, nämligen sgn(pi)=(-1)^v sgn(P)sgn(Q), där v är antalet disjunkta vertikala dominobrickor som får plats i partitionsformen hos P och Q. Teckenobalansen hos en partitionsform definieras som teckensumman av alla standardtablåer av den formen. Som en ytterligare tillämpning av formeln för teckenöverföring ovan bevisar vi också en starkare variant av en annan förmodan av Stanley som handlar om viktade summor av kvadrerade teckenobalanser. Artikel II: Vi generaliserar några av resultaten i artikel I till skeva tablåer. Närmare bestämt undersöker vi hur teckenegenskapen överförs av Sagan och Stanleys skeva Robinson-Schensted-korrespondens. Resultatet är en förvånansvärt enkel generalisering av den vanliga ickeskeva formeln ovan. Som en tillämpning visar vi att vissa viktade summor av kvadrerade teckenobalanser blir noll, vilket leder till en generalisering av en variant av Stanleys andra förmodan. Artikel III: Följande specialfall av en förmodan av Loehr och Warrington bevisades av Ekhad, Vatter och Zeilberger: Det finns 10^n ord med summan noll av längd 5n i alfabetet {+3,-2} sådana att inget sammanhängande delord börjar med +3, slutar med -2 och har summan -2. Vi ger ett enkelt bevis för denna förmodan i dess ursprungliga allmännare utförande där 3 och 2 byts ut mot vilka som helst relativt prima positiva heltal a och b, 10^n byts ut mot ((a+b) över a)^n och 5n mot (a+b)n. För att göra detta formulerar vi problemet i termer av cylindriska latticestigar som kan tolkas som den sydöstra gränslinjen för vissa partitionsformer. Artikel IV: Vi karakteriserar dom permutationer pi sådana att elementen i det slutna bruhatintervallet [id,pi] i symmetriska gruppen motsvarar ickeslående tornplaceringar på ett skevt ferrersbräde. Dessa intervall visar sej vara precis dom vars flaggmångfalder är definierade av inklusioner, ett begrepp introducerat av Gasharov och Reiner. Karakteriseringen skapar en länk mellan poincarépolynom (ranggenererande funktioner) för bruhatintervall och q-tornpolynom, och vi kan beräkna poincarépolynomet för några särskilt intressanta intervall i dom ändliga weylgrupperna A_n och B_n. Uttrycken innehåller q-stirlingtal av andra sorten, och sätter man q=1 för grupp A_n så får man Kanekos poly-bernoullital. / QC 20100818