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
3answers
157 views

How to find distribution for roll of 2 dice

You roll 2 ordinary dice. Let X denote the maximum of the two numbers you get. What is the distribution of X? I did the problem as follows: $$\begin{array}\\ X &= 1: (1, 1) \\ X &= 2: ...
1
vote
1answer
54 views

Gaussian polynomial identities

I'd appreciate any hints for showing that these identities are true for Gaussian polynomials. I've tried to approach the problem using basic algebra but it gets messy very quickly and I've gotten ...
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} = ...
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}$: $$ ...
5
votes
3answers
2k views

How many squares in the $m \times n$ grid

Is there a formula to evaluate the number of all squares in the $m \times n$ grid? Well, I'm just curious, I've seen the question like this somewhere at the university, to solve this they were ...
1
vote
2answers
392 views

When to Add and/or Multiply Combinatorial Coefficients?

Though having read I and II, I still fail to understand when to add and/or multiply Combinatorial Coefficients. I exemplify my confusion: Multinomial Pascal's Rule $\quad$ Source: 1.18, p 20, A ...
2
votes
0answers
44 views

Cartesian product of two graph's sets of edges

If $G=(U,V,E)$ is an undirected bipartite graph, that means that there are no edges in $E$ between vertices from a set in $U$ to/from a vertex in $V$. There are only edges between the sets $U,V$. I ...
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$ : ...
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 ...
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 ...
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 ...
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{ ...
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 ...
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 ...
6
votes
1answer
534 views

What is the number of ways to divide a rectangle into $n$ smaller rectangles line by line?

The original problem was to consider how many ways to make a wiring diagram out of $n$ resistors. When I thought about this I realized that if you can only connect in series and shunt. - Then this is ...
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
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
32 views

Permutations and Combinations: Word Problem

You are to create a committee of $2$ men and $2$ women from a group of $8$ men and $8$ women. Each committee member will fill a role; president, vice president, secretary, and treasurer. How many ...
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 ...
24
votes
6answers
19k views

In how many ways can a number be expressed as a sum of consecutive numbers?

All the positive numbers can be expressed as a sum of one, two or more consecutive positive integers. For example 9 can be expressed in three such ways, 2+3+4, 4+5 or 9. In how many ways can a number ...
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 ...
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.
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
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 ...
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 ...
3
votes
4answers
19k views

How many even numbers of four digits can be formed with the digits 0,1,2,3,4,5 and 6 no digit being used more?

My attempt to solve this problem is: First digit cannot be zero, so the number of choices only $6 (1,2,3,4,5,6)$ The last digit can be pick from $0,2,4,6$, so the number of choices only 4 Second ...
1
vote
3answers
76 views
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 ...
2
votes
3answers
125 views

The number of times will an individual child goes to the cinema before a group is repeated.

$1.)$ A mother with $7$ children takes $3$ at a time to a cinema.She goes with every group of $3$ that she can form.How many times can she go to cinema with distinct groups of $3$ children? ...
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, ..., ...
-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 ...
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!
4
votes
2answers
56 views

The chart-problem; problem solving

In how many ways can we construct a $6\times 6$ chart with only $1$ and $-1$ such that in every row and column, the product is always positive?
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- ...
6
votes
4answers
840 views

Is $n \choose k$ defined when $k < 0$? What about $n < k$?

I know that ${n \choose 0} = 1$, and this makes sense to me based on my understanding of combinatorics. But what about ${n \choose -1}$? My instinct is that this is undefined, since it is equivalent ...
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 ...
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 ...
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
104 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
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 ...
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
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
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 ...