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
22 views

Product of the edges is distinct

We have a complete graph with $n\geq 3$ vertices. Show that we can label the edges with $1,2$, or $3$ so that the product of the edges is distinct at every vertex. For $n=3$ this is obvious. For ...
0
votes
0answers
17 views

combinatorial optimization - choosing portfolios

Here is my problem.. I have 100,000 individuals choosing portfolios of size 6 among 2,000 potential. Each individual must submit a ranked list of orders. A portfolio $j$ yields utility $u_{ij}$ for ...
0
votes
0answers
16 views

Hypercontractivity Lemma

In the proof of the Hypercontractivity Lemma here http://www.cs.cmu.edu/~odonnell/boolean-analysis/lecture13.pdf (3.4) what does it mean to split $p$ into $r + x_n*s$, why can we do this?
0
votes
0answers
26 views

The minimum of two big-O functions

Suppose we have the following lower and upper bounds for an invariant $\chi(G_N)$, where $G_N$ is a graph on $N$ vertices, $N=f(k,n,m) $ and $N,k,n,m\in \mathbb{N}$: $$ ...
0
votes
2answers
27 views

(Probability)Bars and stars problem with two constraints

What is the probability that you roll 4 die and get a sum less than or equal to 5? So far, I have come up with this: $x_1 + x_2 + x_3 + x_4 \leqslant5 $ Constraints: $x_1, x_2, x_3, x_4 ...
3
votes
2answers
30 views

Alice, Beatrice and a tournament

In a tournament of $2^n$ players, Alice and Beatrice ask what's the probability that they'll not compete if they've the same level of play? Let : $A_i$ : Alice plays the $i$-th tournament ; $B_i$ : ...
2
votes
2answers
52 views

Prove that the intersection of all the sets is nonempty.

Given $2^{n-1}$ subsets of a set with $n$ elements with the property that any three have nonempty intersection, prove that the intersection of all the sets is nonempty. I find this question a bit ...
1
vote
1answer
35 views

What is this matrix notation and how is it solved?

I've never taken a stats class, or linear algebra or much of anything that involves matrices. In one of my books they give me this as part of an example and it states, $$\binom{6}{4} = 15 \text{ ...
3
votes
1answer
48 views

Tricky pigeonhole principle question

Say someone is given at least one marble every day for 7 weeks. However, there are never more than 11 marbles given to the person in one week. Prove that there is some period of consecutive days in ...
0
votes
1answer
33 views

In how many ways can you order in line the letters of the words $AAAABBBBBCCDE$ such that

In how many ways can you order in line the letters of the words $AAAABBBBBCCDE$ such that none of the substrings: "$DE$" or "$ED$" appear in the beginning or in the end? I was thinking - take all the ...
0
votes
1answer
15 views

Formula for choosing $x$ elements from a set containing $n$ elements, with repetition allowed

I've been searching around for a formula for the number of cmbinations for choosing $x$ elements from a set containing $n$ elements. For instance, for the set $(1,2,3)$ we have $10$ different ways of ...
0
votes
2answers
19 views

$A = \{{1, … , n\}}$ - How many $(B,C) \in P(A) \times P(A)$ are there such that $B \cap \overline{C} = \emptyset$?

$A = \{{1, ... , n\}}$ How many $(B,C) \in P(A) \times P(A)$ are there such that $B \cap \overline{C} = \emptyset$ ? I got to the conclusion that it must be $\sum\limits_{k=0}^{n}2^k$ because for ...
0
votes
1answer
27 views

Number of n-tuples, whose elements <=than q, sum up to k

Given $X^q_n=\{1,...,q\}^n$, with $q<n$, whose elements are the n-tuples $x = (x_1, ..., x_n)$, I would like to find an explicit formula for $$|V_k^n|$$ where $$V_k^n = \{ x \in X^q_n ...
2
votes
0answers
19 views

Proving number of partitions of $n$ to $3$ parts at most.

I have an exercise, to prove that the number of partitions of $n$ to at most $3$ integers is $\frac{(n+3)^2}{12}$ rounded. I tried to prove by induction but I don't know how.
2
votes
3answers
28 views

In how many ways can you order in line the letters of the word $AAABBCDEFG$

In how many ways can you order in line the letters of the word $AAABBCDEFG$ , such that $A$ or $E$ will be the first letter? I'm thinking there are $2$ options for the first letter ($E$ or $A$) and ...
3
votes
2answers
29 views

How many pairs are in $(B,C) \in P(A) \times P(A)$ such that $B \subseteq C$

I'm trying to solve this problem: Let $A = \{1,2,3,\ldots,n \}$ How many pairs are in $(B,C) \in P(A) \times P(A)$ such that $B \subseteq C$ I want to solve this using combinatorics, Basically what ...
0
votes
0answers
7 views

Count options for sitting people om a bench [duplicate]

I have this combinatoric question which I can't figure out. In how many ways can we sit 12 men and 12 women on a bench where no 2 women sit next to each other. The answer is : $ 13! \cdot 12! $ but my ...
2
votes
0answers
18 views

Factorization of permutations into two factors with fixed number of cycles, plus a placement condition

I have asked this question in MathOverflow, but it received no answers, so I am posting it here. In my recent work I have been led to consider the following type of permutation factorizations. Let ...
0
votes
3answers
53 views

How many non-negative integer solutions are there for the equation $x+y+z = 11$ when $x \geq 1$, $y \geq 2$, and $z \geq 3$?

So, if $x+y+z=11$, and $x \ge 1, y \ge 2$, and $z \ge 3$, how many non negative integer solutions can it have? So far, I did the math this way: $C(10 + (3-1),10) = C(12,10)$ for $x$ being at least ...
2
votes
1answer
88 views

Swapping the order of limits in combinatoric?

Part $A$ Let a power series be $ \sum_{r=1}^\infty x^{a_r}$ Now, we are interested square of the power series with the condition: $$ \sum_{m=1}^\infty \sum_{n=1}^\infty x^{a_m + a_n} = ...
2
votes
1answer
222 views
+100

Positivity of the alternating sum associated to at most five subspaces

Let $V_1 , V_2 , \dots , V_n $ be proper subspaces of $ \mathbb{C}^m$ and let $$\alpha = \sum_{r=1}^n (-1)^{r+1} \sum_{ \ i_1 < i_2 < \cdots < i_r } dim(V_{i_1} \cap \cdots \cap V_{i_r})$$ ...
-4
votes
0answers
47 views

How many ways can you arrange the numbers $1,2,3,4,5,6,7,8,9,10$ in a way that all the numbers that [closed]

How many ways can you arrange the numbers $1,2,3,4,5,6,7,8,9,10$ in a way that all the numbers that are bigger than $6$ will be to the left of $6$. The answer should be: $$\binom{10}{6}5!\cdot ...
10
votes
2answers
107 views

For any $n^2+1$ closed intervals of $\mathbb R$, prove that $n+1$ of the intervals share a point or $n+1$ of the intervals are disjoint

Stuck on a question from 'Introduction to Combinatorics by Martin J. Erickson'. Q: For any $n^2+1$ closed intervals of $\mathbb R$, prove that $n+1$ of the intervals share a point or $n+1$ of the ...
1
vote
1answer
49 views

Find numbers whose sum of digits equals a value

How do I find all of the numbers in a given range whose sum of digits equal to a given value? For example: Range : 100 - 9000 Value : 4 Result : 103, 112, 121, 130, 202, 211, 220, 301, 310, ..., ...
1
vote
2answers
36 views

Counting problem (students assigned to a tutor)

Four new students have to be assigned to a tutor. There are seven possible tutors, and none of them will accept more than one new student. In how many ways can the assignment be carried out? The ...
0
votes
1answer
36 views

In how many ways can 40 identical carrots be distributed among 8 different rabbits?

In how many ways can 40 identical carrots be distributed among 8 different rabbits, while every rabbit needs to get a carrot, and no rabbit get more then 16 carrots. Thank you for the help!
3
votes
1answer
32 views

Number of Different Elements of $S_{ijkl}$ with Some Symmetries

I am not good at combinatorics so I am asking this simple question to learn a little. In fact, this question is motivated by the symmetries happening for the stiffness and Eshelby tensors in the ...
0
votes
1answer
23 views

How find the length of an array

Story: In fact this question is related to THIS. How to create an array maintaining following conditions- ...
2
votes
0answers
20 views

summation combinatoric again with floor function

$\sum_{n=1}^{33}\binom{3n}{\left \lfloor 1.5n-0.5 \right \rfloor}= ...$ $\binom{3}{\left \lfloor 1 \right \rfloor}+\binom{6}{\left \lfloor 2.5 \right \rfloor}+\binom{9}{\left \lfloor 4 \right ...
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 ...
1
vote
1answer
41 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 ...
0
votes
1answer
32 views

Dividing Up A Circular Search Area

BACKSTORY: I need to collect 500 plant samples for strontium analysis. The samples are randomly distributed across a circular area with a radius of 300 kilometers. I have to do this in 30 days, so I ...
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
22 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
72 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 ...
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
42 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}\ \ ...