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
2answers
54 views

Ways to make change

Given unlimited coins with values $1^2$, $2^2$, $3^2$, $4^2$,..., $17^2$ Now given an amount X, in how many ways can we exchange it using these coins? Example for $X=24$ answer is $16$. It means ...
1
vote
1answer
43 views

TCP Connection, 6 Packets, Probability of certain arrival orders

So I have a very hard time with statistics and probability. This comes from not being able to extract what I need to do from the given information. I don't get why I can't solve such easy stuff... :( ...
3
votes
2answers
184 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 ...
1
vote
1answer
69 views

Graph where every vertex has degree 3, perfect matching?

Suppose $G$ is a graph where every vertex has degree $3$. There is no single edge which separates the graph. My question is, must $G$ necessarily have a perfect matching? I tried drawing some graphs ...
5
votes
4answers
198 views

Permutations containing a given subsequence

Let $f(n)$ denote the number of $4n$-long strings formed from $2n$ a's and $2n$ b's, such that the string contains, as a (possibly non-consecutive) subsequence, a pattern containing $n$ a's and $n$ ...
2
votes
2answers
82 views

Simplifying a Triple Summation

I have the summation: $$ \sum_{c=1}^{n-1} \sum_{k=c}^n \sum_j \frac{\rho(n,k)}{j!(k-c-j)!(c-j)!} $$ Where the sum $j$ goes from $0$ to $k-c$ if $k-c \leq c$, but if $k-c \geq c$ then the sum goes from ...
1
vote
1answer
75 views

“At least” type probability question.

Recently, I asked a question: Team A has more Points than team B Though I ultimately got the right answer, it took extreme casework, and long computations. My question is: suppose the question was ...
2
votes
4answers
111 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 ...
2
votes
0answers
58 views

Maximal determinant of a $\{1,−1\}$ matrix of size $n$ is $2^{n−1}$ times the maximal determinant of a $ \{0,1\}$ matrix of size $n−1$.

Maximal determinant of a $\{1,−1\}$ matrix of size $n$ is $2^{n−1}$ times the maximal determinant of a $ \{0,1\}$ matrix of size $n−1$. How to prove this result? (I found this statement while ...
8
votes
2answers
116 views

integer as sum of three binomials

Prove that for any nonnegative integer $n$ $\exists x,y,z \in \mathbb{N}$ and $0\leq x<y<z$ so $$n=\binom{x}{1}+\binom{y}{2}+\binom{z}{3}$$ Please give me a hint, I don't have any idea.
0
votes
0answers
74 views

Reference request for well known theorem in combinatorics

From where, I can find the proof of the following theorem. I have to to cite it, in my research article. Theorem: The combination $ {n} C {r}$ is the number of possibilities for ...
0
votes
1answer
724 views

Probablity question [closed]

A box of clothes contains 15 shirts and 10 pants. Three items are drawn from the box without replacement. What is the probability that all three are all shirts or all pants? The correct answer is ...
3
votes
1answer
59 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) = ...
1
vote
2answers
32 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 ...
1
vote
0answers
37 views

Predicate logic a game where player goes first?

What kind of predicate logic statement describes a game that the person who goes first can always win? Write you answer in terms of successive moves by two players. I am lost here I tried initially ...
4
votes
2answers
153 views

An identity involving Bernoulli and Stirling numbers

I was playing with some combinatorial sums and made an observation that I didn't know how to prove: $$\forall n\in\mathbb N,\hspace{10px}\sum_{k=1}^n\frac{B_k\ ...
0
votes
6answers
3k views

Combinatorial proofs: having a difficult time understanding how to write them out

Can someone explain how combinatorial proofs work? I've included an example questions that's been giving me a hard time. Any insight on the topic would be great. $$\sum_{k=1}^{n}k{n \choose k} = ...
2
votes
1answer
75 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? ...
2
votes
3answers
33 views

Picking edges from a connected graph so that any vertex is incident with an odd number of those edges

Suppose you are given a connected graph G having an even number of vertices. Show that you can select a set $E$ of edges from this graph so that any vertex in G is incident with exactly an odd ...
7
votes
1answer
92 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 ...
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} + ...
4
votes
2answers
73 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 ...
1
vote
1answer
52 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 ...
1
vote
1answer
37 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
0answers
121 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:: ...
2
votes
2answers
96 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 ...
2
votes
1answer
100 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 ...
1
vote
2answers
81 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: ...
4
votes
4answers
2k views

Probability of winning the game 1-2-3-4-5-6-7-8-9-10-J-Q-K

A similar question to mine was answered here on stackexchange: Probability of winning the game "1-2-3" However, I am unable to follow the formulas so perhaps someone could show the ...
3
votes
1answer
87 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)!} + ...
1
vote
1answer
41 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: ...
1
vote
1answer
45 views

Reduced Words of Length $l$

How many reduced words are there of length l the free groups of rank $r$? Moreover I want to know about the number of cyclically reduced words? I think $r(r-1)^{l-1}$ is the answer for first ...
0
votes
1answer
61 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... ...
4
votes
2answers
276 views

Possible sides of and octahedron

What number of unique patterns can be made if all sides of an equilateral octahedron is blue or green? How do you solve such a problem? I have only tried to solve this by a hands-on approach, i.e. ...
3
votes
5answers
90 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
3answers
131 views

Probability that no two consecutive heads occur?

A fair coin is tossed $10$ times. What is the probability that no two consecutive tosses are heads? Possibilities are (dont mind the number of terms): $H TTTTTTH$, $HTHTHTHTHTHTHT$. But ...
1
vote
0answers
40 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 ...
0
votes
2answers
78 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
0answers
85 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 $$ ...
0
votes
2answers
57 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 ...
1
vote
1answer
42 views

Maximal Distance of a graph

So I have the following graph $G = (V, E)$ with $V = [d]^n$ and $E = \{\{(a_1,\dots , a_n), (b_1, \dots , b_n)\} | a_2 = b_1 a_3 = b_2, \dots a_n = b_{n-1}\}$. That is called a $(n, d)$-dimensional ...
1
vote
2answers
57 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
48 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 ...
3
votes
2answers
242 views

How can I prove this combinatorial identity?

Let $n,m$ be non-negative integers. How can one prove the following identity? $$\sum_{j=0}^n j\binom{2n}{n+j}\binom{m+j-1}{2m-1}=m\cdot4^{n-m}\cdot\binom{n}{m}$$
0
votes
1answer
86 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 ...
6
votes
0answers
135 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 ...
3
votes
3answers
98 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
66 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
65 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
42 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 ...