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
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 ...
2
votes
2answers
42 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 ...
-1
votes
1answer
40 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
44 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
37 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
76 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
46 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 ...
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
51 views

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
77 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 ...
2
votes
3answers
47 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
150 views

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

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. I ...
-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
28 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
31 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
110 views

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
20 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
54 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
22 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
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 ...
1
vote
2answers
46 views

How many arrangements are there of the word POISONS so that no two vowels are together?

I actually have 3 questions to ask. You just have to say if my solution is right or not. First question: How many arrangements are there of the word POISONS so that no two vowels are together? I ...
1
vote
3answers
55 views

how many $7$ digit numbers can be formed using $1,2,3,4,5,6,7,8,9,0$

How many seven digit numbers can be made if $(a)$ they must be odd and repetition is not allowed $(b)$ they must be even and repetition is not allowed $0532129$ is not a seven digit number So the ...
1
vote
1answer
83 views

Number of binary numbers given constraints on consecutive elements

I've been trying to solve this question for quite a while, given to us by our discrete maths professor. I've been having a hard time in general with it, so I thought I tried looking it up online but ...
2
votes
1answer
20 views

How many 5-card hands are there with 3 hearts and a three-of-a-kind?

How many possible 5-card hands from a deck of 52 cards are there that consists of 3 hearts and a three-of-a-kind? I did: C(13,3) = number of ways to choose three hearts C(3,1) = number of ways to ...
1
vote
0answers
57 views

Name of this formula or more explantation of the proof?

I have found this formula which is a combinatorial identity for counting binary words. I'd like more information on it, or the name of the proof. I am also not totally clear on the step between the ...
0
votes
1answer
19 views

probability of the product of drawn numbers is positive

We have just started learning probability in class, and have done one lesson on basic combinatorics, I'm going through some practice questions and have stumbled upon a few. The first is: A box ...
0
votes
2answers
55 views

Closed form for a binomial identity another solution

Is this true? $$\sum_{j=0}^n{j \cdot \displaystyle\binom{j}{r}} =\displaystyle\frac{(n+1)(r+1)-1}{r+2}\displaystyle\binom{n+1}{r+1}$$
-2
votes
3answers
61 views

Of 100 people seated at a round table, more than half are women. Prove that there exist two women who are seated diametrically opposite each other. [closed]

Of 100 people seated at a round table, more than half are women. Prove that there exist two women who are seated diametrically opposite each other.
4
votes
2answers
176 views

There are 40 men and 40 women. In how many ways can you pick a board of 31 people that has a majority of women? [duplicate]

There are 40 men and 40 women. In how many ways can you pick a board of 31 people that has a majority of women? I was thinking - let's start with the women. There are $\binom{40}{16}$ ways to pick 16 ...
2
votes
1answer
28 views

Switching balls among 3 piles

There are 3 piles of balls. Each hour, I take a ball from one pile and move it to another. The amount of points I earn from this move is the amount of balls in the pile I took the ball from minus the ...
0
votes
3answers
49 views

Given a number '$N$' find how many how many numbers are there between $1$ to $N$ that doesn't contain the digit $3$?

You are given a number $N\le 10^{18}$. You need to find out how many numbers there exist in between $1$ to $N$, which doesn't contain the digit $'X'$ in it . Say $N = 5, X=4$ The answer is $4$. ...
0
votes
2answers
39 views

What kind of binomial formula works here?

I need to write the following sum in a simple way (without sigma): $$\sum\limits_{k=2}^{50}\binom{50}{k}\cdot k \cdot (k-1)$$ I tried Newton's binomial theorem and even Vandermonde's identity but I ...
0
votes
3answers
31 views

How many ways can 20 coins be selected from four containers filled with pennies, nickels, dimes, and quarters?

How many ways can 20 coins be selected from four containers filled with pennies, nickels, dimes, and quarters? (Each container is filled with only one type of coin) So, 20 slots and four choices per ...
2
votes
2answers
38 views

In how many ways can 10 (identical) dimes be distributed among five children?

a. If there are no restrictions? b. Each child gets at least one dime? c. The oldest child gets at least two dimes? For part (a), the textbook gives the answer $14 \choose 10$. Where did the 14 ...