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
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$ ...
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 ...
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
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 ...
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
1answer
14 views

Finding common ranking of contestants in dance competition

At a dance competition there are a number of contestants and $64$ judges. Each judge ranks the contestants from best to worst, with no ties. For any three contestants $A,B,C$, there do not exist three ...
1
vote
3answers
76 views

Is there an expression for the sum of $\binom nr^2$ for each $n$? [duplicate]

Is there a standard expression for $$\sum_{r=0}^{n}\binom nr^2$$
4
votes
3answers
71 views

A result of equation $y^2+1=x^p$ where $p$ is odd prime.

Example 2.4.4 page 23 of the book "Problems of algebraic number theory" by R. Murty is about solving equation $y^2+1=x^p$ where $p$ is odd prime and $x,y\in \mathbb{Z}$. Solving this example lead to ...
-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
1answer
13 views

Example of set with irrational upper arithmetic density?

All the examples i can think of have rational density.
-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
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
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! ...
1
vote
2answers
41 views

Guide to solving Harary's exercises

Most of Harary's harder exercises are research problems (although solved), that need almost always a single key idea as a breakthrough. Often it so happens that even after thinking for a long time no ...
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 ...
2
votes
2answers
43 views

How many integers are there between $1$ and $2011$ inclusive that are multiples of $6$ or $7$ or $9$ but not $12$?

How many integers are there between $1$ and $2011$ inclusive that are multiples of $6$ or $7$ or $9$ but not $12$?
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
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 ...
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}\ \ ...
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, ...
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 ...
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 ...
1
vote
1answer
73 views

Using generating functions to answer how many bit strings of length N have no 000

The Problem I've been self-studying Introduction to Analysis of Algorithms by Sedgewick and Flajolet. I'm on the fifth chapter, and struggling with exercise 5.1: How many bit strings of length N ...
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 ...
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
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 ...
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 ...
2
votes
1answer
46 views
+50

Seeking more information regarding the “hybriation function.”

Definition 0. Given a pair of finite sets $Y$ and $X$, write $Y_X$ for the set of all collections $\mathcal{K}$ of functions $f : Y \leftarrow X$ that are closed under "hybridization", by which I ...
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 ...
-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?
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. ...
-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 ...
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.
8
votes
3answers
115 views

Find the sum $\sum _{ k=1 }^{ 100 }{ \frac { k\cdot k! }{ { 100 }^{ k } } } \binom{100}{k}$

Find the sum $$\sum _{ k=1 }^{ 100 }{ \frac { k\cdot k! }{ { 100 }^{ k } } } \binom{100}{k}$$ When I asked my teacher How can I solve this question . He responded it is very hard you can't solve it ...
-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 ...
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 ...
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
33 views

Find the different Binary String [duplicate]

I want to generate a binary String, such that number of occurrence of 01,10,00 and 11 are to be fixed. For Ex: Number of occurrence of 01,10,11 and 10 are 1 1 2 and 1 respectively. ...
2
votes
2answers
95 views
+50

Splitting a set into two disjoint sets five times, minimizing pairs in the same set

Suppose you have a class of 11 students . I want to split the class into two groups five different ways, minimizing the number of times that any two students are in the same group. In more ...
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 ...
1
vote
0answers
18 views

Unique unordered combinations of varying length

Given random set of integers. I.e. $\{1,2,2,3,3,3,5\}$ Find the number of unique, unordered of varying length sets that can be created. My Workings This is not a homework problem, but rather, ...
0
votes
4answers
51 views

What is the probability that there are $k$ people between $A$ and $B$?

If $n$ people are randomly seated in a row and two of the people are $A$ and $B$, what is the probability that there are $k$ people between $A$ and $B$ ($A$ can be either to the left or right of ...
0
votes
1answer
24 views

Are the following families of sets closed under intersection?

Problem Statement Let $X$ be any set whatsoever, and let $f:X\to X$ be any function. Note that in general, no structure is imposed on $f$ whatsoever (i.e. continuity, linearity, etc). The problem is ...
2
votes
0answers
21 views

Number of $2 \times 2$ images in RGB

I am a bit rusty on math and was wondering if someone could check my back of the envelope calculation. Each RGB component has values between 0 and 255 inclusive. There are three components so you ...
1
vote
1answer
36 views

Let $A=\{1,..,n\}$. How many pairs $(B,C) \in P(A) \times P(A)$ there are such that $B\space \cap \space C^{c} = \varnothing$? [closed]

How do I solve this set theory problem? Let $A=\{1,..,n\}$. How many pairs $(B,C) \in P(A) \times P(A)$ there are such that $B\cap C^{c} = \varnothing$?
1
vote
0answers
59 views

Counting no of ways under overlapping cases.

I have infinte supply of red and black balls and i am asked what will be the count of number of different arrangements having occurrences of RR, RB, BB and BR equal to inputs A,B,C, and D, ...
-1
votes
1answer
63 views

find number of strings

Find the number of strings consisting of only a and b which have P occurrence of aa Q ...