This tag is for basic 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
39 views

Prove that a preorder is not anti symmetric

Let $\prec$ be a relation on the set $ A = Z \times (N \setminus \{0\}) $ in this way: A. $<a,b> \prec <c,d> $ if $ ad \le bc$ Prove that $\prec$ is a Preorder and show it's not ...
0
votes
1answer
19 views

What happens from $\displaystyle (1+(x+x^2))^n$ to $\displaystyle \sum_k {n \choose k} (x+x^2)^n$?

I'm reading Harris/Hirst/Mossinghoff's: Combinatorics and Graph Theory. I don't understand what happens from $\displaystyle \bbox[1px,border:1px solid black]{(1+(x+x^2))^n} $ to $\displaystyle ...
1
vote
1answer
29 views

Count and description of vertices of certain faces of the Tridiagonal Birkhoff polytope $\Omega^t_{d+k}$

For $k \ge 1$, $d \ge 2$ and $k \le d - 1$, let ${}^f_d\Omega^t_{d+k} (d;c_k(d - 1))$ be the intersection of $k - 1$ facets of the Tridiagonal Birkhoff polytope $\Omega^t_{d+k}$ with equations: ...
4
votes
0answers
46 views

Game to maintain distinct number of balls in glasses

There are $n$ glasses, containing $n+1,n+2,\ldots,2n$ balls, respectively. Two players $A$ and $B$ play a game, alternately taking turns with $A$ going first. In each move, the player must choose some ...
1
vote
0answers
33 views

Traveling salesman neighborhood

I am solving some TSP problems and i got this one and i am not pretty sure about my answer. By seeing TSP as a formal combinatorial problem, i have that the Feasible solutions $F$ is the set defined ...
3
votes
2answers
43 views

Minimum number of bags to buy to allocate equally

It is from a programming contest but I feel it pertains more to the mathematics realm ( I once asked it in stackoverflow but they closed the problem saying I should go here ) The problem goes like ...
2
votes
1answer
29 views

Adjacent dominos in a train

Definition of a domino -- a domino contains two squares separated by a line. In both of the squares, there are some numbers of dots (can be 0). Definition of "double-n" domino set: It contains one of ...
1
vote
1answer
54 views

Proof of the fact that the set of (p,q) shuffles is a cross section of the subgroup $S_p\times S_q$

Definition Let $G$ be a group and $H$ its subgroup. We name a subset $K$ of $G$ a cross section if it has exactly one element from each left coset of $G/H$. Definition Let $n=p+q$ for some ...
8
votes
2answers
246 views

Prove that for all non-negative integers $m,n$, $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is an integer.

Prove that for all non-negative integers $m,n$, $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is an integer. I'm not familiar to factorial and I don't have much idea, can someone show me how to prove this? ...
2
votes
0answers
26 views

Maximization problem related to set of common representatives

We are given set $\{1, \dots n\}$ and requested to construct $A = \{A_1 \dots A_s\}$, where $|A_i|=k$, $|A| = s$, $A_i \subset \{1, \dots n\}$. We say that $S$ is a minimal set of common ...
17
votes
1answer
205 views

Some four clubs have exactly $1$ student in common

There are $100$ students in a school, and they form $450$ clubs. Any two clubs have at least $3$ students in common, and any five clubs have no more than $1$ student in common. Must it be that some ...
0
votes
0answers
22 views

Expected number of matching “cards”. Why is $\sum_{m=0}^n D_{n,m} = \sum_{m=0}^n m \cdot D_{n,m}$?

Each of n ≥ 2 people puts his or her name on a slip of paper (no two have the same name). The slips of paper are shuffled in a hat, and then each person draws one (uni- formly at random at each ...
1
vote
2answers
24 views

Permutation/Combination question on dice

Question: Three dice (six faces: each face -> number 1 to 6) are rolled. What is the number of possible outcomes such that at least one die shows number 2? My attempt: One die has to show two. ...
2
votes
2answers
32 views

Number of Terms in a Polynomial (4th Degree)

Find the number of terms of $(x^3+5x^2-x+2)^4$, when like terms are added. My approach to this uses stars and bars to get $****|||$, since there are $4$ groups. $\binom{7}{3} = ...
5
votes
2answers
41 views

Distributing candies

Suppose ther are B boys and G girls in a classroom.Teacher wants to distribute candies among B boys and G girls such that: 1.Each student gets atleast one candy and atmost N candies. 2.sum of ...
2
votes
1answer
28 views

Set of common representatives and pigeonhole principle in one problem

We are given set $\{1, \dots n\}$ and $A = \{A_1 \dots A_s\}$ such as $|A_i|=k$, $|A| = s = \binom n k$, namely $A$ contists of all possible subsets of size $k$. We say that $S$ is a set of common ...
0
votes
2answers
25 views

Show that the number of subsets of $S_1 \cup \dots \cup S_t$ that contain at most one element from each $S_i$ is $(a_1 + 1)(a_2 + 1) \dots (a_t + 1)$.

I found this problems on Aigner's: A course in enumeration: 1.1 We are given $t$ disjoint sets $S_i$ with $|Si| = a_i$. Show that the number of subsets of $S_1 \cup \dots \cup S_t$ that contain ...
2
votes
2answers
29 views

Probability in dice, Feller exercise

I am stuck with exercise 2 of Chapter 4 Feller vol 1 "an introduction to probability theory and its application". Here I report the exercise text: Five dice are thrown. Find the probability that at ...
1
vote
1answer
51 views

How find the smallest $m$ such this $|A|=n,|B|=m,A\subseteq B$

Question: Let $n \geq 5$ be a positive integer and let $A$ and $B$ be sets of integers satisfying the following conditions: i) $|A| = n$, $|B| = m$ and $A$ is a subset of $B$ ii) For any ...
0
votes
0answers
17 views

Find a probability of $n$ event happening from $m$ types

The question is: to find a sum $$ S=\sum\limits_{n_1+n_2+\ldots+n_m = n,\ n_i=0,1,\ldots,n} p_1^{n_1}p_2^{n_2}\cdots p_m^{n_m}, $$ where $p_i\in[0,1]$. UPDATE. This issue has no probabalistic ...
0
votes
0answers
42 views

Put a set of triangles into proper mathematical equations / objects

I have a set of $n$ points $\{A_1,A_2,...,A_n\}$ of the plane. Three points $A$ should never form a line (so we can still draw a proper triangle). I draw every triangle formed with $3$ points $A$. I ...
1
vote
3answers
146 views

this is a conjecture or a result? every arithmetic progression contains a sequence of $k$ “consecutive” primes for possibly all natural numbers $k$?

Writing a little better the previous question: is it true that if we let $a$ and $b$ be coprime integers, then the arithmetic progression : $a + bh: h\in {\mathbb Z}$, contains a sequence of $k$ ...
18
votes
2answers
479 views

Maximizing curious symmetric function from simple combinatorics

A curious symmetric function crossed my way in some quantum mechanics calculations, and I'm interested its maximum value (for which I do have a conjecture). (This question has been posted at ...
-2
votes
0answers
36 views

Modifying recursion matching result

Let $f_0=\frac{1}{4}$ and $f_i=\dfrac{3f_{i-1}}{4}+\dfrac{2^{-i}}{2}$ and this gives $f_n>\frac{3^{n}}{4^{n+1}}$. This problem came as I was trying to solve a complexity theory problem. ...
1
vote
1answer
60 views

What is the probability of choosing r objects from c different groups when there are m groups of n objects?

Suppose I have m groups of n objects each for a total of nm objects. I am going to choose r of these nm objects. I want to know what the probability is that my r objects come from c different ...
0
votes
2answers
46 views

Exclusion-Inclusion principle.

I have this problem in discrete maths (combinatorics) which nags me. We have a computer system, where a password is of length of at least 3 signs and at most 100 signs. The premitted signs to use ...
5
votes
1answer
46 views

Erasing numbers from circle and writing down sum

There are $50$ copies of the number $1$, and $50$ copies of the number $-1$, written alternately in a circle. In each step, we pick an arbitrary number, write down the sum of the number and its two ...
-3
votes
1answer
358 views

Probability of a particular assignment out of all possible assignments. [on hold]

A group of $60$ second graders is to be randomly assigned to two classes of $30$ each. Five of the second graders, Marcelle, Sarah, Michelle, Katy, and Camerin, are close friends. What is the ...
2
votes
0answers
48 views

General solution for a combinatorial problem

I want to find a general solution for a problem. I explain the problem with an example. $\underline{Problem}:$We have a matrix $A$ of size $M \times N$, where $M <N$. We choose sub-matrices of ...
7
votes
2answers
118 views

Solving a circular permutation problem with recursion

N people are invited to a dinner party, and they are sitting at a round table. Each person is sitting on a chair; there are exactly N chairs. So each person has exactly two neighboring chairs, one on ...
2
votes
4answers
66 views

How to find the number of possible outcomes of 10 games between 20 teams?

Hi I am looking for an equation to find possible combinations in a non repeating format with a twist. Here is the example: There are 10 games between 20 teams. I have to chose 5 winners but ...
2
votes
3answers
36 views

Probability of winning a rigged coin-flipping game

Betsy and Katie are playing a game with an unfair coin. The coin is rigged to come up heads with probability $\frac35$ and tails with probability $\frac25$. Betsy goes first. The two take turns. The ...
15
votes
0answers
131 views
+50

An example where $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is the number of ways of counting something?

Prove that for all non-negative integers $m,n$, $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is an integer. There is a answer given here to this question here. I've seen how it can be proven using recurrence ...
3
votes
3answers
52 views

How many different (circular) garlands can be made using $3$ white flowers and $6m$ red flowers?

This is my first question here. I'm given $3$ white flowers and $6m$ red flowers, for some $m \in \mathbb{N}$. I want to make a circular garland using all of the flowers. Two garlands are considered ...
3
votes
1answer
48 views

Number of ways to arrange items

Given a list of $n$ distinct items, where a smaller item behind a larger item is obscured, if you can see $x$ items from one end, and $y$ from the other, how many ways can the items be arranged? ...
0
votes
1answer
32 views

The number of self-avoiding paths in the plane of length $k$

The number of self-avoiding paths in the plane of length $k$ is at most $4 \cdot 3^{k-1}$ according to this. Why? My immediate thought: four options for the first move and always three choices after ...
-1
votes
4answers
46 views

How many ways are there to prepare one of 400 varieties of coffee in one of 7 ways?

I'm hoping someone can check my thinking: I have 400 distinct varieties of coffee. Each can be prepared in 7 ways (black, cream and sugar, etc.). How many possible combinations are there? I'm thinking ...
5
votes
1answer
107 views

Set with distinct subset sums

The problem is as follows : Given a set A with distinct positive integer elements, prove that there always exists another set B consisting of positive integers, s.t., The size of B is less than or ...
1
vote
1answer
59 views

How to solve this kind of problem?

I've just found the following problem: $\quad\quad$ $\quad\quad$ $\quad\,$ And I believe that it could be done with something in combinatorics, my feeling is that generating functions would ...
7
votes
0answers
125 views

A curious identity of weighted sums over multi-set permutations.

Suppose we have $n$ balls which are the same except colors, denote $S$ to be the set of all different permutations of the balls.(i.e. the swap of two balls with the same color will be the same ...
-10
votes
0answers
33 views

Showing $M(n,k,q)=\sum_{i=0}^{q}(-1)^{q+i}\binom{q}{i}\begin{pmatrix}0&n\\k&i\end{pmatrix}$. [on hold]

How do I show $$M(n,k,q)=\sum_{i=0}^{q}(-1)^{q+i}\binom{q}{i}\begin{pmatrix}0&n\\k&i\end{pmatrix}$$ for $q>1?$
4
votes
4answers
527 views

Is it possible to permute an unknown binary sequence so that two particular bits are equal?

A blind mathematician is give a $2015$ bit sequence. The mathematician can take any two bits and switch them (so the bit in position $A$ goes to position $B$ and vice-versa). He knows at what position ...
0
votes
0answers
41 views

A combinatorial game theory problem

In details, Let, there are four bishops on a chessboard where every two bishops are in pair ( as there are 4 bishops that means 2 pairs and in each pair they sit in vicinal squares). How many ...
0
votes
1answer
51 views

Can this binomial summation be simplified?

I got something like $\displaystyle\sum_{i=0}^K{ \binom{n+i}{i} \cdot \alpha^i} $ where $n,\ K,\ \alpha$ are definite values, $\binom{n+i}{i}$ is the Combinatorial number that choose $i$ from ...
0
votes
0answers
80 views

Number of sequences of 0s and 1s of length N such that k consecutive 1s are present [on hold]

How many different sequences of $0$s and $1$s of length $N$ are possible such that at least $k$ consecutive $1$s are present in them where $k\leq N$ exactly $k$ consecutive $1$s are present in ...
-1
votes
1answer
36 views

All variants of stars and bars / balls and bins problem [on hold]

The Stars and Bars problem or Balls and Bins problem are the the very basic in combinatorics but at the same time are quite helpful for beginners. Can we have list of variants of these problems? Add ...
1
vote
1answer
26 views

Union of each family is not the whole set

Let $n\geq k>0$, and consider all $\binom{n}{k}$ subsets of $A=\{1,2,\ldots,n\}$ of size $k$. We want to partition it into families so that the union of each family is not equal to $A$. At least ...
2
votes
0answers
22 views

Concerning the summation of digits to square-free numbers

Consider an alphabet of $n+1$ letters: $\{0,...,n \}$. Let $z$ be a number in base $n+1$ such that it has at most $n$ digits (so the initial/first string of digits can be composed of $0$'s). Let ...
1
vote
1answer
28 views

Concerning the summation of digits in strings: how many strings have an even such sum?

This is a continuation of a previous question of mine Consider an alphabet of $n+1$ letters: $\{0,...,n \}$. Let $z$ be a number in base $n+1$ such that it has at most $n$ digits (so the ...
5
votes
1answer
55 views

Max flow min cut from duality

I have been having some trouble deriving the max flow min cut theorem from duality, which I was told is possible. To begin with, I need to cast the problem into the form "maximize $\langle c, ...