User vasu vineet - MathOverflow

Box removing operators on partitions

2013-02-20T03:43:18Z

Consider the box removing operators $d_i$ for $i\geq 1$ defined as follows.

Let $\lambda$ be a partitions. Then $d_i(\lambda)$ is the partition obtained by removing a box from a part of length $i$ in $\lambda$ so as to obtain another partition. (Here removing a box is an operation performed on the Ferrers diagram of $\lambda$.) If there is no part of length $i$ in $\lambda$, then $d_i(\lambda)=0$. (As pointed out by Darij in the comments below, $0$ is not to be confused with the empty partition $\varnothing$.)

It is easy to see that the following equalities are satisfied. $$ d_id_j=d_jd_i \text{ if } \lvert i-j \rvert\geq 2$$ $$d_id_{i+1}d_i=d_id_id_{i+1}$$ $$d_id_{i+1}d_{i+1}=d_{i+1}d_id_{i+1}$$

Now consider words in the $d_i$. Two words $w_1$ and $w_2$ are called equivalent if $w_1(\lambda)=w_2(\lambda)$ for all partitions $\lambda$.

Is it true that if $w_1, w_2$ are equivalent then one can be obtained from the other by using the 3 relations mentioned above?

Bijection between saturated chains in Youngs lattice and SYTs using jeu-de-taquin

2012-06-23T21:45:26Z

Consider the following saturated chain in the Young's Lattice: $$ \phi \subset \lambda^{1}\subset \lambda^{2}\subset \cdots \subset\lambda^{n}$$ where $\phi$ is the empty partition and $\lambda^{i}$ is a partition of $i$, denoted $\lambda^{i} \vdash i$, for $i=1,2,\ldots ,n$.

I am going to consider the Ferrers diagram of partitions in French notation, and reference the cells of the Ferrers diagram by the pair (row,column).

With the aforementioned saturated chain, associate a column growth word $w=w_1w_2\ldots w_n$ in the following manner: $$w_i= \text{ column of the cell } \lambda^{i}/\lambda^{i-1}$$ Starting from the empty tableau, do jeu-de-taquin slides starting from the outer corner as given by the word $w$ to recover a standard Young tableau(SYT) of shape $\lambda^{n}$. This gives one a(nother) bijection between saturated chains in Young's Lattice and SYTs.

$\textbf{Question}$: Is it possible to predict what the SYT associated with a saturated chain will be, just by the knowing the column growth word, so as to avoid making $n$ jeu-de-taquin slides?

What follows is what I have been doing. I would like a reference where this has already been dealt with, or is implicit (since I am pretty sure this has to be in the literature somewhere).

1) Reverse the word $w$ to obtain $w^r$.

2) Standardise the word $w^r$ to obtain a permutation $\pi$.

3) $\pi \longleftrightarrow (P,Q)$ via the RSK correspondence.

4) $Q^{t}$ (the transpose of the tableau, that is) is the SYT we are looking for.

Example for making the notation clear: Consider the maximal chain $\phi \subset (1)\subset (1,1)\subset (2,1)\subset (2,1,1)\subset (2,2,1)$. Then the column growth word associated with this chain is $w=11212$. Then $w^r=21211$ and the standardisation gives the permutation $41523$ in single line notation.

A bijection between sets of Young tableaux of two kinds

2011-07-13T06:25:50Z

Assuming that the problem of exhibiting a bijection is not considerd a frivolous pursuit, allow me to ask a question troubling me for some time now.

Let $\lambda \vdash n$ denote the fact that $\lambda$ is a partition of $n$. Denote the number of parts by $l(\lambda)$. If $T$ is a standard Young tableau (SYT), we will denote the underlying partition shape by $sh(T)$.

Given a positive even integer $2n$, let $$ Pe_{2n}=\{ \lambda: \lambda\vdash 2n,\text{ } l(\lambda) \leq3 \text{ and all parts of } \lambda \text{ are even} \}$$ and $$ Qe_{2n}=\{ \lambda: \lambda\vdash 2n, \lambda = (k,k,1^{2n-2k}), \text{ }k\geq 1 \}$$

Using these sets we will define two more sets whose elements are SYTs. $$ TPe_{2n}=\{T: T \text{ an SYT, } sh(T)\in Pe_{2n} \}$$ and $$ TQe_{2n}=\{T: T \text{ an SYT, } sh(T)\in Qe_{2n} \}$$

$\textbf{Question}$: Is there a bijective proof exhibiting the fact that the cardinalities of $TPe_{2n}$ and $TQe_{2n}$ are equal?

The second question is very similar. Given an odd positive integer $2n+1$, let $$ Po_{2n+1}=\{ \lambda: \lambda\vdash 2n+1,\text{ } l(\lambda)=3 \text{ and all parts of } \lambda \text{ are odd} \}$$ and $$ Qo_{2n+1}=\{ \lambda: \lambda\vdash 2n+1, \lambda = (k,k,1^{2n+1-2k}), \text{ }k\geq 1 \}$$

Using these sets we will define two more sets whose elements are SYTs. $$ TPo_{2n+1}=\{T: T \text{ an SYT, } sh(T)\in Po_{2n+1} \}$$ and $$ TQo_{2n+1}=\{T: T \text{ an SYT, } sh(T)\in Qo_{2n+1} \}$$

$\textbf{Question}$: Is there a bijective proof exhibiting the fact that the cardinalities of $TPo_{2n+1}$ and $TQo_{2n+1}$ are equal?

I tried quite a few approaches ( Motzkin path interpretations, matching diagrams etc) but did not succeed. I hope somebody here can guide me.

The relevant OEIS entry would be link text

Thanks,

Vasu

Lattice walks and a q-series curiosity

2010-10-29T03:20:16Z

I had been fiddling around with a particular expression over the summer. Since I haven't had much luck with it, I thought it was about time I took an opinion over the question.

So here's where it all began. Consider the hexagonal lattice (also called the equilateral triangular lattice). Fix some point $P$ on the lattice to be the origin. Let $W_{n}$ be the number of walks of length $n$ which start and end at $P$. I was considering the simplest possible model, so there are no constraints (meaning no self-avoidance condition or anything of that sort). In trying to enumerate these walks, I came up with this 'cute' little identity

$$\displaystyle\sum_{j=0}^{n}\binom{n}{j}^{3} = \sum_{j=0}^{n}\binom{n}{j}2^{j}\times W_{n-j}$$ We have the initial constraints being $W_{0}=1$, $W_{1}=0$.

Next I tried to tweak out a q-deformation of this particular identity. Combinatory-wise I haven't got anything particularly exciting. But here is the q-version I am considering. The binomial coefficients are replaced with the q-binomial coefficients. Fix an integer $k$. Define $$2_{k}^{j} = \prod_{i=1}^{j} (1+q^{k+i})$$ with the norm that $2^{0}=1$. Now this allows one to obtain polynomials $W_{n,k}(q)$ recursively from the identity above with the initial conditions $W_{0}=1$, $W_{1}=0$. They don't necessarily have positive coefficients but as $n$ gets large, they do. Though one does obtain interesting polynomials for $k=-1,0$, here's the one I'll mention. As $k,n$ become large, one notices (formally) $$W_{n,k}(q)\rightarrow\prod_{i=1}^{\infty} \frac{1}{(1-q^i)^2}$$

Is there a good reason? I have a feeling my setup is slightly artificial, but I'd love to know what's happening!

Edit dated 6th Jan'2011:

$$W_{n}=\displaystyle\sum_{i=0}^{n} (-2)^{n-i}\binom{n}{i}(\displaystyle\sum_{j=0}^{i} \binom{i}{j}^3)$$

Enumeration of Standard Young Tableau of bounded height

2010-11-23T08:15:32Z

First for some notation $$ l(\lambda) = \text{ number of parts in a partition } \lambda \vdash n$$

$$ f_{\lambda} = \text{number of standard Young tableau of shape } \lambda\vdash n$$

The number $f_{\lambda}$ is given by the hook length formula and might not acquire a "nice form". Given an integer $k$ consider the problem of computing $$ \tau_{k}(n) = \displaystyle\sum_{\lambda\vdash n \text{, } l(\lambda)\leq k}f_{\lambda}$$

Contrary to expectation, relatively neat closed forms are known for $\tau_{2}(n)$, $\tau_{3}(n)$ and $\tau_{4}(n)$. Gessel link text proved the following $$\tau_{2}(n) = \binom{n}{\lfloor \frac{n}{2} \rfloor}$$ $$\tau_{3}(n) = M_{n}$$ $$\tau_{4}(n) = C_{\lfloor \frac{n+1}{2} \rfloor}C_{\lceil \frac{n+1}{2} \rceil}$$ where $M_{n}$ denotes the n'th Motzkin number link text and $C_{n}$ denotes the n'th Catalan number link text

(Here both sequences are indexed starting 0)

(Aside: Proving the first two identities bijectively is a cute exercise in my opinion.)

As a by-product of my research I obtained the following identity $$ \displaystyle\sum_{\lambda\vdash n, l(\lambda)=5,\lambda_{5}=1}f_{\lambda} = \displaystyle\frac {\lfloor \frac{k+1}{2} \rfloor (\lceil \frac{k+1}{2} \rceil +1)}{k+1}C_{\lfloor \frac{k+1}{2} \rfloor}C_{\lceil \frac{k+1}{2} \rceil} - C_{\lfloor \frac{k}{2} \rfloor +1}C_{\lceil \frac{k}{2} \rceil +1}+M_{k}$$ where the sum on the left runs over all partitions $\lambda$ with length exactly 5 and minimum part $\lambda_{5}$ being 1. Admittedly this is very specific but my question is what is known about sums of the above sort

a) where the minimum part is fixed and so is the length of the partition ?

b) where $l(\lambda) \leq k$ and the k'th part $\lambda_{k} \leq i$ for a fixed non-negative integer $i$?

Gessel, I believe, used some really clever symmetric function manipulation to obtain the identities mentioned earlier. I'd appreciate if somebody has seen this stuff elsewhere ( i.e. reference other than Gessel / Gouyou-Beauchamps) and directs me. Thanks!

Number of Longest Decreasing subsequences and RSK

2010-11-10T04:48:28Z

It is well known via the RSK-correspondence that the length of the longest decreasing subsequence in a permutation $\pi \in S_n$ is the length of the longest column of the insertion tableau of $\pi$. ( The insertion tableau and the recording tableau produced by this algorithm have the same shape)

link text

My question is what else can be gleaned from the RSK correspondence in terms of ,say,

a) the length of the next longest decreasing subsequence in $\pi$ ?

b) the number of longest decreasing subsequences in $\pi$, given the fact that there is exactly one column of maximum length ?

c) can we say more about the above two questions if we knew that $\pi$ was an involution? (If $\pi$ happens to be an involution, then insertion tableau and recording tableau produced are equal)

A Distinct parts/Odd parts identity for standard Young tableaux

2010-10-26T06:43:37Z

Let $\lambda$ denote a partition of size $n$. Let $$d_{\lambda}= \text{number of distinct parts of } \lambda $$ $$o_{\lambda}= \text{number of odd parts of } \lambda $$ $$f_{\lambda}= \text{number of standard Young tableau of shape } \lambda $$ Given an involution $\pi \in S_{n}$, whose insertion tableau has shape $\lambda$, it is well known (via the Robinson-Schensted correspondence, and neatly outlined in Sagan's book on the Symmetric Group) that : $$ o_{\lambda^{t}}= \text{number of fixed points in the involution } \pi $$ $$ \sum_{\lambda \vdash n} f_{\lambda}= \text{number of involutions in } S_{n} $$

In the aforementioned formulae, $\lambda^{t}$ refers to the conjugate of the partition $\lambda$. Now, some computations I have carried out for Kronecker products of two irreducible characters of $S_{n}$ revealed the following identity in a special case: $$\sum_{\lambda \vdash n}d_{\lambda}f_{\lambda}=\sum_{\lambda \vdash n}o_{\lambda}f_{\lambda}$$

Note that the right hand side actually counts the total number of fixed points in all involutions in $S_{n}$. I did manage to prove the above result in general, but I am hoping someone could guide me to a proof which is bijective, i.e say uses the RS correspondence to establish the left hand side equals the the total number of fixed points in all involutions in $S_{n}$.

Also, I'd like it if I could be directed to where this and/or similar sums appeared.(as an exercise in a book, or in some paper).

Thanks!

Edit: I had a look at Sagan, which I did not have handy last night and made a minor change in saying the number of fixed points in an involution $\pi \in S_{n}$ is the number of odd columns in the insertion tableau of $\pi$.

Edit(10/27):

I thought I should put down the idea that I had. But since I am not sure if this should count as an answer, I am putting it in the body of the question. Note that $$\sum_{\lambda \vdash n}d_{\lambda}f_{\lambda}=\sum_{\lambda \vdash n+1}f_{\lambda}-\sum_{\lambda \vdash n}f_{\lambda}$$ So all that remains to be shown is the nice fact that the total number of fixed points in all the involutions of $S_{n}$ is the difference between the number of involutions in $S_{n+1}$ and the number of involutions in $S_{n}$.

Comment by Vasu vineet

2013-04-27T06:58:04Z

and I don't think there is such a thing as 'the' q-analog

Comment by Vasu vineet

2013-04-12T18:59:28Z

I imagine this might get closed. But here's a hint to get you started anyway: every part of odd length can be 'bent' into a hook shape that is symmetric.

Comment by Vasu vineet

2013-02-21T20:14:15Z

Thank you for the answer. Let me see if I can push the idea here in the general case.

Comment by Vasu vineet

2013-02-20T23:08:13Z

Here is the reference of Fomin-Greene that I am talking about (example 2.6 specifically) math.lsa.umich.edu/~fomin/Papers/ncschur.ps

Comment by Vasu vineet

2013-02-20T23:07:34Z

Thanks for the answer and the link to Garsia's paper. But I do believe there is a lot more going on here than the case you mention, and I disagree that these are the Coxeter-Knuth relations. I checked a paper of Fomin's that defines the adjoint of the operators that I am considering, calling them Schur operators (or box adding operators if you will). He further goes on to say that the complete list of relations between the Schur operators is not known.

Comment by Vasu vineet

2013-02-20T05:45:17Z

If you check the relations that I gave, then they already list some words that are equivalent. For example, $d_1d_3$ and $d_3d_1$ are equivalent words because either both act on a partition to give $0$ or the same partition. Hope this clarifies.

Comment by Vasu vineet

2013-02-20T04:17:02Z

Sorry, I should have mentioned that. I will edit the question. Thanks

Comment by Vasu vineet

2012-10-05T17:41:18Z

I think a combinatorial model for the case at hand is dealt with in emis.de/journals/SLC/wpapers/s54goupchau.html

Comment by Vasu vineet

2012-06-25T06:46:30Z

Thanks for the reference, Prof. Stanley. Let me look at the paper in detail before I accept the answer. From a first glance, surely the paper seems to be doing the sort of thing I want.

Comment by Vasu vineet

2011-12-26T15:28:05Z

I have seen people dealing with Left Regular Bands call this 'left regularity'. I might be mistaken.

Comment by Vasu vineet

2011-11-22T05:52:29Z

This paper discusses a related problem (Generalized ballot problem): thales.math.uqam.ca/~serrano/paths.pdf

Comment by Vasu vineet

2011-11-16T01:48:42Z

Okay, I see the question got answered!

Comment by Vasu vineet

2011-11-16T01:47:24Z

Not sure if this helps but in the case where A and B are equal then one can put $x_i=\sqrt{t}q^j$, $y_j=\sqrt{t}q^j$ and the expression looks like the Cauchy determinant, and can be expanded as sum of product of Schur functions. Then you are trying to compute a specialization of Schur functions labeled by a partition $\lambda$ with the alphabets being $\sqrt{t}q^i$. The quotient of alternants formula for Schur function might come handy.

Comment by Vasu vineet

2011-09-10T06:55:24Z

@Gjergji : Could you please tell me what are the values for $TP_{10}$ and $TQ_{10}$ that you obtained? Thanks.

Comment by Vasu vineet

2011-09-03T19:28:23Z

I seem to be getting 13393689 for the both of them. I will look into my code to see if I am bungling up somewhere.