The distributions of the entries of Young tableaux

where (T) is the shape of tableau T and jTj is the number of cells in T Thus we can speak of \the probability that a Young tableau has a subtableau appearing in C," without reference to the size, n, of the tableau This phrase will mean the limit in (2)

The Simplex Method: Step by Step with Tableaus

Tableau IV BASIS x 1 x 2 x 3 x 4 x 5 RHS x 1 1 6 0 4 -1 36 x 3 0 -1 1 -1 0 5 6 ( z) 0 9 0 11 0 5 294 Thus, the optimal value of the MINIMIZATION formulation is z= 294 This means that the opti-

Limites et comportement asymptotique Fiche(1)

c Dresser le tableau de variations de f sur I 3 f est de la forme ( ) a Calculer f ’(x) en fonction de a et de c b Exprimer que A et B sont des points de C et qu’en S la tangente est horizontale c Ecrire un système d’inconnues a, b et c puis le résoudre pour trouver l’expression de f(x) 4 On admet que ( ) a

Limits and derivatives formulas - Free math calculators

Limits Derivatives Math Formulas Higher-order Created Date: 1/31/2010 3:27:33 AM

LIMIT SHAPES OF BUMPING ROUTES IN THE ROBINSON-SCHENSTED

being the insertion tableau corresponding to the permutation; the de nition of the second tableau Q n, known as the recording tableau, will not be necessary for our purposes More de-tails on Young tableaux, the Robinson-Schensted correspondence and their properties can be found in several well-known sources such as [Ful97, Knu98, Sta99]

TABLEAU CHEAT SHEET - Montana

TABLEAU CHEAT SHEET Relevant videos are linked throughout the document You must be signed in to your Tableau account in order to view the videos Workbook Components Sheet: A sheet is a singular chart or map in Tableau A sheet is represented in Tableau with this symbol: Dashboard

CH 1 – Analyse : 4ème Sciences Continuité et limites

3 Continuité et limites 4ème Sciences 09 – 10 www espacemaths com II Continuité et limite d’une fonction composée Définition Soit f une fonction définie sur un ensemble I et g une fonction définie sur ensemble J tel que f(IJ) Ì

Fonctions Logarithmes Exercices corrigés

a Rappeler la limite de la fonction h en et déterminer la limite de la fonction h en 0 b Calculer hx'( ), où h ’ désigne la fonction dérivée de h; retrouver les variations de h Déterminer les valeurs exactes de et hx() 0 c Déterminer l’intersection de la courbe (C) avec l’axe des abscisses 3 Soit O un

Fiche(1) Fonction exponentielle - LeWebPédagogique

Soit f la fonction définie sur ℝ par : – dont le tableau de variation est donné ci-contre 1 Justifier les renseignements consignés dans le tableau en précisant la valeur de a 2 Résoudre algébriquement l’inéquation f(x) 0 Exercice 2 Partie A-On considère la fonction f définie sur ℝ par : f(x) = x + ex

[PDF] limite polynome en 0

[PDF] limite polynome terme plus haut degré

[PDF] limite racine carré en 0

[PDF] limite racine carré forme indéterminée

[PDF] limite sinus en l'infini

[PDF] limite somme suite géométrique

[PDF] limite suite

[PDF] limite suite arithmético géométrique

[PDF] limite suite définie par récurrence

[PDF] limite suite géométrique

[PDF] limite variation

[PDF] limite, fonction exponentielle et démonstration

[PDF] Limiter l'alcoolisme chez les jeunes

[PDF] Limiter l'atteinte à la biodiversité planétaire

[PDF] limiter le droits de greve

The distributions of the entries of Young tableaux

Brendan D. McKay

1 , Jennifer Morse 2 , and Herbert S. Wilf 3

Abstract

LetTbe a standard Young tableau of shape`k. We show that the probability that a randomly chosen Young tableau ofncells containsTas a subtableau is, in the limitn!1, equal tof =k!, wheref is the number of all tableaux of shape. In other words,the probability that a large tableau containsTis equal to the number of tableaux whose shape is that ofT, divided byk!. We give several applications, to the probabilities that a set of prescribed entries will appear in a set of prescribed cells of a tableau, and to the probabilities that subtableaux of given shapes will occur. Our argument rests on a notion of quasirandomness of families of permutations, and we give sucient conditions for this to hold.

2000 Mathematics Subject Classication:05E10

Keywords:Young tableau, hook formula, probability distribution, quasirandom, subtableau 1 Dept. of Computer Science, Australian National University, ACT 0200, Australia; 2

Dept. of Mathematics, University of Pennsylvania, Philadelphia, PA 19104-6395;

3 Dept. of Mathematics, University of Pennsylvania, Philadelphia, PA 19104-6395; 1

1 Main results

Our basic result is the following.

Theorem 1Fix a standard Young tableauTof shape`k,letN(n;T)be the number of tableaux ofncells that containTas a subtableau, 4 and lett n be the number of all tableaux ofncells. Then we have lim n!1

N(n;T)

t n =f k!;(1) wheref is the number of all tableaux of shape. In other words, the probability that a large tableau containsTis equal to the number of tableaux whose shape is that ofT, divided byk!. We now state two corollaries of this theorem, after which we will discuss several applications. Two excellent references regarding the general theory of tableaux are [2] and [3]. Corollary 1LetCbe a collection of Young tableaux, none of which is a subtableau of any other in the collection, and letN(n;C)be the number of Young tableaux ofncells which have a subtableau inC. The probability that a randomly chosen tableau ofncells has a subtableau inCis then

N(n;C)=t

n ,wheret n is the number of tableaux ofncells (equivalently, the number of involutions ofnletters). We have

Prob(C)=

def lim n!1

N(n;C)

t n X T2C f (T) jTj!;(2) where(T)is the shape of tableauTandjTjis the number of cells inT. Thus we can speak of \the probability that a Young tableau has a subtableau appearing inC," without reference to the size,n, of the tableau. This phrase will mean the limit in (2). The next corollary is the special case of Corollary 1 in which the distinguished listCof tableaux is dened by a list of allowable shapes. Corollary 2LetLbe a list of Ferrers diagrams with no shape a subshape of another in the list, and letN(n;L)be the number of Young tableaux ofncells which have a subtableau with shape in L. The probability that a tableau ofncells has such a subtableau is thenN(n;L)=t n , and we have

Prob(L)=

def lim n!1

N(n;L)

t n X 2L (f 2 jj!:(3) From these results, we will deduce a number of interesting consequences:

1. LetCbe the list of all tableaux ofkcells such that the letterklives in the (i;j) position,

for some xed (i;j). Then Prob(C) is the probability that a Young tableau has the entryk in its (i;j) position. We will nd a rather explicit formula (see subsection 4.1 below) for this probability. This formula was previously found by Regev [4]. 4

A subtableau of a tableauTofncells is a tableau that is formed by the letters 1;2;:::;kinT,forsomekn.

2. LetCbe the list of all tableaux ofkcells in which a certain xed collection of cells contain

prescribed entries. Then Prob(C) is the probability that a Young tableau has the prescribed entries in the prescribed cells. We will nd a rather explicit formula for this probability (see subsection 4.2 below). In the case where the xed collection of cells consists of just two cells, this formula was also previously found by Regev [4], who also found this two-cell probability with a variety of measures on the space of tableaux. Our result, while it applies to arbitrary collections of prescribed cells, holds only in the uniform measure on tableaux.

3. LetLbe the list of all partitions of the integerkwhose parts are2, in Corollary 2. Then

Prob(L) is the probability that a Young tableau has its smallestkletters in just two columns, and we'll nd an explicit formula for it (see subsection 4.3 below). Finally, in section 5, we will nd the probability that the (1;2) entry of a tableau ofncells is k, in the form of an exact formula that is valid for everyn;k. The asymptotic form of this result will illustrate the rate of approach to the limit in the more general theorems already cited above. We thank the anonymous referee who noted that our proof of Corollaries 1 and 2 actually proved them in the form shown here, which is more general than our original statement.

2 Proof of Theorem 1

The set of lettersf1;2;:::;`gis denoted [`]. We begin with a small observation. Proposition 1In the Robinson-Schensted (RS) correspondence between involutions,ofnletters, and tableauxT,ofncells, the subtableau ofTin the letters[k]depends only on the order of the rstkletters in the involution, and does not depend on their preimages or on the disposition of the remainingn-kletters. To see this, note that when a letter>kis inserted into some stage of the RS algorithm it cannot disturb the position of any letterk.2 Fix a tableauT,ofkcells. How many involutions ofnletters correspond to a tableau that containsTas a subtableau? To answer this, letZ(k) denote the set of all permutations ofkletters which correspond, under the RS correspondence, to an ordered pair of tableaux (T;T 0 )forsome tableauT 0 . Then an involution ofnletters will correspond to a tableau that containsTi the set of letters 1;2;:::;kin its value sequence appear in one of the arrangements inZ(k).

Thus ifis some permutation ofkletters, andF

n () denotes the number of involutions ofn letters which containas a subsequence, then exactly X 2Z(k) F n involutions ofnletters correspond to tableaux which containTas a subtableau, so the probability that a randomn-tableau containsTis X 2Z(k) F n t n ;(4) 3 wheret n is the number ofn-involutions. What can be said about the summandF n ()=t n ?Itisthe probability that a randominvolutionof [n] contains the letters 1;2;:::;kin some particular order . If instead we had wanted the probability that a randompermutationof [n] contains the letters

1;2;:::;kin some particular order, the question would have been trivial: the required probability

would be exactly 1=k!, no matter what the \particular order" was. We claim that for involutions the answer is essentially the same, up to a term that iso(1) as n!1. Lemma 1Letbe a xed permutation ofkletters. The probability that a random involution ofn letters containsas a subsequence is1=k!+o(1),forn!1. We will prove this lemma in the next section as a corollary of a more general theorem about the quasirandomness of families of permutations. However, for the moment let us imagine that we have proved the Lemma, and we will now nish the proof of Theorem 1. By (4) and the Lemma, the probability that a tableau ofnletters contains a given subtableauTofkletters is X 2Z(k) 1 k!+o(1) =jZ(k)j k!+o(1) (n!1): SinceZ(k) is the number of all permutations ofkletters corresponding to ordered pairs of the form (T;T 0 )forsomeT 0 , well-known RS theory gives that this is simply the number of tableaux T 0 whose shape is that ofT, i.e.f (T) . Thus the probability that a tableau ofnletters contains a xedTofkletters as a subtableau is f (T) k!+o(1) (n!1); and the proof of Theorem 1 is complete.2 Corollary 1 follows from the theorem by summing over the tableaux in the listC,sincetwo tableaux cannot be subtableaux of the same larger tableaux unless one is a subtableau of the other. Corollary 2 follows from Corollary 1 since, ifCis the list of all of the tableaux whose shapes are inL, X T2C f (T) jTj!= X 2L X fT:(T)=g f (T) jTj! X 2L X fT:(T)=g f jj! X 2L f jj! X fT:(T)=g 1= X 2L (f 2 jj!: 4

3 Involutions are typical

In this section we will prove a proposition that implies Lemma 1 above.

LetPbe a collection of permutations such thatP

n =P\S n is non-empty for innitely many values ofn,whereS n is the set of all permutations of [n]. Ifis a sequence ofkdistinct elements of [n], leth(n;) be the number of elements ofP nquotesdbs_dbs13.pdfusesText_19

[PDF] The distributions of the entries of Young tableaux