Tag Info

New answers tagged

3

Every partition counted in $p(n,k)$ is one of the following two forms. One of the subsets in the partition is $\{n\}$. There are $p(n-1,k-1)$ of these, since all you need to count is the number of ways to partition the remaining elements $1,\ldots, n-1$ into $k-1$ subsets. $\{n\}$ is not one of the subsets. Then, you need to count the number of ways of ...


0

Multiplying formal power series in multiple indeterminates is not really much more complicated than doing so for univariate ones. The main difference is that each term has not a single degree, but separate degrees for each of the $k$ indeterminates, so the coefficient is attached to a point of $\def\N{\Bbb N}\N^k$ rather than of$~\N$. With an infinite ...


0

Generating functions are a powerful tool, you should have no fear in using them. Here we have that $$P_n(k,i)=[z^n]\;(z+z^2+\ldots+z^k)^i = [z^n]\;z^i\left(\frac{1-z^k}{1-z}\right)^i = [z^{n-i}]\;\left(\frac{1-z^k}{1-z}\right)^i,$$ and: $$\frac{1}{(1-z)^i}=\sum_{m=0}^{+\infty}\binom{i+m-1}{m}z^m,\tag{1}$$ $$(1-z^k)^i = \sum_{r=0}^{i}\binom{i}{r}(-1)^r ...


0

I do not have access to the above article at this time but as the results are fairly basic I will try to include a proof here, for the sake of completeness and with no claim to originality. We will use the Polya Enumeration Theorem. By definition we have that $$\Big\langle {n\atop k}\Big\rangle = [z^n] Z(C_k)\left(\frac{z}{1-z}\right)$$ where ...


2

This problem has a solution using ordinary generating functions. First question. Observe that $$\sum_{q\ge 0} q z^q = \frac{z}{(1-z)^2}.$$ Therefore the generating function of the contribution from partitions with $k$ terms is given by $$\left(\frac{z}{(1-z)^2}\right)^{k-1} \frac{z}{1-z}$$ and the contribution from all partitions is $$p(z) = \sum_{k\ge ...


0

I can't provide a nice formula as in your referenced question, but I can show you at least half of the way. Let's start with your Example: There are two dice with 4 and 6 sides. How many ways are there, so that rolling both dice once result in 8 pips? We encode the dies with polynomials and use the exponents to label the pips \begin{align*} ...


2

The partitioning follows directly from the definition of a total order (specifically, this is a strict total order, like < on the integers). Strict total orders exhibit trichotomy: any pair of objects is either in order one way, or the other, or else it is the same object. These three categories are exclusive, thus it partitions the set. For the second ...


1

First, you have to define clearly how you are representing a relation between two real numbers graphically. For example, if $a \sim b$, are you plotting the point $(a, b)$ on the graph? Then it would make sense to plot each point $(a, a)$ for every $a \in S$ (but it will not make up the entire line $y = x$ unless $S = \mathbb R$). If this is your ...


1

Your description of reflexivity is correct. For symmetry it means that the subset $R$ is "symmetric" around the line $y = x$, this means that for any point $(a, b)\in R$ its mirror point $(b, a)\in R$ (it's the point you get by doing reflection in the line $y=x$), i.e. either none of the two points $(a, b)$ and $(b, a)$ is included in $R$, or both of them ...


2

The question if this integral is zero, is one of the classical $NP$-complete Problems given in the book of Garey and Johnson, Computers and Intractability, 1979. p. 252. There called AN14 and with the upper limit of the integral $2\pi$ instead of $\pi$.


1

This paper provides an example of a distribution on $\Bbb N$ which has infinite entropy. Thus, in your case $P$ is any partition satisfying $$ m(I_i) = \frac{1}{\lg(i+1)} - \frac{1}{\lg(i+2)}, \qquad i\in \Bbb N, $$ where $\lg i$ is a logarithm base $2$. For example, $I_1 = [1,\frac1{\lg3})$, $I_2 = [\frac1{\lg 3},\frac12)$, $I_3 = [\frac12,\frac1{\lg5})$ ...


2

Let $\omega(n)$ be the amount of ways you can express $n$ as $a_0!a_1!\cdots c_k!$. Then obviously $\omega(n!) = \Omega(n)$. Since $n\geq \max \lbrace a_i\rbrace_{1\leq i\leq n} \geq P_\max$. Then $\max\lbrace a_i\rbrace$ can be any number, $k$, between $P_\max$ and $n$. For each of those numbers, we have $n! = k!\frac{n!}{k!}$ so we need to express ...



Top 50 recent answers are included