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)

0
votes
1answer
25 views

Two candidates, A & B, are running for president. What is the probability that candidate A beats candidate B?

Candidate A has already garnered 80 votes. Candidate B has already garnered 50 votes. The number of votes a candidate must have in order to win the election is 115. The votes of 5 states are still ...
1
vote
1answer
20 views

Counting models that satisfy PL sentences

I have an assignment where I need to count the number of models of a certain sort which satisfy a given sentence, and I keep finding that the number of models I count exceeds the total number of ...
1
vote
0answers
18 views

Given $5$ points on a sphere, divide the surface into $5$ congruent connected regions containing one point.

There are $5$ points on the surface of a sphere. Is it always possible to divide the surface into $5$ connected congruent regions such that each region contains one of the $5$ points?
1
vote
0answers
29 views

For any given $k$, show that an integer $n$ can be represented as: $n={m_1 \choose 1} + {m_2 \choose 2} + \cdots + {m_k \choose k}$

For any given $k$, show that an integer $n$ can uniquely be represented as: $$n={m_1 \choose 1} + {m_2 \choose 2} + \cdots + {m_k \choose k}$$ where $0 < m_1 < m_2 < \cdots < m_k$. My ...
1
vote
0answers
14 views

Dividing students into groups with added diversity rule

Could someone help me out for a second, please? See here's the problem: 9 greeks, 17 finns, 7 russians, 11 chinese and 8 swedish students are studying in groups. A group can consist of one or more ...
0
votes
0answers
18 views

2016 AMC 10A #18 — Number of ways to label vertices of acube

Each vertex of a cube is to be labeled with an integer $1$ through $8$, with each integer being used once, in such a way that the sum of the four numbers on the vertices of a face is the same for ...
0
votes
0answers
37 views

The probability of the sum of $10$ dice rolls adding up to $57$

So the question is: given that you roll $10$ dice, what is the probability of the sum of the total dice rolls adding up to $57$? I know that there are three ways to do this: Seven die rolls must ...
1
vote
0answers
16 views

Combinatorial proof that $(n-r){n+r-1 \choose r}{n \choose r} = n{n+r-1 \choose 2r}{2r \choose r}$ [duplicate]

Combinatorial proof that $(n-r){n+r-1 \choose r}{n \choose r} = n{n+r-1 \choose 2r}{2r \choose r}$. Typically to combinatorially prove something we need to show that the LHS indeed counts the same ...
0
votes
0answers
24 views

Is there an arbitrarily large set of naturals so that the sum of each two has exactly $n$ prime divisors? What about an infinite set?

Is there an arbitrarily large set of naturals so that the sum of each $2$ has exactly $n$ prime divisors where $n$ is fixed? What about an infinite set? For $n=1$ this is clearly false, what ...
0
votes
0answers
16 views

$r$ balls are randomly distributed into $n$ urns. What's the expected number of urns with $k$ balls?

My text book uses the linearity of the expected value to compute it. It defines a random variable $X_i$ that indicates whether the urn $i$ contains $k$ balls or not. So the asked value is $E[X_1 + X_2 ...
1
vote
0answers
12 views

Best pattern of cinnamonbuns on a baking tray?

Imagine that i have a 50 x 100 cm baking tray, and i have a load of cinnamonbuns, shaped like a circle with a diameter of 10cm. How do i calculate the best place to place my cinnamonbuns, as the ...
0
votes
0answers
21 views

Sampling efficiently conditioned on linear constraints modulo both $\mathbb{F}_p$ and $\mathbb{F}_2$.

Given a prime $p$ and positive integer $t \ll \log p$ (say $t = \sqrt{\log p}$), is there an algorithm that is polynomial time in $\log p$ to sample uniform $X, Y \in \mathbb{F}_p$ conditioned on the ...
0
votes
1answer
37 views

Combinatorial proof for the identity $\binom{m + n}{r} = \binom{m}{0}\binom{n}{r} + \binom{m}{1}\binom{n}{r - 1} + \cdots + \binom{m}{r}\binom{n}{0}$

Think of a set with $m+n$ elements as composed of two parts, one with $m$ elements and the other with $n$ elements. Give a combinatorial argument to show that $\dbinom{m+n}{r}$ = ...
0
votes
1answer
19 views

Using Pascal's formula to derive another formula

Use Pascal’s formula repeatedly to derive a formula for $\dbinom{n+3}{r}$ in terms of values of $\dbinom{n}{k}$ with $k \leq r.$ (Assume $n$ and $r$ are integers with $n\geq r \geq 3).$ I have a idea ...
1
vote
1answer
45 views

Prove ${20n \choose 10n}\ge {2n-1 \choose n-1}^{10}$

As the title says, I can't prove that, no matter what I try. What I've tried so far: induction: seemed the most obvious method, since we already had a lot of tasks with it, but using the esimates ...
0
votes
1answer
23 views

Number of permutations with given cyclic structure

If $\sigma$ is a permutation made up by the disjoint cycles $\tau_1, \dots, \tau_r$ (including those of length $1$), we call structure of $\sigma$ $$(l_1, \dots, l_r),$$ where $l_1, \dots, l_r$ are ...
0
votes
1answer
25 views

There are $n$ seats in a room. If $n$ people come to the room, what is the probability that $j$ specified people occupy $j$ specified seats?

There are $n$ seats in a room. If $n$ people come to the room, what is the probability that $j$ specified people occupy $j$ specified seats? ($j$ names were tagged on the $j$ seats) $n$ people can ...
0
votes
0answers
66 views

Find number of rectangles

There is $N\times M$ grid present with numbering as $1,2,\cdots,NM$ (numbering is done row wise. 1st row will contain number from $1,\cdots,M$, second row will contain $M+1,\cdots,2M$ and so on). ...
1
vote
1answer
31 views

Turning Preordered Sets into Preordered Monoids (Constructing Preordered Monoids from Preordered Sets)

Question: Referring to the Wikipedia article on Adjoint Functors in Section 2 (Motivation), they talk about "turning rngs into rings" (can be rephrased as "constructing rings from rngs"). I do not ...
1
vote
6answers
50 views

Probability of getting $5$ heads on $10$ (fair) coin flips?

Even before attempting the problem, I immediately defaulted to an answer: $\frac{1}{2}$. I thought that this was a possible answer since the probability of flipping a head on one flip is definitely ...
2
votes
2answers
41 views

How many bit strings of length 8 begin and end with a 1?

A bit string is a finite sequence of $0$’s and $1$’s. How many bit strings of length $8$ begin and end with a $1$? My answer would be: $2^6$. Because we know, that the bit starts with $1$ and ...
4
votes
2answers
34 views

What is the probability that these two objects are of the same color?

We have $11$ bins with $10$ objects each. Every object is either black or white, and the $i$th bin ($1 \le i \le 11$) has precisely $(i -1)$ black objects in it. Someone selects, uniformly at random, ...
2
votes
1answer
33 views

Are these two events $A$ and $B$ independent?

Abe and Bernard are dealt five cards each from the same $52$ card deck. Let $A$ be the event that Abe gets a flush (five cards of the same suit) and $B$ be the event that Bernard’s five cards are of ...
1
vote
1answer
18 views

Counting “How many ways to choose courses to graduate” with constraints

I have a problem like, "to graduate you must choose 6 out of 20 courses, but at least 2 out of the 6 courses must be a math course. 8 out of the 20 offered courses are math courses. How many choices ...
1
vote
1answer
23 views

show that the maximum degree of the graph is 6

Let p1, p2, . . . , pn be n points in the plane such that the distance between any two points is at least one. Let G = (V, E) be the graph such that V = {p1, p2, . . . , pn} and E = {pipj | distance ...
0
votes
2answers
26 views

How many times will the innermost loop be iterated

How many times will the innermost loop be iterated when the algorithm segment is implemented and run? Assume $n$, $m$, $k$, and $j$ are positive integers. ...
5
votes
2answers
68 views

Minimum elements present in {0, 1, 2, …, 225} to guarantee triple which sums to 225

Suppose I have the set: $$A=\{0, 1, 2, ... 224, 225\}$$ I want to find a triple that sums to $225$ (where a triple is a set of 3 unique values from the set). No Repetition Version: There are many ...
12
votes
3answers
425 views

Expected value problem with cars on a highway

There is a very long, straight highway with $N$ cars placed somewhere along it, randomly. The highway is only one lane, so the cars can’t pass each other. Each car is going in the same direction, ...
1
vote
1answer
19 views

5-tuples of n integers

If n is a positive integer, how many 5-tuples of integers from 1 through n can be formed in which the elements of the 5-tuple are written in decreasing order but are not necessarily distinct? In other ...
0
votes
1answer
35 views

A coin is tossed $m+n$ times. Find the probability of getting atleast $m$ consecutive heads

A coin is tossed $m+n$ times. Find the probability of getting atleast $m$ consecutive heads I already know that the exact same question has already been answered here But I am trying to solve it ...
2
votes
1answer
33 views

In how many ways can we pick a group of 3 different numbers from the group $1, 2, 3, …, 500$ such that one number is the average of the other two?

Here's the question which I'm struggling with - In how many ways can we pick a group of 3 different numbers from the group $1, 2, 3, ..., 500$ such that one number is the average of the ...
4
votes
2answers
33 views

Pair of friends and a pair of “enemies” in each group of three students

The problem: There is a class. In each group of three students in the class there is a pair of friends and a pair of "enemies". Find the maximum number of students in the class. I tried to play with ...
0
votes
1answer
30 views

How many non-congruent triangles with perimeter 11 have integer side lengths? [on hold]

How many non-congruent triangles with perimeter 11 have integer side lengths? I failed to solve it. Can anyone help?
2
votes
2answers
29 views

Combinatorics: Does this method take into account every possible matchup

It's actually a question on finding the probability, but I am stuck on a different part of this question. There are $2^n$ players playing a tennis tournament. I have to find the total number of ways ...
0
votes
1answer
28 views

number of ways of arranging balls so that there are exactly two pairs of green balls

There are $5$ identical red balls and $6$ identical green balls. In how manys we can arrange them so that there are exactly two pairs of green balls. Let red balls be $R,R,R,R,R$ and green be ...
1
vote
0answers
43 views

How many ways to pick four increasing numbers from 1 through 39?

Say there's a bin of balls numbered 1 through 39, how many ways are there to pick 4 increasing numbers in a row? First I figured that it would be a permutation without repetition problem, so I got ...
2
votes
2answers
36 views

constrained stars and bars problem

I want to know number of solutions for following equation, where $r_k$'s are non-negative integers, and there is a constraint on $r_k$'s such that $r_1 \geq r_2 \geq \cdots \geq r_K$ \begin{equation} ...
0
votes
0answers
15 views

Small graphs containing all trees on $n$ vertices

What do those graphs look like which contain a copy of every tree on $n$ vertices and such that no proper subgraph has this property?
4
votes
2answers
110 views

What am I counting wrong?

EDIT: I made a mistake in the beginning, the second condition has changed. Sorry for this. I'm asked to count the number of sets of 4 elements that satisfy the two following conditions: 1) Each ...
-1
votes
0answers
26 views

Number of solutions of equation with natural numbers [on hold]

Given natural numbers $s, n, k$. How to find number of solutions to equation $a_1 + a_2 + \ldots + a_s = n-s$ where $0 \leq a_i \leq k-1$ and $a_i \in \mathbb{N}$?
0
votes
1answer
67 views
+50

all but one sub-strings within a cyclic string

over $GF(q)$ where $q\in\mathbb{N}$, we build a string of size $q^n-1$. now, how can I show that it is always possible to construct that string so it contains all sub-strings of size $n$ exactly once, ...
-1
votes
0answers
19 views

Onto functions from a set with 4 elements to a set with 3 elements [duplicate]

How many onto functions are there from a set with four elements to a set with three elements? If the four elements set is A = {a, b, c, d} and the three elements set is B = {u, v, x} I see these ...
1
vote
0answers
29 views

What is the probaility that two random permutations have same order?

I am interested in the orders of random permutations. Since the law of the log of the order of a permutation converges to a normal law (for instance Erdös-Turan Statistical group theory III), one ...
0
votes
2answers
27 views

equation to create unique value

I have a list of n objects say [ apple, orange, carrot, cherry, banana ] Now I am trying to come up with an equation which will generate an unique number for ...
3
votes
1answer
57 views

Product of sums into a sum of products

Any idea on how I can get an expression in the form of sum of products from the following one?: \begin{equation} \prod_{i=1}^M \left(\sum_{n=1}^i x_n\right) \end{equation}
1
vote
1answer
37 views

The probability of being dealt at least 5 wanted cards

In a fictional deck of cards, there are 30 cards, 15 different ones (each card has an identical pair, so 15 pairs = 30 cards). I want to answer the question: I am dealt 10 cards. I wish to receive 5 ...
5
votes
1answer
90 views

How to solve this hard sum problem?

$$\sum _{ x=1 }^{ \infty }{ \frac { 3{ x }^{ 2 }+12x+16 }{ { \left( x\left( x+1 \right) \left( x+2 \right) \left( x+3 \right) \left( x+4 \right) \right) }^{ 3 } } } =\frac { 1 }{ 4{ (a!) }^{ b } } ...
10
votes
2answers
136 views

Number of ways to partition $40$ balls with $4$ colors into $4$ baskets

Suppose there are $40$ balls with $10$ red, $10$ blue, $10$ green, and $10$ yellow. All balls with the same color are deemed identical. Now all balls are supposed to be put into $4$ identical baskets, ...
6
votes
2answers
87 views

Given the set $A=\{1,2,\dotsc,14\}$, find all subsets of $7$ elements that sum to a multiple of $7$.

I would appreciate if somebody could help me with the following problem. Given the set $A=\{1,2,\dotsc,14\}$, calculate the number of distinct sets $M \subset A$ such that $|M| = 7$ and such that ...
3
votes
2answers
61 views

Find number of ways to seat $n$ boys and $n$ girls in a row so that every boy has atleast one girl sitting beside him.

My attempt: I am getting $2^n(n!)^2$ . First I paired $n$ boys and $n$ girls in $n!$ ways then these pairs can be arranged in $n!$ ways and in each of these pairs boy and girl can arrange themselves ...