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
3answers
25 views

Combinatorics Question (discrete math)

In how many ways can one mark 6 blocks on a grid of 5 columns and 3 rows such that in every row at least one block will be marked? an explanation will be appreciated! Thx a lot
1
vote
1answer
20 views

Proof regarding notations

I tried to solve the following question: Let $f,g$ be non-negative functions such that $f(n)=g(n)\left[1+o(1)\right]$. Prove that $f(n)=\Theta(g(n))$. I looked on two cases: ...
1
vote
2answers
19 views

Deciding $\displaystyle o,\omega,\Theta$ notations

I have a question which I couldn't solve for about two hours. It goes like this: Let $\displaystyle f(n)=\left(\frac{n+3\ln(n)}{n}\right)^n \ ; \ g(n)=27^{\ln(n)}$. Fill the blank box with ...
-1
votes
0answers
18 views

If $k, m, n$, are natural numbers and $k \leq n$ What is the final answer of this :

If $k, m, n$, are natural numbers and $k \leq n$ What is the final answer of this: $$\sum_{r=0}^{m}\frac{k\binom{m}{r}\binom{n}{k}}{(r+k)\binom{m+n}{r+k}}$$
1
vote
1answer
14 views

Generalized Dyck words with alphabet of size $k$

It is known (e.g., here) that the Catalan number $C_n$ is the number of Dyck words of length $2n$, where a Dyck word is a string consisting of $n$ $X$'s and $n$ $Y$'s such that no initial segment of ...
0
votes
2answers
31 views

Binomial-coefficients if, k, m, n natural numbers and k \leq n the result of

If $k, m, n$, are natural numbers and $k \leq n$ What is: $$\sum_{r=0}^{m}\frac{k\binom{m}{r}\binom{n}{k}}{(r+k)\binom{m+n}{r+k}}$$
0
votes
2answers
15 views

combinations which way way is correct?

The problem How many ways are there to select 5 persons: 2 men and 2 women from a group of 20 people: 12 men and 8 women. So far I've found 2 solutions: We select 3 men and 2 women or 2 men ...
-3
votes
0answers
16 views

circles and points on a grid [on hold]

An infinite number of points are marked on the coordinate grid such that there is no circle that passes by 1000 of them. Is there necessarily a circle of radius 20 that does not contain any of those ...
0
votes
1answer
27 views

Miklos Schweitzer 2014 - sum of reciprocal of lengths of intervals

We let there be $k$ intervals within $[0,1]$. Prove that the sum of the reciprocals of the lengths of the intervals plus twice the sum of the reciprocals of the lengths of the nonempty intersection of ...
2
votes
2answers
36 views

If given $\sum_{r=1}^{m-1}\binom r3$, how does the summation evaluate when $n<r$ in $\binom nr$?

Correct me if I'm running the summation correctly - $$\sum_{r=1}^{m-1}\binom r3=\binom 13+\sum_{r=2}^{m-1}\binom r3$$ $$\sum_{r=1}^{m-1}\binom r3=\binom 13+\binom 23+\sum_{r=3}^{m-1}\binom r3$$ ...
4
votes
2answers
25 views

Number of teams and matches

This question has two parts. Given n players, how many different teams can be created with at least one and at most n-1 players? For example, given the four players A, B, C, and D, the following ...
2
votes
1answer
29 views

Combinatorics calc

I'm trying to make an application that's based on bets system. Until now i was able to calc the number of combination of the inserted events, in particular, i've used this formula: ...
2
votes
1answer
46 views

Calculating sum of all permutations

Given a number n. If we generate all the permutation from 1 to n, for a permutation $P_i, F(P_i)$ is defined as $\sum(|P_i - i|)$ for i = 1 to n. So if n = 3, for the permutation 1 3 2 F = |1-1| + ...
0
votes
1answer
33 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 ...
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 ...
3
votes
1answer
45 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 ...
1
vote
1answer
35 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 ...
2
votes
1answer
51 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 ...
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} = ...
2
votes
1answer
34 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 ...
1
vote
2answers
26 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. ...
1
vote
0answers
41 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 ...
6
votes
0answers
51 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 ...
2
votes
2answers
31 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
27 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 ...
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
0answers
37 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. ...
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 ...
1
vote
1answer
53 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
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
3answers
37 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 ...
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? ...
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 ...
-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 ...
0
votes
0answers
43 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
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 ...
-10
votes
0answers
34 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?$
3
votes
3answers
53 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 ...
0
votes
0answers
43 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
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 ...
0
votes
0answers
81 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 ...
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
3answers
56 views

How many ways to make a connected graph using 4, 5, 6 edges?

How can/how many ways can you make a connected graph that has 5 vertices using 4, 5, 6 edges? I'm not sure how it would look like for 4 edges. Can you draw a diagram?
1
vote
0answers
17 views

Inequality to bound $\sum_i a_i b_i - \sum_i c_i d_i$ (harmonic eigenfunction/graph) type sum with constraints

We have a homogeneous graph $G = (V,E)$ with a function $f:V\rightarrow \mathbb{R}$. We define the following modulus: $\displaystyle \omega(s) = \sup\{f(x)-f(y) \ | \ |x-y|=s \}$ and wish to lower ...
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 ...
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 ...