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)

3
votes
3answers
95 views

Proof that $\sum_{i=0}^n {n\choose i}2^{i}=3^{n}$ [duplicate]

The following sum came up in a combinatorial argument. I know what it equals thanks to Wolfram Alpha, but I'm not sure how to show it $$\sum_{i=0}^n {n\choose i}2^{i}=3^{n}$$
6
votes
4answers
100 views

# of partitions of $n$ into at most $r$ positive integers $=$ # of partitions of $n + r$ into exactly $r$ positive integers?

How do I see that the number of partitions of the integer $n$ into at most $r$ positive integers is equal to the number of partitions of $n + r$ into exactly $r$ positive integers?
1
vote
0answers
32 views

What is the probability of no cycles length $n$ in a simple, directed Erdos-Renyi graph with $n$ vertices?

What is the probability of having no cycles with length $n$ (touching all vertices) in a simple, directed Erdos-Renyi graph with $n$ vertices? For example, if $n=2$, then the probability is ...
7
votes
2answers
271 views

Combinatorial proof: $p^{r-n}$ divides $\binom{p^{r-2}}{n}$

Let $p$ be an odd prime. Then if $1<n<r$, $$p^{r-n}\,\left|\,\binom{p^{r-2}}{n}\right.$$ Does anyone have a clever combinatorial proof of this fact? There's an easy argument just by counting ...
1
vote
1answer
40 views

Circles on a plane

$n$ circles with total area A have been drawn on the plane (overlapping circles are not counted multiple times). Prove that we can select a disjoint union of circles that has area greater than ...
2
votes
1answer
24 views

Let $x_{1},…,x_{n}\in\mathbb{Z}_{\leq1}$ with sum $1$. There is a circulant permutation s.t $\sum_{i=1}^{k}x_{\pi(i)}\leq0 \forall k\leq n-1$.

Let $x_{1},...,x_{n}$ be integers such that $x_{i}\leq1$ and $\sum_{i=1}^{n}x_{i}=1$. I want to show there exists a circulant permutation $\pi$ of ${1,...,n}$ such that $\sum_{i=1}^{k}x_{\pi(i)}\leq0$ ...
2
votes
2answers
21 views

Number of ways to distribute 4 different objects and 5 identical objects in 3 separate groups?

So, the question goes as: The number of ways in which 4 different toys and 5 identical marbles can be distributed between 3 different people, if each person gets at least one toy and one marble is? ...
0
votes
0answers
16 views

Tournament graph with strong vertex in any subset

Consider a tournament graph with $110$ vertices. In any set of $55$ vertices, there exists a vertex that has an out-edge to at least $50$ of the remaining $54$ vertices. Prove that there exists a ...
0
votes
0answers
30 views

Number of sequences of heads and tails of length $k$ such that the number of heads is never more than $m$ less than the number of tails?

If I flip a coin $k$ times and write down the sequence of heads and tails. If it any point during flipping I flip $m$ more tails than heads, then I stop. How many valid sequences of heads/tails can I ...
1
vote
0answers
49 views

How many people at the party?

At a party, there are $n$ people. A waiter counts 188 cin-cin. How many people partecipate at the toast? I have solved the problem in this way: $\displaystyle\frac{n(n-1)}{2}=188$ but I ...
2
votes
0answers
23 views

Prove that $\sum^{n}_{i=0}\binom{n}{i}F_{i}=F_{2n}$ [duplicate]

I am asked: Let $F_{i}$ denote the $i$-th Fibonacci number. Prove that $$\sum^{n}_{i=0}\binom{n}{i}F_{i}=F_{2n}$$ I have the base case and the inductive hypothesis, but I'm not sure what ...
0
votes
2answers
48 views

Minimum number of moves to even out a row of brick piles

Consider a row of $15$ piles of bricks. There is a total of 75 bricks, all identical. The number of bricks per pile varies across the piles. For instance, the distribution of bricks per pile might be ...
1
vote
2answers
237 views

Ways to color an octagon's vertices with three colors?

In how many ways can we color the 8 vertices of an octagon each red, green, or blue, so that no two adjacent vertices are the same color? I think there should be something to do with Catalan numbers ...
3
votes
2answers
36 views

Combinatorics Question with bridges and inability to cross over each other

Several small villages are situated on the banks of a straight river. On one side, there are $20$ villages in a row, and on the other there are $15$ villages in a row. I would like to build bridges, ...
1
vote
2answers
378 views

Combinations & Permutations whole numbers

I would like to know how to figure out the following problem using a combination formula: -How many ways are there of making a total of 15 using three different whole numbers? Thank you, Estella
-2
votes
1answer
24 views

Combinatoric problem - roundtable [closed]

How many ways we can settle 25 people to roundtable ? every place is the same. Thanks
1
vote
2answers
49 views

Baseball related problem (balls and boxes)

Thanks in advance for any help! So I am trying to figure out if the number of hits an inning of baseball is random, or if hits tend to come in bunches. To do this, I'm just using a fairly small ...
1
vote
1answer
33 views

Show any graph G contains an r-partite subgraph H with e(H) $\geq \frac{r-1}{r} e(G)$

I'm trying to show that for any $r \geq 2$, any graph G contains an r-partite subgraph H with e(H) $\geq \frac{r-1}{r} e(G)$ I'm supposed to be using the first moment method in probabilistic ...
-1
votes
1answer
41 views

Permutation of letters, the principle of inclusion and exclusion [closed]

How many permutations of the letters ABCDEFG do not include ABCDE, EDAB, EDG, GFAB. My solution: $$7! - \left(\frac{7!}{5!} + 2 \cdot \frac{7!}{4!} + \frac{7!}{3!}\right)$$
1
vote
1answer
13 views
0
votes
1answer
38 views

The expected range covered by a random walk

The question that I have been struggling with lately is: If we have a one-dimensional random walk of length $n$ (consisting of $n$ steps) with discrete steps $1$ and $-1$, with probabilities of ...
1
vote
2answers
38 views

In how many ways can 5 men and 5 women sit at a round table such that no 2 persons of the same gender sit next to each other?

In how many ways can 5 men and 5 women sit at a round table such that no 2 persons of the same gender sit next to each other? The book's answer is $2\times 5! \times 5!$ Why is it not $2\times 4! ...
0
votes
0answers
44 views

5 red balls, 5 white balls and 5 blue balls into 3 different boxes?

Consider this Question How many ways can we put 5 red balls, 4 green balls and 3 white balls into 12 slots? This question is answered in math.stackexchange.com. Accepted answer is 12!/(5!. ...
1
vote
2answers
74 views

Example of non-commutative association scheme

I need an example of non-commutative association scheme of ordered 6. I tried to use the example in the book Handbook of Combinatorial Designs, Second Edition by Charles J. Colbourn‏،Jeffrey H. Dini ...
0
votes
2answers
26 views

Counting ways to arrange the word REGULATIONS.

Find the number of ways the word REGULATIONS can be arranged such that there are exactly $4$ letters between $R$ and $E$ . I did $4!\ \ \ \ \text{for}\ \ ...
4
votes
0answers
213 views

What is known about this jigsaw combinatorics problem?

The problem: How many valid reconfigurations, as defined below, are there for a given puzzle? My question is, what, if anything, is known about this problem already? For example, does this ...
2
votes
0answers
502 views

How should I count visitors to a website that receives visitors from 3 locations?

I'm doing a programming exercise, these are the instructions: TLDR version of problem below Priority Our website receives visitors from 3 locations and the number of unique visitors from each of ...
0
votes
2answers
32 views

How to calculate the minimum and maximum number of matches between two sequences?

I have two sequences of the same length $n=3$: $\{A,B,C\}$ and $\{A,A,B\}$. When I compare them, there is 1 match since both have an "$A$" in the first position. Generating all 6 permutated versions ...
3
votes
3answers
55 views

In how many ways can the letters be arranged so $A$ is not adjacent to $B$, $B$ is not adjacent to $G$, and $G$ is not adjacent to $D$?

The letters are $A,B,C,D,E,F,G,H,I,J$. The question is in how many ways can you order the letters in line, such that: $A$ is not adjacent to $B$, $B$ is not adjacent to $G$, $G$ is not adjacent to ...
1
vote
1answer
43 views

Stable Matching Problem Worst Preference?

Suppose we have one hundred pairs of women and men, and there is a man M that is ranked the second highest on every woman's preference rankings. Would it be possible that he ends up with the woman he ...
2
votes
0answers
29 views

Simplify binomial coefficients sum [duplicate]

Exercise requires to simplify this sum: $$\sum_{k=0}^{20} \binom{50}{k}\binom{50}{20-k}$$ Tried to figure this out with no success. I have only final answer, which is $\binom{100}{20}$. Please help ...
1
vote
0answers
19 views

In how many ways can you sit 12 men and 12 women on a bench, so that no 2 women sit next to each other [duplicate]

In how many ways can you sit 12 men and 12 women on a bench, so that no 2 women sit next to each other? There are 2 possible ways to sit them: 1 - In the first sit (from the left) sits a man, and then ...
1
vote
4answers
1k views

password lock problem

There is a lock with the password between 000-999. But we could use only two digits to open the lock. For example, if the password is 123, the lock is open when you try 1*3, or *23, or 12*. ...
-4
votes
2answers
49 views

Combinations of 8 people and 4 double tents [closed]

We have eight people and four tents. Tents are double, indistinguishable / same. How many possibilities are?
0
votes
2answers
61 views

What is the minimum number of sign patterns in $\frac n2$ of columns (or rows) of Hadamard matrices?

Given a Hadamard matrix of size $n$, I want to know what is the minimum number of unique sign patterns in any $\frac n2$ columns (or rows). I count a sign pattern and its negation to be the same. My ...
8
votes
1answer
402 views

Counting ordered tuples with an additional condition

Let $a_1 \le a_2 \le ... \le a_n$ be positive integers. I'm looking for a closed formula of the number $f(a_1,...,a_n)$ of all (ordered) tuples $(x_1,...,x_n)$ of positive integers statisfying $$x_1 ...
0
votes
1answer
23 views

Trouble with Inclusion-Exclusion (Multiplication Theorem)

$A_i$ is one event out of $n$. $$P\left(\bigcap_{i=1}^n A_i\right) = P(A_1)P(A_2|A_1) \dotsb P(A_n|A_1A_2...A_{n-1})$$ I have trouble with this theorem (I am not sure what its name is, so the title ...
-1
votes
1answer
20 views

number of combinations in a set [closed]

If I have a set, say $A = \{1,2,3,4,5,6,7,8,9\}$. I think combinations is the incorrect term here, but I don't know what is. I want the total number of different combination of all lengths so I ...
3
votes
3answers
54 views

how to come up with this identity $\sum\limits_{i=r}^{n-k+r}{i \choose r}{{n-i} \choose {k-r}}={{n+1} \choose {k+1}}$

This identity is used in an exercise. Could you help me understand how I should reason to come up with it? Ideally, from a combinatorial point of view.
0
votes
2answers
75 views

How many ways to arrange people on a bench so that no woman sits next to another woman? [closed]

There are $12$ women and $12$ men. How many ways are there to sit them all on a bench where no woman can sit next to another woman? Thank you.
0
votes
1answer
40 views

Fibonacci numbers of higher order

Which short closed-form formulas for the Fibonacci numbers of higher order $F(m;n)$ (Wikipedia: Generalizations of Fibonacci numbers), or of its shifted form $F(m;n+m-1)$, are there? I already found ...
0
votes
2answers
359 views

Number of ways to choose a sequence of three letters from the letters of MISSISSIPPI

How many ways can a sequence of three letters be chosen from the letters of MISSISSIPPI? I'm just a little confused how to go about this since so many letters repeat I=4 S=4 P=2 So ultimately ...
2
votes
3answers
46 views

Vandermonde's identity? How to continue? [duplicate]

I have: $$\sum\limits_{k = 1}^{10}k\binom{10}{k}\binom{20}{10-k} = $$ and I know that it doesn't matter if $k = 0$ so it also equals: $$= \sum\limits_{k = 0}^{10}k\binom{10}{k}\binom{20}{10-k} = ...
1
vote
0answers
22 views

How can I divide 2 identical objects of one type, 2 identical objects of second kind and 2 identical objects of third kind?

How can I divide $2$ identical objects of one type, $2$ identical objects of second kind and $2$ identical objects of third kind into $3$ groups such that each groups contains only two objects. ...
0
votes
1answer
29 views

Where do the combinations come from in these examples of using the generalized inclusion exclusion principle?

I'm trying to understand where the combinations (the coeffecients of the $Si$'s) of this example come from. From my understanding, the first example denotes the generalized inclusion ...
-3
votes
0answers
22 views

Number of binary strings given number of two bit patterns

Given $p,q,r,s$, find the number of binary strings in which there are exactly $p$ substrings $00$, exactly $q$ substrings $01$, exactly $r$ $10$ and exactly $s$ $11$. How should I approach this ...
-1
votes
1answer
61 views

Probability of last $3$ captains photo (stars and bars) [on hold]

For a promotional event each packet of chips contains a photo of one of the last $5$ captains of the Indian test cricket team. The probability that a given packet contains the photo of any particular ...
1
vote
2answers
27 views

Combinatorics. Find the number of three digit numbers from 100 to 999 inclusive which have any digit that is the average of other two?

Combinatorics. Find the number of three digit numbers from 100 to 999 inclusive which have any digit that is the average of other two? i tried to do it by making different cases but the answer did ...
-1
votes
0answers
51 views

No. of ways to Generate the String [duplicate]

I want to generate a binary string, such that number of occurrence of $00,01,10$ and $11$ are to be fixed. How can we find out the numbers of ways for given value. For example: number of occurrence ...
4
votes
1answer
19 views

Number of quadrilaterals in a heptagon: is my reasoning correct?

I found this question on a GRE prep site: If you join all the vertices of a heptagon, how many quadrilaterals will you get? There is a bunch of multiple choice answers but to me none of them ...