# Tag Info

## New answers tagged partitions

1

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 ...

0

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 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 ... -2 Consider this example$S = \{s_1,s_2,s_3\} = \{1,2,3\}$i.e$s_1 = 1 , s_2 = 2 , s_3 = 3$and$N = 4$i.e$Sum = 4$. There are four solutions:$\{1,1,1,1\},\{1,1,2\},\{2,2\},\{1,3\}C(N,m)$can be partitioned in two ways with or without considering sm i.e with considering$s_3$i.e$3$in set$\{1,3\}$or without considering$s_3$i.e ... 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 ... 0 A partition is a set of sets whose union is the universal set and intersection is the null set. In your case,$\{a,b,c\}$is not a partition because, its elements$a ,b, c$are not sets.$\{\{a,b,c\}\}$is a partition because its only element$\{a,b,c\}$is the set$A$. Other examples of partitions:$\{\{a\},\{b\},\{c \}\} \{\{a\} ,\{b,c\}\}$etc... No. ... 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 ... 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 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 ... 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 ... 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 ... 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 ... 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 ... 1 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 ... 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 ... 0 Consider a Ferrer's diagram of n into at most r parts. ooooooo\\ oooooo\\ ooo\\ o For example this is a partition of 17 into 4 parts - 17=7+6+3+1. So in this example we know r\ge4. This means we can insert a first column of size exactly r to get a partition of n+r with exactly r parts. We also need to establish a bijection, and we can ... 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 ... 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 ... 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} ... 0 Here is a different approach to the problem than my other answer, which tries to set up a recurrence relation directly instead of passing through unordered partitions and young diagrams. The trick is to subdivide the set of solutions into pieces that can be better analyzed. To that end, let us define several functions. Let f(m,n) be the number of ... 0 Here is a sketch for how to solve the problem. It is not complete, and yields a solution only in terms of the number of partitions into at most a fixed number of parts, but it gives at least one useful way to think about the problem. If we denote the number in question by f(m,n), then f(m,n)/n! is the number of partitions of n into m+2 ... 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 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 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). 0 This is the number of permutations of 18 elements, divided 6 times by the number of permutations of 3 elements. 0 Their union is$\mathbb{Z}$as every consecutive point in$\mathbb Z_j$for some$j$belonging to$(0,1,...,m-1)$is equispaced with a distance$m$, so each$\mathbb Z_j$completes$1/m$th of the$\mathbb Z$by its$m$spaced motion along the real line and as they are non intersecting so their union completes$m$times$1/m$th of$\mathbb Z$, i.e. the whole ... 0 Why don't you think it's not a partition? It's clear that the union is a subset of$\mathbb Z$, so the only way it would not become$\mathbb Z$is that there's an integer not in the union. So assume that$z\in \mathbb Z$, then by Euclid division you have$z = qm + r$where$0\le r< m$. Therefore$z\in \mathbb Z_r$and therefore in the union. Note that ... 3 The Euclidean Division Theorem: Given two integers$a$and$b$, with$b ≠ 0$, there exist unique integers$q$and$r$such that $$a = bq + r$$ and $$0 ≤ r < |b|,$$ where$|b|$denotes the absolute value of$b$. So given a integer$a$, there exist a$r$such that$a = mq + r$with$0 ≤ r < |b|$. By the definition of$Z_i$,$i=0,\dots,m-1$, ... 1 Hint. The relation$a=b \mod m$is an equivalence relation and$\mathbb{Z}_i, i=0 \ldots m-1 $are the equivalence classes with respect to the relations. Then use a theorem that the set of all equivalence classes form a partition of the set$\mathbb{Z}.$0 Condition (b) is also satisfied, since any integer has a remainder in$\;\{0,1,\dots, m-1\}\;$by the Euclidean division theorem. 5 From Wikipedia: The sets in P are called the blocks, parts or cells of the partition. Regarding your question, though, I'd rather call$\{1,3\}\$ a 'set in the partition' or 'element of the partition' than a 'set of the partition,' but that's just a personal preference.

Top 50 recent answers are included