Hot answers tagged

4

The existence of a solution is guaranteed by Baranyai's theorem. A proof of the theorem can be found, for instance, in Dieter Jungnickel - Graphs, Networks and Algorithms. The proof is constructive, so an algorithm can be derived from it. The book I mention contains references for explicit constructions in certain special cases. Furthermore, a Python ...


3

Consider the problem of $4n$ balls with $n$ balls of each of the four colors being distributed into four indistinguishable baskets where each basket holds exactly $n$ balls. The naive approach here would be to use the Polya Enumeration Theorem (twice). Surprisingly enough this is sufficient to compute the initial segment of the sequence using the ...


3

You can find a bijection between the set of partitions of $n$ into $r$ non-negative integers and of $n+r$ into $r$ positive integers. Let $(\alpha_1, \alpha_2, \dots, \alpha_r)$ be a partition of $n$ such that $\alpha_i \geq 0, \forall i \in \{1,2,\dots,r\}.$ Then $(\alpha_1 + 1, \alpha_2 + 1, \dots, \alpha_r + 1)$ is a partition of $$ (\alpha_1 + 1) + ( ...


3

Because $\sim$ is reflexive, for every $x\in X$ we have $x\in [x]$, thus $X\subseteq \bigcup_{[x] \in X/\sim} [x] \subseteq X$, which proves the first condition. For the second condition, we prove the contrapositive. Suppose $[x] \cap [y] \ne \emptyset$; we show that $[x] = [y]$. Given $z\in [x] \cap [y]$, we have $z\sim x$ and $z\sim y$, so by symmetry and ...


3

This answer is a slightly different variation of the theme which affirms the result of @MarkoRiedel. Here we use exponential generating functions to count the number of configurations of labelled objects and apply the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a generating series. If we are looking for the number of ...


3

Comment From Def. 6 we have that: if $x \mathrel{\mathscr{E}}y$, then $x \in y/\mathscr E$. From Th. 3(a) we have that: $x \in x/\mathscr{E}$ Thus, we have that: if $x \mathrel{\mathscr{E}}y$, then $x \in x/\mathscr{E}\cap y/\mathscr{E} \neq \emptyset$. Thus, how to conclude from: $x/\mathscr{E}\cap y/\mathscr{E}\neq \emptyset$ that $x/\mathscr{E} ...


2

With these kinds of problems it can be useful to employ Stirling numbers of the second kind which encapsulate inclusion-exclusion. The count then becomes quite simple. Suppose we first count $n$-digit numbers with one, two, three and four different digits where we include those that start with one or more zeroes. This is given by ...


2

You can use generating functions. Let $P=p_1x+p_2x^2+p_3x^3+p_4 x^4+p_5 x^5 +p_6 x^6$ where $p_i$ is the probability of $i$ occurring when rolling the die once. Then the coefficient of $x^k$ in $P^N$ gives the probability of rolling a sum of $k$ when rolling the die $N$ times and summing. For example, suppose ...


2

You don't have $(1) \le (1)(2)$ because $(2)$ is not a reunion of blocks from $(1)$, just like you don't have $(1)(23) \le (1)(2)(3)$ because $(2)$ isn't a reunion of blocks from $(1)(23)$. You can prove that the natural bijection $f : \alpha \mapsto \alpha \cup \{ \{x_{n+1}\} \cup X \setminus \bigcup \alpha \}$ preserves the ordering. If $\alpha \le ...


2

Take the Young diagram of a partition of $n$ into at most $r$ parts, and add an extra box to the end of each row. If there were less than $r$ rows, then add additional rows of length one so that the diagram has $r$ rows. This way, we get the Young diagram of a partition of $n + r$ with exactly $r$ rows. To see that this is a bijection, it is enough to show ...


2

$$\{A,B,C,D,E,F\}\{G,H,I,J,K\}$$ Starting with this first partition, we want to choose the second partition so that no subset with $4$ elements is repeated. We must therefore swap exactly $3$ elements between the two set. All such swaps are identical at this point, so we can fix the second partition as: $$\{A,B,C,G,H,I\}\{D,E,F,J,K\}$$ Next, we'll want to ...


1

Note: The answer of @Logophobic seems to be very close to an optimal solution. Here is some elementary information which makes this claim reasonable together with some aspects which could be helpful to find a proper selection of the sets $A_k,B_k$. If we denote the eleven players with $\{x_1,x_2,\ldots,x_{11}\}$ we observe that @Logophobic uses some ...


1

For each $s\in S$ define $p_s$ as the intersection of all elements of $Q$ containing $s$, intersected with the intersection of all complements of elements of $Q$ that do not contain $s$. Then if $p_s$ intersects $p_t$, we must have $p_s=p_t$, this gives the desired partition. In other words, for each $s$ and each $q\in Q$ let $r_{s,q}=q$ if $s\in q$, and ...


1

Now as you have edited ofcourse answer changes so the answer is creating equal groups of 4 . There are m objects to be divided in $a...d$ where they are same (baskets)so the ways are $\frac{40!}{(10!)^4.4!}$ you can reason out why $4!$


1

One way is to consider the Ferrers diagrams of the partitions. It’s easiest to start with a partition of $n+r$ into $r$ parts. Its Ferrers diagram will have exactly $r$ rows. If you remove the first column of the diagram, you’ll have the Ferrers diagram of a partition of $n$. That diagram might have fewer than $r$ rows (why?), but it can’t have more, so ...


1

You are looking for the integer partitions of 30, and in particular those that are made of 4 parts. In general this is a very well studied problem, and there is not a simple closed form that can allow computing this number from 30 and 4. Depending on your mathematical level you may find useful the not-so-simple formulas you find on Wikipedia or MathWorld. ...


1

You are asking for the number of integer partitions restricted to the number of parts. Let $n$ be the partitioned number, and $k$ the number of parts. You are looking for the number of partitions of the integer $n$ into exactly $k$ parts. See e.g. Wikipedia: Partition (number theory). For your problem, $n=30$, $k=4$. The sequence in OEIS is: A026810. ...


1

I do not think your first example is correct. We have between $1$ and $4$ red balls, exactly $2$ balls, and at most $2$ yellow balls. You have an extra $1$ in two of your expressions (I am not sure why). $$[x^7](x+x^2+x^3+x^4)(x^2)(1+x+x^2) = 2$$ Your answer to the dice question is exactly correct. You can make it a little more compact ...


1

Yes, it's correct. Note that you only need to generate the first row. The first column needs to be strictly increasing and thus follows immediately. So your first row should be indeed 123, 124, 125, 134, 135, 145 (in what I consider to be a more orderly fashion).


1

It seems to me the spirit of the original context is experimental. In order to get an analytic answer, even in a simple case with only two rolls, you need to specify precisely how the die is loaded. Here is a simulation in R of an experiment with $n = 3$ rolls of a die loaded so that faces 1 to 6 appear with probabilities $(1/12, 1/12, 1/12, 3/12, 3/12, ...


1

Let’s look at $p_5(9)$. The Ferrers diagrams of the $5$-part partitions of $9$ are: $$\begin{array}{lll} \begin{array}{ccc} \bullet&\bullet&\bullet&\bullet&\bullet\\ \bullet\\ \bullet\\ \bullet\\ \bullet \end{array}&\qquad& \begin{array}{ccc} \bullet&\bullet&\bullet&\bullet\\ \bullet&\bullet\\ \bullet\\ \bullet\\ ...


1

A partition of a set $A$ is a set $S$ of subsets of $A$ which satisfy: $\varnothing\notin S$. If $X,Y\in S$ then either $X=Y$ or $X\cap Y=\varnothing$. For every $a\in A$ there is some $X\in S$ such that $a\in X$. The set $\{a,b,c\}$ is a subset of $A$ but not necessarily a set of subsets of $A$. Likewise, $\{a,b,c,\varnothing\}$ is generally not even a ...



Only top voted, non community-wiki answers of a minimum length are eligible