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)

2
votes
1answer
131 views

A combinatorial identity: $ \sum_{k=m}^n \frac{\binom{1/2}{k-m}}{k \binom{-1/2}{k}}=\frac{\binom{-1/2}{n-m}}{m \binom{-1/2}{n}} $

Let $m,n$ be two positive integer, $n>m$. I have trouble proving that $$ \sum_{k=m}^n \frac{\binom{1/2}{k-m}}{k \binom{-1/2}{k}}=\frac{\binom{-1/2}{n-m}}{m \binom{-1/2}{n}} $$ Any suggestions, ...
0
votes
1answer
54 views

Labeling edges of a cube with + and - so each face has an odd number of +s.

I am looking for a specific proof, using tools from cellular homology, of the following theorem. Let $I^n$ be the standard $n$-dimensional hypercube with its standard cellular structure. There ...
0
votes
1answer
36 views

Finding the Probability of a Probability Using binomial

The exercise goes like this: Let $X$ be $Bin(n,p)$ where $n=10$ and $p$ can be either $1/4$ or $3/4$, where both possibilities of $p$ are equally likely. It is known that $X=7$. What is the ...
-1
votes
1answer
84 views

How many options are there for dividing 200 pennies into 3 bags?

Ill be glad if you could help me solve this one. How many options are there for dividing same 200 pennies into 3 same bags? Thanks ahead.
2
votes
2answers
89 views

Can we get the line graph of the $3D$ cube as a Cayley graph?

Given a graph $G=(V,E)$, the line graph of $G$ is a graph $\Gamma$ whose vertices are $E$ (the edges of $G$) and in $\Gamma$, two vertices $e_1,e_2$ are connected if, as edges in $G$, they share an ...
3
votes
2answers
92 views

Arithmetical proof of $\cfrac{1}{a+b}\binom{a+b}{a}$ is an integer when $(a,b)=1$

When $(a,b)=1$, $\cfrac{1}{a+b}\binom{a+b}{a}$ refers to the number of paths from one corner to its opposite corner of an $a\times b$ lattice that lies completely above (or below) the diagonal. ...
3
votes
1answer
61 views

How many (linear) order types are there on a set of n elements?

Given number $n$ variables $a_1, a_2, \dots, a_n$. How many way can we place $>$, $=$ between them ? For example, for $n = 3$ (Let's call $a_1 = x, a_2=y, a_3=z$ for convenient). There are 13 way: ...
1
vote
6answers
768 views

Queens in the chess board

A curious question. a) How many different ways exists to put "n" queens on a chessboard and they all can't capture the others? b)If you put one queen in the chess board knowing that exist one other ...
0
votes
2answers
172 views

Combinatorics: several problems

I have several questions related to combinatorics. I am not a mathematician, and only understand the basics of $n \choose k$ (and commonly use Wolfram Alpha to solve such problems), maybe you can take ...
2
votes
1answer
81 views

Non 0-1 integer programming

Many interesting combinatorial problems - graph coloring, maximal matching, set cover, and knapsack among others - can be reformulated as integer linear programs. One thing that all of these ...
1
vote
1answer
90 views

Counting number of group homomorphism

Let $G$ be a group. Show that $$\# \text{hom}(\mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/2\mathbb{Z}, G)=\# \{f:\mathbb{Z}\times\mathbb{Z}\to G\mid f\; \text{is a homomorphism},2\mathbb{Z}\times ...
0
votes
3answers
123 views

Mathematics Combinatorics

If I have 10 BALLS and 3 boxes, how many possible number of solutions are there with a maximum number of 9 and minimum number of 1? numbers cannot be repeated. Mathematically, we are finding the ...
0
votes
2answers
51 views

discrete math question for ratio

From n men and n women one wants to select k male and k female candidates, to create either a committee or a ballot. In a ballot the members are fully ranked (first, second, ...); in a committee they ...
3
votes
2answers
948 views

How many positive integers N are there such that the least common multiple of N and 1000 is 1000?

How many positive integers N are there such that the least common multiple of N and 1000 is 1000? I did found the solution to this problem , but I did it by brute force. When I was tackling ...
1
vote
2answers
164 views

Four-letter strings from the set $S = \{A, B, C, D, D, D, E, E, F, G\}$ with a few conditions

Consider the set $S = \{A, B, C, D, D, D, E, E, F, G\}$. How many different four-letter strings can be built using elements of $S$ such that no two adjacent letters in the string are the same ...
1
vote
0answers
115 views

Expansion of subsets of a hamming ball in hypercube

Consider a hypercube graph $G_n = (V,E)$ in n dimensions. Let $H_{1/2} \subset V$ be the set which represents the hamming ball of radius $n/2$. That is for every $v \in H_{1/2}$ the hamming weight of ...
9
votes
4answers
169 views

Number of strings of length n formed by $\{0,1,2\}$ such that $1$ and $2$ do not occur successively.

What is the number of ways of forming a string of length $n$ from the set $\{0,1,2\}$ such that $1$ and $2$ do not occur successively.
1
vote
2answers
76 views

Single error correcting binary code of length $16$ and size $2^{12}$

Consider there is a 12 bit data, and we want to add 4 check bits, such that 1-bit errors can be detected and corrected. How can this be done ? Consider the data as : b15 b14 b13 b12 b11 b10 b09 b08 ...
11
votes
1answer
219 views

What's the name of this quantity?

For each permutation $\sigma$ of $ \left\{ 1, 2, \dots, n \right\}$ define $$\operatorname{dist}(\sigma)=\sum_{i=1}^{n}\left| \sigma (i)-i \right|$$ For each $n\in\mathbb{N}$, I'm interested in ...
1
vote
4answers
91 views

N is a natural number N>1, and K is a natural number between 1 and N. In how many permutations of numbers 1 to N …

N is a natural number N>1, and K is a natural number between 1 and N. In how many permutations of numbers 1 to N the number K is smaller then all the numbers on his right? The answer says: ...
14
votes
3answers
311 views

On a Putnam's 2009 problem [duplicate]

Find all even natural numbers $n$ such that the following is true: There is a non-constant function $f : \Bbb{R}^2 \longrightarrow \Bbb{Z}_2$ such that for any regular $n$-gon $A_1...A_n$, $f(A_1) + ...
4
votes
1answer
262 views

Periodic (-1,0,1) matrices of two types

similar question: http://mathoverflow.net/questions/9547/how-to-construct-matrices-with-periodicity Definition: a (-1,0,1) matrix is a matrix with entries either -1, 0 or 1. I am trying to understand ...
0
votes
1answer
86 views

Rigorous proof: Combinatorics problem - The number of ways to arrange $n$ objects, $n_1$ being of one kind,…, $n_r$ being of an rth kind.

Reading in a book on the subject Mathematical Statistics I came across this theorem, whcih is in the section of Combinatorics. The number of ways to arrange $n$ objects, $n_1$ being of one kind, ...
0
votes
2answers
192 views

For positive integer N the numbers 1,2,3,…,2N are arranged in two adjacent column. In how many ways they can be arranged that:

For positive integer N the numbers 1,2,3,...,2N are arranged in two adjacent column. In how many ways they can be arranged so that: The numbers in each row arranged from smaller to bigger (from left ...
1
vote
1answer
68 views

6 people into 3 rooms - Combinatorics

There are $3$ different rooms and $6$ people. How many different ways are there to put the $6$ people into the $3$ rooms if each room has to have at least $1$ person? I am not sure I am right. I ...
2
votes
1answer
143 views

Burnside's lemma: 30 possible different dice

I have been working with Burnside's counting lemma and I came across the problem to show that there are 30 possible different dice. I have tried working with the 24 rotational symmetries of the cube ...
5
votes
2answers
204 views

Counting non-isomorphic relations

On a set $X$ of $n$ elements, how many non-isomorphic relations are there? The number of relations on a set of $n$ elements is $|\mathcal{P}(X \times X)|=2^{n^2}$, but is there any way to give a ...
0
votes
2answers
74 views

Estimating odds of random sequence recurring — very big numbers

I have two related questions. I'm trying to calculate the odds that at least one sequence of 30 characters (a "30-mer") will recur within a random sequence of one billion characters, drawn from an ...
6
votes
2answers
869 views

What is the total number of distinct sums possible from tossing six, six-sided dice?

I was reading The Ascent of Money by Niall Ferguson, and he writes "... he [John Law] wagered 10,000 to 1 that a friend could not throw a designated number with six dice at one throw. (He probably ...
3
votes
1answer
96 views

Worpitzky numbers as coefficients in summation formulae

The following exercise problem appears in Rozanov's Probability Theory: A Concise Course: Balls are drawn from an urn containing $w$ white balls and $b$ black balls until a white ball appears. ...
1
vote
1answer
244 views

Devise recurrence formula for restricted strings over alphabet $\left\{0,1,2\right\}$.

Let $A_n$ denote set of strings over characters $\left\{0,1,2\right\}$ of length $n$ which do not contain substring $22$. Moreover let $B_n$ denote set of strings which both do not contain ...
0
votes
1answer
102 views

How many words can you make with {1,2,3,4} such that difference between 2 letters is 1

Hello and happy new year. I've been struggling with this question and I really need some help. The question is, find a recurrence relation that demonstrates how many words of length $n$ can we write ...
1
vote
2answers
87 views

Combinatorics Question: Alphabet of $16$ letters, $8$ slots, arbitrary blanks

If I have an alphabet of $16$ characters and $8$ slots that are filled with any combination of characters (no duplicates except blanks), how do I calculate the total number of combinations? Edit for ...
1
vote
0answers
103 views

Randomized packing of items

An adversary gives you a set of items whose total size is $x$ (he gets to choose how $x$ is distributed. e.g. there may be $k-1$ items of size $\frac{x}{k}$ and 2 items of size $\frac{x}{2k}$). The ...
4
votes
3answers
3k views

How many ways $12$ persons may be divided into three groups of $4$ persons each?

How many ways $12$ persons may be divided into three groups of $4$ persons each? I think the answer should be $\frac{12!}{(4!)^3}$ but the suggested correct answer is $5775$, could anybody ...
1
vote
2answers
668 views

What is the probability of having same cards given two decks?

A practical question. Given two decks of cards (52 cards) if i pick 15 cards randomly from one deck and then 5 cards from another deck, what is the probability that exactly 3 cards, between two picked ...
6
votes
1answer
263 views

How to simply show that there are “78 'strict ordinal' 2x2 game matrices”

In "Theory of Moves", Steven J. Brams analyses two-player games with two strategies per player, where each player can totally rank his payoffs, although payoffs need not be comparable among players. ...
12
votes
3answers
1k views

Nice application of the Cauchy?-Frobenius?-Burnside?-Pólya? formula

Burnside's Lemma, whose list of names is longer than the proof, says that the number of orbits of a permutation group is the average number of fixed points of its elements. It's a very elegant result, ...
22
votes
2answers
739 views

Permutations with restriction

We have $n$ types of objects, and the number of objects of type $i$ is $a_i$, $1\leq i\leq n$. What is the number of permutation of the $\sum_{i=1}^n a_i$ objects, if no two objects of the same type ...
0
votes
1answer
61 views

Probability of a hand containing more clubs than spades in an incomplete deck

The problem: A deck is missing a number of cards. It has S spades, C clubs, and E red cards, for a total of M cards. A side point is that C = S + 1. A hand of N cards is dealt. A) What is the ...
1
vote
2answers
432 views

Number of ways in which a composite number can be resolved into 2 coprimes? [duplicate]

for example 210 = 2*3*5*7,number of relative primes is 2*(4-1) =8,please help me derive this result.here's my try = 4C0+4C1+4C2+4C3+4C4=2*4 .Since nCr = nCn-r we decide this by two.4C0 couples with ...
4
votes
1answer
90 views

Set of integers with a particular additive property

I have a set of integers $S = \{a_1,a_2,\ldots,a_n\}$. Let $K = a_1+a_2+\ldots+a_n$. Consider the space of all $n$-tuples whose values are taken from the set $S$. For example $(a_1,a_2,\ldots,a_n)$ ...
1
vote
0answers
316 views

Permutation for arranging letters in such a way that no similar letters come together (except SPACE)

I would like to get a general expression for arranging n letters such that any similar letters in them never come together (except SPACE). For example : Lets take AABBCCC and three ...
1
vote
2answers
136 views

How many ways to $22$ balls in $5$ boxes problem

How many ways are there to put $22$ identical balls into $5$ boxes, with each box has at least $2$ balls? The answer is $16$ choose $4$, i.e., $_{16}C_4$, but can someone explain it to me?
2
votes
2answers
133 views

When does the series $\sum_{n=1}^\infty \frac 1{nf(n)}$ converges?

Let $f : \Bbb{N}\longrightarrow \Bbb{N}$ be a function. a. Suppose $M$ is fixed and for any $n$, $|f^{-1}(\{n\})| < M$. Show that $\sum_{n=1}^\infty \frac 1{nf(n)}$ is convergent. b. Suppose ...
3
votes
4answers
119 views

A team of 4 students is to be selected from 12 students with conditions

conditions- two particular students refuse to be together. other two students wish to be together only. Approach-total number of ways to form team without any restrictions is $$\binom{12}{4}$$. Now ...
8
votes
1answer
295 views

Under what conditions does the n-dimensional, infinite, unit-square-grid graph contain a Hamiltonian ray?

I am no graph-theory expert, but I've been thinking about this problem for a long time. Let $G_n$ be the $n$-dimensional, infinite, unit-square-grid graph, i.e. the graph whose vertices are the ...
3
votes
2answers
1k views

How many unique Hamming (7,4,3) Codes are there?

I cannot find an answer to this on Google so I thought I would ask here. By unique I mean "distinct sets of codewords." By my count, there are $7!$ ways to choose an ordering of message bits and ...
1
vote
1answer
120 views

Number of non-equivalent necklaces

A necklace is made up of 12 beads in a circular loop. 3 are green and 9 are yellow. How many non-equivalent necklaces can be made? I have to use Burnside's Counting Lemma in this question.
2
votes
3answers
110 views

How to find coefficient of $x^8$ in $\frac{1}{(x+3)(x-2)^2}$

Using which way can we find coefficient of $x^8$ in $\frac{1}{(x+3)(x-2)^2}$? I have used binomial theorem but failed to find an answer for it.