For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

0
votes
1answer
53 views

Dividing all permutations

Suppose you're trying to solve the Traveling Sales Person problem by going over all possible paths. To do so, you have a number of computers. Each gets $(n-1)!/p$ paths to scan, where $p$ is the ...
1
vote
1answer
93 views

Combinations of a jigsaw

I'm just asking myself of how many combinations you would have to go through to solve a jigsaw puzzle by "brute force" if you have $n = (p \times q)$ pieces. To simplify that, I assume that there are ...
5
votes
3answers
750 views

Compute probability of a particular ordering of normal random variables

There are $m$ normally distributed, independent random variables $N_1, \ldots, N_m$ with distinct means $\mu_1, \ldots \mu_m$ and standard deviations $\sigma_1, \ldots, \sigma_m$. Then, we get a ...
1
vote
1answer
230 views

the group of symmetries of the nodes of a cube

Can you explain me please how can I find rotation for a cube. I will attach an image: Thanks :)
1
vote
1answer
548 views

one application on Burnside's lemma

Using Burnside's Lemma find out: How many different necklaces having $5$ beads can be formed using $3$ different kinds of beads, if we discount : (a) Both flips and rotations? (b) Rotations only? ...
0
votes
1answer
530 views

Polya's formula for determining the number of six-sided dice

Use Polya's enumeration to determine the number of six-sided dice that can be manufactured if each of three different labels must be placed on two of the faces. Can you help me please to solve this ...
1
vote
0answers
149 views

Young tableaux: evaluate action of permutation

Consider the irreducible representation $V$ in the symmetric group $S_5$ corresponding to the Young diagram (these are meant to be boxes): $$[\;\;][\;\;] \\ [\;\;][\;\;] \\ [\;\;]\;\;\;\;$$ (a) List ...
0
votes
1answer
139 views

Examples of dictionaries between two distinct fields of mathematics (or between “differents” structures of math).

I'd like to meet explicit examples of dictionaries between two distinct fields of Mathematics (or between two "different" structures of Mathematics). I'm not interested in the usual sense dictionary ...
1
vote
1answer
93 views

Notation for multiplication of combinations of length $k$

Suppose we have list of $n$ integers $i_1,i_2,\ldots, i_n$ , and we choose $k$ integers from it in all possible combinations (i.e., $C^n_k$ combinations). Now for each combination, we multiply chosen ...
1
vote
0answers
98 views

Burnside's Lemma Triangle

I'm doing research into triangles and I was looking for the amount of possible triangles if 4 links are available between each point, without triangles which look the same if rotated. The 4 links ...
2
votes
0answers
25 views

Majorante functions of class $C^k$ to multinomial coeficientes.

Let's $k_1+\ldots +k_p=1$. What functions of class $c^k$ are upper bounds for multinomial coeficientes $$ \begin{pmatrix} n\\k_1,\ldots,k_p\end{pmatrix}=\frac{n}{k_1!\cdot k_2!\cdot\ldots\cdot k_p!} ...
2
votes
4answers
373 views

Shifting of index in power series

Suppose $$F(x)=\sum_{n \geq 0}{f_nx^n}=\frac{x}{1-3x}$$ We are asked to find an explicit formula for $f_n$. My working is , since$$\frac{1}{1-3x}=\sum_{n \geq 0}{3^nx^n} \\ \frac{x}{1-3x}=\sum_{n ...
2
votes
2answers
243 views

Prove coefficient of geometric series

Notice that the geometric series $$\sum_{n \geq 0}{x^n}=\frac{1}{1-x}, x \in (-1,1)$$ is a special case of the binomial theorem for real exponents, in which the binomial theorem for real exponenets is ...
1
vote
1answer
564 views

Puzzle of $N$ men around a table

This was asked to me by a friend. $N$ men sit around a circular table. Man 1 has a sword with him and he kills the Man 2, Man 3 picks up this sword and kills the next person i.e. Man 4. Thus the man ...
4
votes
3answers
444 views

Probabilities in choosing committees

I got stuck on this question while tutoring a Math 12 student : Q : There are 12 boys and 10 girls in a class. A yearbook committee of 4 is to be chosen at random. What is the probability (to the ...
3
votes
1answer
71 views

Simple Permutations and Combinations

I'm tutoring a math student and I'm having trouble with this question Q : A sub-committee of 7 members must be formed from 15 students. There are 9 male students and 6 female students. What is the ...
2
votes
2answers
226 views

A problem involving the lattice grid.

Suppose that $22$ points are arbitrarily chosen from a $7\times 7$ lattice grid. We are to prove that there exists at least one rectangle in any $4$ points chosen from the above $22$. A general ...
1
vote
1answer
134 views

Mathematical formula for permutation

I have been assigned to write mathematical equation for permutation using only 1,3,5,7,9 numbers starting from single digit going up to five digits numbers. For example Single digit 1 3 5 7 9 two ...
2
votes
4answers
283 views

Combinations of up to eleven letters

How many combinations of all sizes can be formed with the first 11 letters of the alphabet, a; b; c; d; e; f; g; h; i; j; k ? If for example abc is a solution then bac is not an additional solution. ...
0
votes
2answers
62 views

Maximum 2 apples

There are 10 types of fruits, of them 1 type is apples. You have to pick 4 of fruits, but max 2 apples. How many ways are there for you to pick fruits?
1
vote
1answer
155 views

The redundancy of Rubik's cube states [duplicate]

Possible Duplicate: Rubik’s Cube Not a Group? I take a Rubik's cube in the solved state, and I secretly assign a unique integer label to each of the cubies. I then, via an arbitrarily long ...
0
votes
2answers
199 views

The number of states in which $N$ binary strings with strictly adjacent $1$ bits have a specific number of strings with any $1$ bits

I have $N$ binary strings of length $L$. If a string has more than one $1$ bit, these bits must be adjacent to one-another. For example, for a length $L = 4$ string, the possible string states (of ...
4
votes
3answers
244 views

How come $\frac{n!}{n_1!\cdot n_2!\cdot…\cdot n_k!}$ is always an integer? [duplicate]

Possible Duplicate: Division of Factorials For a set of $n$ objects of which $n_1$ are alike and one of a kind, $n_2$ are alike and one of a kind, ... , $n_k$ are alike and one of a kind, ...
2
votes
1answer
1k views

game combinations of tic-tac-toe

How many combinations are possible in the game tic-tac-toe (Noughts and crosses)? So for example a game which looked like: ...
27
votes
1answer
2k views

Six Frogs - Puzzle (order reversal using special transpositions)

I had come across a puzzle: The six educated frogs in the illustration are trained to reverse their order, so that their numbers shall read 6, 5, 4, 3, 2, 1, with the blank square in its ...
3
votes
1answer
217 views

Table and dish rotation for monthly supper club

In each of four months (eg. Jan, Feb, Mar, April) four tables of four guests meet for a four course dinner. Rule 1: Each guest brings a different course each month and Rule 2: the guests NEVER dine ...
4
votes
1answer
247 views

Probability of a certain dice roll sum disregarding lowest rolls

The number of ways to obtain a total of $p$ in $n$ rolls of $s$-sided dice is: $$c=\sum_{k=0}^{\lfloor(p-n)/s\rfloor}(-1)^k\binom{n}k\binom{p-sk-1}{n-1}\;.$$ What I'm interested in is making the $n$ ...
0
votes
2answers
224 views

50 States w/2 senators each. Probablity of various committee compositions

From Carol Ash's, "Probability Tutoring Book". pg. 28 section 1-4, question 10. There are 50 states and 2 senators from each state. Find the prob that a committee of 15 senators contains: ...
4
votes
1answer
163 views

integer partitions and Faà di Bruno coefficients

I'm trying to check whether the following statement is true. Let $n$ be a non-negative integer and $p(n)$ the number of integer partitions of $n$. Is it true that \begin{equation} ...
3
votes
2answers
134 views

For a simple XML doc, how to find number of possible arrangements of elements (i.e open and close tags) when given maximum number of tags?

For a simple XML doc, how to find number of possible arrangements of elements (i.e open and close tags) when given maximum number of tags ? Let me rephrase the question by example, we have a set ...
5
votes
1answer
211 views

Algorithm creating subsets with certain properties

I'm trying so solve following problem: Let's say, we have a set $A=\{1,2,3,...,49\}$. Now, I am defining sets $A_1, A_2, A_3,...,A_n$ as follow: $A_1=\{a_1,a_2,a_3,...,a_{30}\}$, $A_2= ...
5
votes
1answer
321 views

Mutual set of representatives for left and right cosets: what about infinite groups?

Let $G$ be a group and $H$ a subgroup of $G$. If $G$ is finite, then according to Philip Hall's "marriage theorem" there is a left transversal $T$ of $H$ in $G$ (that is, $T$ contains precisely one ...
0
votes
1answer
349 views

Sum of consecutive sub-sequence of 100 natural numbers divides 100 (equals 0 mod 100) [duplicate]

Possible Duplicate: pigeonhole principle and division I need a little help in an exercise. Given 100 natural numbers $a_{1},..,a_{100}$ , prove that there is a consecutive sub-sequence ...
3
votes
2answers
88 views

Subsets with small interaction.

For a set $X$ of cardinality $N$: how can we find a set of subsets of $X$ of cardinality $C$ such that no two subsets have an intersection of more than $n$ elements? What is the largest cardinality of ...
1
vote
1answer
452 views

$n$ choose $k$ where $n$ is less than $k$

I am working on parameter estimation and one of the estimators involves a summation of $_nC_k$ ($n$ choose $k$) expressions. For some iterations, I need to compute expressions like $_0C_1$, $_0C_2$, ...
0
votes
0answers
79 views

Distribution of binary digits in moduli

Considering the (infinite) set of all positive integers that are a product of $2$ primes only, represented in binary $100...01$. Question: is the distribution of the proportion of $0,1$ digits ...
1
vote
2answers
120 views

Probability of a 12 symbol string containing 3 even digits

From Carol Ash's, "Probability Tutoring Book", pg. 19, prob. 1-3.4. If a 12 symbol string is formed from the 10 digits and 26 letters, repetition not allowed, what is the prob that it contains 3 ...
86
votes
1answer
2k views

Is there a characterization of groups with the property $\forall N\unlhd G,\:\exists H\leq G\text{ s.t. }H\cong G/N$?

A common mistake for beginning group theory students is the belief that a quotient of a group $G$ is necessarily isomorphic to a subgroup of $G$. Is there a characterization of the groups in which ...
2
votes
2answers
890 views

A difference between a roller coaster and a ferris wheel.

A roller coaster has five cars, each containing four seats, two in front and two in back. There are 20 people ready for a ride. In how many ways can the ride begin? What if a certain two people ...
2
votes
1answer
673 views

A classroom has two rows of eight seats…

A classroom has two rows of eight seats each. There are 14 students, 5 of who always sit in the front row and 4 of who always sit in the back row. In how many ways can the students be seated? ...
7
votes
0answers
208 views

Combinatorial Proofs of Real Analysis Identity

In this question,a proof using real analysis is given of the following identity: $$ \sum_{n=1}^{\infty} \frac{(n-1)!}{n \prod_{i=1}^{n} (a+i)} = \sum_{k=1}^{\infty} \frac{1}{(a+k)^2}$$ Is there a ...
3
votes
2answers
149 views

Math game, the least number of operations to get N from 0

We can add do the following operations a) add 1 to number b) multiply number by 2 By using only a) and b) operations we can get any number from 0. How much operations we need to do at least to get ...
4
votes
2answers
103 views

Equivalence of $x,y\in G$ given that $xzy^{-1}z^{-1}$ is a commutator for some $z$

Let $G = \langle a,b,c\:|\: a^2, b^2, c^2\rangle$. Let $\tilde{}$ by the equivalence relation on $G$ generated by conjugation and inversion (i.e., $x\tilde{} y$ if there is a finite sequence of ...
0
votes
2answers
416 views

How many solutions possible for the equation ${2x}+{3y}+{7z}={r}$

I want to solve this problem with generating function : How many solutions(non-negative) possible for the equation $${2x}+{3y}+{7z}={r}$$$(r \ge0)$ such that : 1)$x,y,z \ge0$ 2)$0 \le z\le 2 \le ...
1
vote
1answer
72 views

Using a certain theorem to calculate the number of ordered partitions of a set.

Consider the theorem Let $A_1,\ldots,A_n$ be $n$ sets of cardinalities $N_1\ldots,N_n$, and $S:=A_1\times \ldots\times A_n$. Then $|S|=N_1\cdot \ldots \cdot N_n$. How do I have to apply this ...
1
vote
1answer
699 views

Dependent Bernoulli trials

The probability of a sequence of n independent Bernoulli trials can be easily expressed as $$p(x_1,...,x_n|p_1,...,p_n)=\prod_{i=1}^np_i^{x_i}(1-p_i)^{1-x_i}$$ but what if the trials are not ...
4
votes
3answers
299 views

What is the next number of this sequence?

Consider the sequence $ (a_{n})_{n \in \mathbb{N}} $ of positive integers whose first few entries are $ 2 ~~ 6 ~~ 20 ~~ 70 ~~ 252 ~~ \ldots $ Now, consider the infinite matrix ...
3
votes
1answer
60 views

Enumerating simultaneous combinations in set

I have a group of 6 objects, that I want to put into 2 groups of 3. I know there are 20 combinations, but simultaneously there are only 10 combinations as the others are redundant. How do I ...
1
vote
3answers
88 views

Combinatorics alphabet

If say I want to arrange the letters of the alphabet a,b,c,d,e,f such that e and f cannot be next to each other. I would think the answer was $6\times4\times4\times3\times2$ as there are first 6 ...
1
vote
1answer
43 views

Using a certain theorem to calculate the number of stacks cards with the same color.

Consider the following theorem: Let $A$ be a set of size $n$. Then there are $\frac{n!}{k_{1}!\cdot\ldots\cdot k_{t}!}$ ways to partition this set into $t$ nonempty set of sizes $k_{i}$. And ...