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)

1
vote
2answers
24 views

Number of edges Upper Bound

Given a simple graph with $n$ vertices and $m$ edges, then show: $m \le \binom{n}{2}$. Obviously the equality holds when the graph is complete, and if you have less edges, then the inequality would ...
2
votes
4answers
88 views

Probability that team $A$ has more points than team $B$

Seven teams play a soccer tournament in which each team plays every other team exactly once. No ties occur, each team has a $50\%$ chance of winning each game it plays, and the outcomes of the ...
0
votes
0answers
37 views

What will be Terms after repeating this step(Differentiation and multiplication) F times.

I was solving a probability problem and got stuck on the following situation, where each x_i is independent of others: $$f=(x_1+x_2+..x_k)^N$$ I'm interested in the expression obtained after ...
2
votes
1answer
53 views

Finding the number of ways to pick ${n}$ marbles from a jar

Problem: А jar contains 8 blue marbles, 6 green marbles, and 4 red marbles. Five marbles are selected at random, all at once. In how many ways can: A.) two red and three blue marbles be obtained? ...
7
votes
0answers
80 views

A matrix with a dense submatrix - application of Chernoff’s Inequality

I am trying to solve an exercise from this book, which I will post here for convenience. I have a bit of a problem understanding how the hint of using Chernoff's bound implies the claim. Specifically ...
2
votes
0answers
22 views

Prove for $ \forall n \in \mathbb{N}, \exists x,y,z$ ( $0 \leq x < y < z$ ) such that $ n = \binom{x}{1} + \binom{y}{2} + \binom{z}{3}$ [duplicate]

I'm trying to solve a problem from the combinatorics book. Prove or disprove for $ \forall n \in \mathbb{N}, \exists x,y,z \in \mathbb{N} $ ($0 \leq x < y < z$) such that $$ n = \binom{x}{1} + ...
7
votes
1answer
81 views

Is the set $\phi(\mathbb{N})$ syndetic?

A set $A \subset \mathbb{N}$ is said to be syndetic if the gaps in $A$ are bounded. Is the set $\phi(\mathbb{N})$ syndetic? (where $\phi$ denotes de Euler totient function) I've thought quite a ...
1
vote
1answer
33 views

Finding the number of combinations

A teacher distributes 7 books to 7 children (each student a books), on the next day she collects the books back and redistributes in such a way that each students get a new book. In how many ways can ...
2
votes
2answers
85 views

Verify input is the sum of other numbers

I have a relationship: 4000k + 2500j + 400g = n, k >= 0, 0 <= j <= k, 0 <= g <= j I have to, given n, verify ...
9
votes
0answers
165 views

Maximum integer not in $\{ ax+by : \gcd(a,b) = 1 \land a,b \ge 0 \}$

Ryan asked about a variation of the coin problem, which was whether for any coprime natural numbers $x,y$ every sufficiently large natural number is $ax+by$ for some coprime natural numbers $a,b$. ...
2
votes
1answer
57 views

Combinatorics: How many ways are there to distribute zero to thirteen distinct cards to four distinct players?

Other ways to word the question so that it's clear: In a game where players hold a maximum of thirteen cards and a minimum of zero cards, how many possible positions are there? How many possible ...
16
votes
1answer
340 views

On the inequality $\frac{1+p(1)+p(2) + \dots + p(n-1)}{p(n)} \leq \sqrt {2n}.$

For all positive integers $n$, $p(n)$ is the number of partitions of $n$ as the sum of positive integers (the partition numbers); e.g. $p(4)=5$ since $4=1+1+1+1=1+1+2=1+3=2+2=4.$ Prove ...
3
votes
1answer
64 views

Let n and k be integers such that $n > k ≥ 0$. Show that ${n\choose k }$+ ${n\choose k + 1 }$ = ${n + 1\choose k + 1 }$

I'm trying to prove it using algebra and it didn't get very far. Here is how far I got. Now I know ${n\choose k } = \frac{n!}{k!(n-k)!}$ So the entire expression would be $$\frac{n!}{k!(n-k)!} + ...
2
votes
0answers
35 views

Limit probability of winning a card game [duplicate]

As mentioned in this question, the probability of winning, with an $n$-card per $k$ suit deck, a counting-up match card game (where you count through each of $n$ cards in order $k$ times and lose if ...
1
vote
1answer
35 views

Ways to place tiles on an $8\times8$ board.

How many ways are there to place, in an 8x8 board, 6 red tiles where they can't be in the same row or column, and 5 different coloured tiles (not red), which must all be in the same row. Attempt: ...
2
votes
0answers
87 views

Expected Power Product of rolling a dice .

A 15 sided dice is rolled 1000 times. Let k1,k2,k3,k4,..k15 denote the number of times 1,2,3...15 appears. How can I compute the following expected value :$$E( (k_1 k_2 k_3 k_4)^5).$$ My attempts:: ...
0
votes
1answer
22 views

How-many-different-adjacency-matrix-with-N-vertices-and-E-edges-have?

i'm studing graphs in algorithm and complexity and was perplexed in front of the following questions. I hope I get clear explanation for it... ...
3
votes
2answers
45 views

Finding the number of ways of picking three cards

Problem: An urn has 10 red cards numbered 1 through 10 and 8 blue cards numbered 1 through 8. Three cards are randomly drawn, one at a time, without replacement. Find the number of ways to ...
3
votes
5answers
63 views

Find ${n\choose0} + 2{n\choose1}+ 2^2{n\choose2}+…+2^n{n\choose n} = \sum_{k=0}^{n}{n\choose k}2^k$

Find ${n\choose0} + 2{n\choose1}+ 2^2{n\choose2}+...+2^n{n\choose n} = \sum_{k=0}^{n}{n\choose k}2^k$ Calculating the first couple of sums it seems that the answer is $3^n$, but I am having ...
3
votes
2answers
61 views

Finding how many bits of length n there are

So we are starting on the section of combinatorics in my discrete math class and our instructor gave us a simple problem to see if we understood what we learned that day. The problem consists of three ...
3
votes
2answers
151 views

IMO 1995 Shortlist problem C5

IMO 1995 Shortlist problem C5 At a meeting of $12k$ people, each person exchanged greetings with exactly $3k+6$ people. For any two people, the number who exchange greetings with both is ...
0
votes
0answers
28 views

Need recommendation for following topics in combinatorics

I have to do following topics for my exam .I have 2 months time .However i have never done any combinatorics except that of high school (Permutations ,Combinations etc ) .I want a book which covers ...
1
vote
0answers
65 views

Stirling number Combinatorics. Summation .

$$ \sum_{k=0}^n \left\{ {n\atop k} \right\} *(x)_k = x^n $$ is well known . What if the k-th term of LHS summation is divided by $q^k$ where $q$ is some positive constant, What about $$ ...
1
vote
1answer
37 views

how to calculate the number of less comparisons in this algorithm

I have this algorithm The teacher asked us what is the number of the less that compare : He said that the number is: I am trying to find out how did he know that, I did this 1- The ...
0
votes
2answers
45 views

question based on probability/permutation/combination

In a box containing $15$ apples, $6$ apples are rotten. Each day one apple is taken out from the box. What is the probability that after four days there are exactly $8$ apples in the box that are not ...
1
vote
1answer
30 views

Proving a combinatorial identity?

Let $n=2k$ if $n$ is even, and $n=2k+1$ if $n$ is odd, where $n \in \mathbb{N}$. Then prove: $$\sum\limits_{i=0}^k \binom{n}{2i}2^{n-2i}=\frac{3^n++1}{2}$$ I know that the binomial expansion of ...
1
vote
2answers
35 views

Generate all multisets of length k for n symbols [duplicate]

I am trying to generate a list of all multisets of length $k$ in a set with $n$ symbols. For example, if I had the set $S = {A, B, C}$ I would expect the following output for $k = 2$ and $n = 3$: ...
1
vote
1answer
32 views

Nearly-unit-distance graph (UDG) density

Q1. How dense can a nearly-unit-distance graph be? Let points sit in $\mathbb{R}^2$. A unit-distance graph UDG "connect[s] two points by an edge whenever the distance between the two points is ...
6
votes
0answers
104 views

Balanced, center-free set. [closed]

We say that a finite set $\mathcal{S}$ of points in the plane is balanced if, for any two different points $A$ and $B$ in $\mathcal{S}$, there is a point $C$ in $\mathcal{S}$ such that $AC=BC$. We say ...
0
votes
1answer
84 views

Why don't by multiply by $\binom{n}{k}$ here?

A while ago, I asked why we multiply by $\binom{n}{k}$. Take this question: At a soccer match there are 230 all-stars and 220 half-stars. You pick five people from the crowd. What is the ...
1
vote
2answers
47 views

Unique combinations of 7 items (repetition allowed, order doesn't matter)

I am trying to calculate the number of unique combinations for a 7 element set with repetition allowed where order doesn't matter. For example: ...
0
votes
2answers
32 views

Unique combinations from 7 items where repetition is allowed, and order doesn't matter

I am trying to calculate the number of unique combinations from a 7-element set where repetition is allowed and order doesn't matter. For example: Suppose $S = \{a, b, c, d, e, f, g\}$, and I want 3 ...
3
votes
1answer
55 views

finding the partial bell polynomial of $e^x$

$$ \left(e^{x+z} - e^x\right) = \sum_{n=1}^\infty \frac{z^n}{n!} \frac{d^n}{dx^n}[e^x] $$ $$ \left(e^{x+z}-e^x\right)^k = \sum_{n \geq k} Y^{\Delta}_{e^x}(n,k,x)z^n $$ Where: $$ Y^{\Delta}(n,k,x) = ...
3
votes
3answers
73 views

Arrangements of Chairs in a Circle

Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least three adjacent chairs. Hints only please! This is a confusing worded-problem. We ...
2
votes
1answer
52 views

Formula to find possible number of combinations

A committee of 5 is to be selected from a group of 6 men and 9 women. If the selection is made randomly, what is the probability that the committee consists of 3 men and 2 women. We can solve ...
-2
votes
4answers
64 views

How many arrangements exist (a + b + c = 4) [duplicate]

For example, $a + b + c = 4$ Solving this using stars and bars You have $4$ stars and $2$ bars: $$ x | x | xx$$ For example. Then what does $\binom{6}{2}$ mean? The number of arrangements ...
0
votes
1answer
27 views

Calculating the number of all possible connected regions on a discrete grid

Given an $N \times M$ grid. How would one calculate the number of possible connected regions of that grid? A connected region is a set of cells in this grid such that there is a path from any cell ...
3
votes
1answer
32 views

Permutations of n objects taken r at a time ( r=1 to r=n ) where objects may be groups of same entities and it's sum

I'm given n objects where n1 objects are the same ,along with another group of n2 objects of same element etc.. such that Σni = n (i=1 to k). Assuming there are k groups of similar objects eg: in ...
4
votes
2answers
47 views

Prove that $x\ge n(n-1)(n-3)/8$, where $x$ is the number of $C_4$ cycles in a graph.

If there are no $C_4$ cycles in a graph the edges in $G$, ie, $e(G)\le\frac n4(\sqrt{4n-3}+1)$, but if $e(G)\ge\frac12 {n \choose 2}$, we have to show that $x$ (number of $c_4$ cycles) $\ge ...
4
votes
1answer
40 views

How many matches are played?

A tennis club has $10$ couples as members. They meet to organize a mixed double match. If each wife refuses to partner as well as oppose her husband in the match, then in how many different ways ...
0
votes
0answers
33 views

A complicated summation of binomial coefficients

I am trying to evaluate this sum. I think closed form of this sum is not possible, but there might be some bound or approximate result. So far I was unable to find any approximation. Any help will be ...
0
votes
2answers
53 views

Proof Question regarding product sum and series

The question is let $\{m_1, m_2, m_3, \dots \}$ be a sequence of numbers where $m_k\geq 0$ for every $k \geq 1$. Let $$M_n = \sum_{k=1}^n m_k $$ when $n \geq 1$ is an integer. Show that if ...
4
votes
6answers
90 views

Show that if n+1 integers are choosen from set $\{1,2,3,…,2n\}$ ,then there are always two which differ by 1

Considering n=5 i have $\{1,2,3,...,10\}$ .Making pairs such as $\{1,2\}$ ,$\{2,3\}$ ... total of $9$ pairs which are my holes and $6$ numbers are to be choosen which are pigeons .So one hole must ...
2
votes
3answers
42 views

Permutations without repetitions (exclude repeated permutations) [duplicate]

The formula to calculate all permutations without repetitions of the set {1,2,3} is $\dfrac{n!}{(n-r)!}$ But how to calculate it if the set (or rather array in programming terms) includes repeated ...
2
votes
1answer
26 views

Number of subsets of $[n]$ with $k$ runs

This is an exercise from Douglas West's course on combinatorics. Given a set $S \subseteq [n] = \{1, 2, \ldots, n\}$, a run in $S$ is a maximal subset of $S$ that contains only consecutive integers. ...
4
votes
1answer
75 views

Does Euler's $\phi$ function have the same value in arbitrarily large subsets of $\mathbb{N}$?

As my most recent question still does not have any answers and it appears to be a difficult problem, I propose the following problem (that seems easier), but which I still could not manage to solve: ...
1
vote
1answer
38 views

Are there different combinatorial species with the same symmetry type?

First off: for my purposes, let $\sf B$ be the category of finite sets with bijections, and ${\sf B}_n$ the subcategory of sets with cardinality $n$, and define a combinatorial species to be a functor ...
0
votes
1answer
41 views

“quasi-increasing” permutation of a number

Call a permutation $a_1,a_2,\ldots,a_n$ quasi-increasing if $a_k\le a_{k+1}+2$ for each $1\le k\le n-1$. For example, $54321$ and $14253$ are quasi-increasing permutations of the integers ...
1
vote
2answers
24 views

how many ways to arrange 10 players between 3 positions with at least two players in each position?

my thought is that you would do 10 choose 6 to decide the 6 players to split between the 3 groups, then 6 choose 2 times 4 choose 2 times 2 choose 2 divided by 3! to determine how to arrange the 6 and ...
1
vote
1answer
21 views

characterize convergent sequences

Suppose that there is a strictly decreasing sequence $\{a_i\}$ such that $\sum_i a_i=1$. Given a rational number $r$ with $0<r<1$, is it possible to characterize for which subsets $A\subseteq ...