Return to Question

Let $p_1^{a_1}p_2^{a_2}\cdots$ denotes the integer partition of $n$, i.e. $a_1p_1+a_2p_2+\cdots=n$. Or equivalently $m_1+m_2+\cdots=n$. It is known that the number of partitions of set $\{x_1,x_2,\cdots,x_n\}$ corresponding to $p_1^{a_1}p_2^{a_2}\cdots$ (i.e. there are $a_i$ length-$p_i$ parts in the partition) is $$\frac{n!}{(p_1!)^{a_1}\cdots(p_l!)^{a_l}a_1!\cdots a_l!}$$

Now, after obtain partitions the set $\{x_1,x_2,\cdots,x_n\}$, we consider assign values from $\{1,2,\cdots,L\}$ to the elements, such that if elements are in the same part, then the value should be the same; if the element are in different part, then the value should be different. Thus there are in total $\binom{L}{\sum_{i=1}^l a_i}(\sum_{i=1}^l a_i)!\frac{n!}{(p_1!)^{a_1}\cdots(p_l!)^{a_l}a_1!\cdots a_l!}$ valued-assigned set partitions.

For example consider $n=3$ and partition $\{x_1,x_2\}\{x_3\}$, we want to assign values from $\{1,\cdots,L\}$ to them such that $x_1=x_2$ and $x_1\neq x_3$, $x_2\neq x_3$. Thus there are $\binom{L}{2}2!$ ways of assignments.

My question considers adding additional constraint on set partitions and compute how many valued-assigned set partitions are there. Specifically, constraint that $\sum a_i\binom{p_i}{2}=N$ where $N\in\{0,1,2,\cdots,\lfloor \frac{n^2-2\sqrt{2} n^{3/2}-2cn^{1+\epsilon}}{2} \rfloor\}$ where $C,0<\epsilon<\frac{1}{2}$ are constants. Equivalently, $\sum a_ip_i^2=2N+n$ or $\sum m_i^2=2N+n$.

The number of valued-assigned set partitions satisfying this constraint is

$$\sum_{\substack{n^1\neq p_1^{a_1} \cdots p_l^{a_l}\vdash n, \\ \sum_{i=1}^la_i\leq L},\\ \sum_{i=1}^l \binom{p_i}{2}a_i=N(n)}\binom{L}{\sum_{i=1}^l a_i}(\sum_{i=1}^l a_i)!\frac{n!}{(p_1!)^{a_1}\cdots(p_l!)^{a_l}a_1!\cdots a_l!}$$

How to find the asymptotic/non-asymptotic upper bound on this quantity?

Note: $L$ as increasing function of $n$ but it is ok if we consider $L$ to be a constant that does not depend on $n$ if it make problem simpler.

If this problem is hard to solve, I would be grateful to hear the reason, the thoughts.. Thanks in advance for any help!

Let $p_1^{a_1}p_2^{a_2}\cdots$ denotes the integer partition of $n$, i.e. $a_1p_1+a_2p_2+\cdots=n$. Or equivalently $m_1+m_2+\cdots=n$. It is known that the number of partitions of set $\{x_1,x_2,\cdots,x_n\}$ corresponding to $p_1^{a_1}p_2^{a_2}\cdots$ (i.e. there are $a_i$ length-$p_i$ parts in the partition) is $$\frac{n!}{(p_1!)^{a_1}\cdots(p_l!)^{a_l}a_1!\cdots a_l!}$$

Now, after obtain partitions the set $\{x_1,x_2,\cdots,x_n\}$, we consider assign values from $\{1,2,\cdots,L\}$ to the elements, such that if elements are in the same part, then the value should be the same; if the element are in different part, then the value should be different. Thus there are in total $\binom{L}{\sum_{i=1}^l a_i}(\sum_{i=1}^l a_i)!\frac{n!}{(p_1!)^{a_1}\cdots(p_l!)^{a_l}a_1!\cdots a_l!}$ valued-assigned set partitions.

For example consider $n=3$ and partition $\{x_1,x_2\}\{x_3\}$, we want to assign values from $\{1,\cdots,L\}$ to them such that $x_1=x_2$ and $x_1\neq x_3$, $x_2\neq x_3$. Thus there are $\binom{L}{2}2!$ ways of assignments.

Question 1 considers adding additional constraint on set partitions and compute how many valued-assigned set partitions are there. Specifically, constraint that $\sum a_i\binom{p_i}{2}=N$ where $N\in\{0,1,2,\cdots,\lfloor \frac{n^2-2\sqrt{2} n^{3/2}-2cn^{1+\epsilon}}{2} \rfloor\}$ where $C,0<\epsilon<\frac{1}{2}$ are constants. Equivalently, $\sum a_ip_i^2=2N+n$ or $\sum m_i^2=2N+n$.

The number of valued-assigned set partitions satisfying this constraint is

$$\sum_{\substack{n^1\neq p_1^{a_1} \cdots p_l^{a_l}\vdash n, \\ \sum_{i=1}^la_i\leq L},\\ \sum_{i=1}^l \binom{p_i}{2}a_i=N(n)}\binom{L}{\sum_{i=1}^l a_i}(\sum_{i=1}^l a_i)!\frac{n!}{(p_1!)^{a_1}\cdots(p_l!)^{a_l}a_1!\cdots a_l!}$$

How to find the asymptotic/non-asymptotic upper bound on this quantity?

Note: $L$ as increasing function of $n$ but it is ok if we consider $L$ to be a constant that does not depend on $n$ if it make problem simpler.

If this problem is hard to solve, I would be grateful to hear the reason, the thoughts.. Thanks in advance for any help!

Let $p_1^{a_1}p_2^{a_2}\cdots$ denotes the integer partition of $n$, i.e. $a_1p_1+a_2p_2+\cdots=n$. Or equivalently $m_1+m_2+\cdots=n$. It is known that the number of partitions of set $\{x_1,x_2,\cdots,x_n\}$ corresponding to $p_1^{a_1}p_2^{a_2}\cdots$ (i.e. there are $a_i$ length-$p_i$ parts in the partition) is $$\frac{n!}{(p_1!)^{a_1}\cdots(p_l!)^{a_l}a_1!\cdots a_l!}$$

Now, after obtain partitions the set $\{x_1,x_2,\cdots,x_n\}$, we consider assign values from $\{1,2,\cdots,L\}$ to the elements, such that if elements are in the same part, then the value should be the same; if the element are in different part, then the value should be different. Thus there are in total $\binom{L}{\sum_{i=1}^l a_i}(\sum_{i=1}^l a_i)!\frac{n!}{(p_1!)^{a_1}\cdots(p_l!)^{a_l}a_1!\cdots a_l!}$ valued-assigned set partitions.

For example consider $n=3$ and partition $\{x_1,x_2\}\{x_3\}$, we want to assign values from $\{1,\cdots,L\}$ to them such that $x_1=x_2$ and $x_1\neq x_3$, $x_2\neq x_3$. Thus there are $\binom{L}{2}2!$ ways of assignments.

My question considers adding additional constraint on set partitions and compute how many valued-assigned set partitions are there. Specifically, constraint that $\sum a_i\binom{p_i}{2}=N$ where $N\in\{0,1,2,\cdots,\lfloor \frac{n^2-2\sqrt{2} n^{3/2}-2cn^{1+\epsilon}}{2} \rfloor\}$ where $C,0<\epsilon<\frac{1}{2}$ are constants. Equivalently, $\sum a_ip_i^2=2N+n$ or $\sum m_i^2=2N+n$.

The number of valued-assigned set partitions satisfying this constraint is

$$\sum_{\substack{n^1\neq p_1^{a_1} \cdots p_l^{a_l}\vdash n, \\ \sum_{i=1}^la_i\leq L},\\ \sum_{i=1}^l \binom{p_i}{2}a_i=N(n)}\binom{L}{\sum_{i=1}^l a_i}(\sum_{i=1}^l a_i)!\frac{n!}{(p_1!)^{a_1}\cdots(p_l!)^{a_l}a_1!\cdots a_l!}$$

How to find the asymptotic/non-asymptotic upper bound on this quantity?

Note: $L$ as increasing function of $n$ but it is ok if we consider $L$ to be a constant that does not depend on $n$ if it make problem simpler.

Let $p_1^{a_1}p_2^{a_2}\cdots$ denotes the integer partition of $n$, i.e. $a_1p_1+a_2p_2+\cdots=n$. Or equivalently $m_1+m_2+\cdots=n$. It is known that the number of partitions of set $\{x_1,x_2,\cdots,x_n\}$ corresponding to $p_1^{a_1}p_2^{a_2}\cdots$ (i.e. there are $a_i$ length-$p_i$ parts in the partition) is $$\frac{n!}{(p_1!)^{a_1}\cdots(p_l!)^{a_l}a_1!\cdots a_l!}$$

Now, after obtain partitions the set $\{x_1,x_2,\cdots,x_n\}$, we consider assign values from $\{1,2,\cdots,L\}$ to the elements, such that if elements are in the same part, then the value should be the same; if the element are in different part, then the value should be different. Thus there are in total $\binom{L}{\sum_{i=1}^l a_i}(\sum_{i=1}^l a_i)!\frac{n!}{(p_1!)^{a_1}\cdots(p_l!)^{a_l}a_1!\cdots a_l!}$ valued-assigned set partitions.

For example consider $n=3$ and partition $\{x_1,x_2\}\{x_3\}$, we want to assign values from $\{1,\cdots,L\}$ to them such that $x_1=x_2$ and $x_1\neq x_3$, $x_2\neq x_3$. Thus there are $\binom{L}{2}2!$ ways of assignments.

My question considers adding additional constraint on set partitions and compute how many valued-assigned set partitions are there. Specifically, constraint that $\sum a_i\binom{p_i}{2}=N$ where $N\in\{0,1,2,\cdots,\lfloor \frac{n^2-2\sqrt{2} n^{3/2}-2cn^{1+\epsilon}}{2} \rfloor\}$ where $C,0<\epsilon<\frac{1}{2}$ are constants. Equivalently, $\sum a_ip_i^2=2N+n$ or $\sum m_i^2=2N+n$.

The number of valued-assigned set partitions satisfying this constraint is

$$\sum_{\substack{n^1\neq p_1^{a_1} \cdots p_l^{a_l}\vdash n, \\ \sum_{i=1}^la_i\leq L},\\ \sum_{i=1}^l \binom{p_i}{2}a_i=N(n)}\binom{L}{\sum_{i=1}^l a_i}(\sum_{i=1}^l a_i)!\frac{n!}{(p_1!)^{a_1}\cdots(p_l!)^{a_l}a_1!\cdots a_l!}$$

How to find the asymptotic/non-asymptotic upper bound on this quantity?

Note: $L$ as increasing function of $n$ but it is ok if we consider $L$ to be a constant that does not depend on $n$ if it make problem simpler.

If this problem is hard to solve, I would be grateful to hear the reason, the thoughts.. Thanks in advance for any help!

Let $p_1^{a_1}p_2^{a_2}\cdots$ denotes the integer partition of $n$, i.e. $a_1p_1+a_2p_2+\cdots=n$. Or equivalently $m_1+m_2+\cdots=n$. It is known that the number of partitions of set $\{x_1,x_2,\cdots,x_n\}$ corresponding to $p_1^{a_1}p_2^{a_2}\cdots$ (i.e. there are $a_i$ length-$p_i$ parts in the partition) is $$\frac{n!}{(p_1!)^{a_1}\cdots(p_l!)^{a_l}a_1!\cdots a_l!}$$

Now, after obtain partitions the set $\{x_1,x_2,\cdots,x_n\}$, we consider assign values from $\{1,2,\cdots,L\}$ to the elements, such that if elements are in the same part, then the value should be the same; if the element are in different part, then the value should be different. Thus there are in total $\binom{L}{\sum_{i=1}^l a_i}(\sum_{i=1}^l a_i)!\frac{n!}{(p_1!)^{a_1}\cdots(p_l!)^{a_l}a_1!\cdots a_l!}$ valued-assigned set partitions.

For example consider $n=3$ and partition $\{x_1,x_2\}\{x_3\}$, we want to assign values from $\{1,\cdots,L\}$ to them such that $x_1=x_2$ and $x_1\neq x_3$, $x_2\neq x_3$. Thus there are $\binom{L}{2}2!$ ways of assignments.

My question considered adding additional constraint on set partitions and compute how many valued-assigned set partitions are there. Specifically, constraint that $\sum a_i\binom{p_i}{2}=N$. Consider $N(n)\in\{0,1,2,\cdots,\lfloor \frac{n^2-2\sqrt{2} n^{3/2}-2cn^{1+\epsilon}}{2} \rfloor\}$ where $C,0<\epsilon<\frac{1}{2}$ are constants. Equivalently, $\sum a_ip_i^2=2N+n$ or $\sum m_i^2=2N+n$.

The number of valued-assigned set partitions satisfying this constraint is

$$\sum_{\substack{n^1\neq p_1^{a_1} \cdots p_l^{a_l}\vdash n, \\ \sum_{i=1}^la_i\leq L},\\ \sum_{i=1}^l \binom{p_i}{2}a_i=N(n)}\binom{L}{\sum_{i=1}^l a_i}(\sum_{i=1}^l a_i)!\frac{n!}{(p_1!)^{a_1}\cdots(p_l!)^{a_l}a_1!\cdots a_l!}$$

How to find the asymptotic/non-asymptotic upper bound on this quantity?

Note: $L$ as increasing function of $n$ but it is ok if we consider $L$ to be a constant that does not depend on $n$ if it make problem simpler.

Let $p_1^{a_1}p_2^{a_2}\cdots$ denotes the integer partition of $n$, i.e. $a_1p_1+a_2p_2+\cdots=n$. Or equivalently $m_1+m_2+\cdots=n$. It is known that the number of partitions of set $\{x_1,x_2,\cdots,x_n\}$ corresponding to $p_1^{a_1}p_2^{a_2}\cdots$ (i.e. there are $a_i$ length-$p_i$ parts in the partition) is $$\frac{n!}{(p_1!)^{a_1}\cdots(p_l!)^{a_l}a_1!\cdots a_l!}$$

Now, after obtain partitions the set $\{x_1,x_2,\cdots,x_n\}$, we consider assign values from $\{1,2,\cdots,L\}$ to the elements, such that if elements are in the same part, then the value should be the same; if the element are in different part, then the value should be different. Thus there are in total $\binom{L}{\sum_{i=1}^l a_i}(\sum_{i=1}^l a_i)!\frac{n!}{(p_1!)^{a_1}\cdots(p_l!)^{a_l}a_1!\cdots a_l!}$ valued-assigned set partitions.

For example consider $n=3$ and partition $\{x_1,x_2\}\{x_3\}$, we want to assign values from $\{1,\cdots,L\}$ to them such that $x_1=x_2$ and $x_1\neq x_3$, $x_2\neq x_3$. Thus there are $\binom{L}{2}2!$ ways of assignments.

My question considers adding additional constraint on set partitions and compute how many valued-assigned set partitions are there. Specifically, constraint that $\sum a_i\binom{p_i}{2}=N$ where $N\in\{0,1,2,\cdots,\lfloor \frac{n^2-2\sqrt{2} n^{3/2}-2cn^{1+\epsilon}}{2} \rfloor\}$ where $C,0<\epsilon<\frac{1}{2}$ are constants. Equivalently, $\sum a_ip_i^2=2N+n$ or $\sum m_i^2=2N+n$.

The number of valued-assigned set partitions satisfying this constraint is

$$\sum_{\substack{n^1\neq p_1^{a_1} \cdots p_l^{a_l}\vdash n, \\ \sum_{i=1}^la_i\leq L},\\ \sum_{i=1}^l \binom{p_i}{2}a_i=N(n)}\binom{L}{\sum_{i=1}^l a_i}(\sum_{i=1}^l a_i)!\frac{n!}{(p_1!)^{a_1}\cdots(p_l!)^{a_l}a_1!\cdots a_l!}$$

How to find the asymptotic/non-asymptotic upper bound on this quantity?

Note: $L$ as increasing function of $n$ but it is ok if we consider $L$ to be a constant that does not depend on $n$ if it make problem simpler.