Tag Info

New answers tagged

1

You can partition any set $X$ as $X=\displaystyle\bigcup_{x\in X}\{x\}$.


0

The trick here is to consider the following "switching operation": $$\sigma_{ij}(\lambda_1,\ldots,\lambda_N) = (\lambda_1,\ldots,\lambda_i+1,\ldots,\lambda_j-1,\ldots,\lambda_N).$$ Now the question becomes: what can we say about $f(\sigma_{ij}(\lambda))$? Assume without loss of generality that $\lambda_j\ge1$, and that all $\lambda_k\ge0$. A short ...


0

This problem is a straightforward application of the Polya Enumeration Theorem and very similar to the problem discussed at this MSE link. Remark. What follows below does permit repeated factors, the formula for distinct factors is at the end. Recall the recurrence by Lovasz for the cycle index $Z(S_n)$ of the multiset operator $\mathfrak{M}_{=n}$ on ...


0

Yes! From a number theoretical perspective, this is known as the divisor function. Or, even more generally, $\sigma_k (n)$ where the sigma function denotes the sum of all divisors of an integer to the power $k$. If we set $k=0$ we see that this is exactly the same as counting all possible divisors of this integer. The general form of the divisor function ...


0

Any number in prime factorization would look like: N = X_1^a * X_2^b * X_3^c * ... where X_1, X_2, X_3, ... are its prime factors Notice that all powers of X_1 will be factors of N. So we can vary a from 0 through 1, 2, 3, ... to a. i.e. a can have a+1 values and for all these, X_1^a will be a factor. Similarly X_2 and X_3 and so on will be factors from 0 ...


0

Hint: Here is one equivalence class (which in turn is a set of the partition): $\{\{3\},\{1,3\},\{2,3\},\{1,2,3\}\}$. This set of the partition contains all subsets of $\{1,2,\dots,100\}$ with max element $3$.


0

Your proven identity looks like the q-binomial theorem, and the terms can be rewritten with q-shifted factorial. I don't have the answer for your question, but it might exist some useful identities in q-series that can help to prove the identity. If you have already use this, then ignore my answer.


1

Recall the species of set partitions with the constituents marked which is $$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$ which gives the generating function $$G(z, u) = \exp(u(\exp(z)-1)).$$ It follows that the exponential generating function of Bell numbers is given by $$G(z) = \exp(\exp(z)-1).$$ Suppose we are trying to compute ...


2

Notice that \begin{align} S & = \sum_{n = 0}^{\infty} \frac{n^{2}}{n!} \\ & = \frac{0^{2}}{0!} + \frac{1^{2}}{1!} + \frac{2^{2}}{2!} + \frac{3^{2}}{3!} + \cdots \\ & = \frac{1}{0!} + \frac{2}{1!} + \frac{3}{2!} + \frac{4}{3!} + \cdots. \end{align} Then \begin{align} S - e & = \left( \frac{1}{0!} + \frac{2}{1!} + \frac{3}{2!} + ...


0

You want the following theorem, which I quote from Miklós Bóna, Introduction to Enumerative Combinatorics: Theorem. Let $a_n$ be the number of ways to carry out a certain task on an $n$-element set, and set $a_0=0$. For $n\ge 1$, let $h_n$ be the number of ways to partition $[n]$ into an arbitrary number of non-empty blocks, and then to carry out the ...


-1

This is equal to (12C3 * 3C1 * 2^9)/ 3^12 which is inturn equal to 55/3 * (2/3)^11 hence option (2).


0

Sometimes a little research can help. The formula you posted was discovered by Jon Perry in 2003. The generating function for this problem is: $$g(x) = \frac{1}{(1-x) \left(1-x^2\right) \left(1-x^3\right) \left(1-x^4\right)} $$ There does not seem to be something simple for your question but Michael Somos comes up with ...


1

As you started to say in your edit, this all comes down to plane partitions. An expression for the number of your partitions of $n$ is $$ \sum_{c=1}^n pp(n-c,c) $$ ($c$ for [core]) where $pp(i,j)$ is the number of plane partitions of $i$ with largest part $j$; this triangle of numbers is given in OEIS A242642 (with references back to MacMahon), which is ...


2

For the asymptotic, given $n$ we want to maximize $\frac {(n-1)^k}{k^{2k}}$. You probably know how to do that, take the derivative and set to zero. Alpha says this comes at $n=e^2k^2+1$, so $k=\frac{\sqrt{n-1}}e$


2

The criteria demands that when you and your friends order a pizza and you each take a part of the pizza: Every one got some part of the pizza. No two people ate from the same slice. You ate the entire pizza. As for the proof, my best advice is once you get the intuitive idea, or even well before that, just work with the definitions carefully and slowly. ...


1

Do I understand this correctly? The degrees $d_s$ are given, and you want to count the number of subsets $T$ of $S$ such that $\sum_{t \in T} d_t \ge N$ and $|T| \le N$. Note that given such a $T$, you can easily get the $p_t$ by starting with the $d_t$ and reducing one at a time. The number $c(m,n)$ of $T$ with each given cardinality $m = |T|$ and sum ...


1

There are $2^n$ subsets of the first $n$ positive integers, and for each subset the sum is bounded below by zero and above by $\sum_{i=1}^n i^k = O(n^k/k)$. The problem of finding a partition with equal sums is equivalent to finding a subset with a particular sum in this range, specifically $\frac 12 \sum_{i=1}^n i^k$. If we think these subset sums are ...


0

This is probably way too little too late, but someone just linked to this question from elsewhere on the site and seeing as it was never answered I thought I'd give an answer. Consider the natural action of $S_n$ on ($\mathbb{C}$-linear combinations of) $b$-element subsets of $\{1,2,\dots,n\}$. This is not quite the representation you want but its character ...



Top 50 recent answers are included