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
0answers
10 views

references of discrete association scheme

I tried to find a book or paper to understanding discrete association scheme but I could not get any book for that. What is the good references for that?
1
vote
2answers
32 views

What is the probability that a psychic correctly “predicts” the outcome of at least 5 out of 10 coin flips?

Assume the psychic is actually just randomly guessing on each flip. The attempt: let E be the event in question number of outcomes per flip = 2 chance of correctly guessing the correct outcome = ...
0
votes
0answers
52 views

How many ways are there to choose one-half dozen donuts from $9$ varieties so that there are exactly $4$ glazed? [on hold]

How many ways are there to choose one-half dozen donuts from $9$ varieties so that there are exactly $4$ glazed? How should I approach this problem? Okay I think it's C(10, 2) because I already have ...
0
votes
0answers
24 views

Combinatorics: number of ways to choose $n$ distinct items from k boxes, each containing $s_i$ items?

Say there're $k$ boxes, each containing $s_1, s_2, s_3, \ldots, s_k$ objects; every object is distinct from another. I want to choose $n$ ($n \leq k$) objects, each from a different box (i.e. no two ...
0
votes
0answers
20 views

HW - Number of subspaces T of a vector space K containing a fixed subspace M.

Given a vector space $K$ of dimension $k$ over a finite field $\mathbb{F}_q$, what is the number of subspaces $T$ of dimension $t<k$ that contain a given subspace $M$ of dimension $m<t$? ...
1
vote
1answer
34 views

Number of ways to choose $k$ subsets such that $ B_1 \cap B_2 \cap \cdot \cdot \cdot \cap B_k = \emptyset$.

Let $ \space n,k \in \mathbb Z \space $ such that $1 \le k \le n \space$. Let $\space A=\{1,2,...,n\}$. Find the number of ways to choose $k$ subsets $\space B_1,B_2,...,B_k\space $ of $A$ such that $ ...
-2
votes
0answers
28 views

Different Ids on mars [on hold]

I am doing some exam questions - and I don't know the answer, can u show How to calculate it and what the answer is? The question: On Mars,each Martian alien, has an ID card with a unique string ...
0
votes
1answer
17 views

How many 13-card hands have at least one Jack, King, Queen, or Ace?

So with this question, I came to this math: I have a J, Q, K, and A in four suits, and after having one of those face cards in a hand, now we are left to choose 12 more cards. so then I figure we get ...
0
votes
1answer
12 views

How many mappings are there between these two graphs?

Let $P_{20}$ be a path of length 20 like so: $x_0$-$x_1$-$~\cdots~$-$x_{20}$ and $G$ a cycle of order 3. Allegedly there are $3 \cdot 2^{20}$ mappings $P_{20}\rightarrow G$, which I don't quite see. ...
0
votes
1answer
27 views

Alternate proof to number of monomials in a given degree - “more” rigorous, formal [duplicate]

Let $s$ be the number of variables and $n$ be the degree of the monomials we want to count in $R[X_1,\dots,X_s]$. Then show, that the count is $$\delta(n,s):=\binom{s-1+n}{s-1}.$$ The question ...
1
vote
1answer
32 views

How many ways can the team be created?

I am doing some old exam questions - and I don't know the answer, can some one calculate the result and show how you did it?
0
votes
0answers
8 views

Matching of points in two discrete linear sequences with potentially missing points

This is a question that I've been thinking about in my research lately. I've gone down the route of a few linear-optimization techniques, but nothing particularly spectacular has come up. Anyway, ...
-2
votes
3answers
45 views

Find the number of elements in $A \cup B \cup C$ if there are 50 elements in $A$, 500 in $B$, and 5,000 in $C$

I am given this: Find the number of elements in $A \cup B \cup C$ if there are 50 elements in $A$, 500 in $B$, and 5,000 in $C$ if: $A \subseteq B$ and $B \subseteq C$ The sets are pairwise ...
2
votes
1answer
49 views

Euler and Bernoulli Polynomial Identity Proof

Given that the Euler Polynomials $E_n(z)$ are defined in terms of the generating function $$\frac{2e^{xz}}{e^x+1}=\sum_{n=0}^\infty E_n(z)\frac{x^n}{n!}$$ and that the Bernoulli Polynomials $B_n(z)$ ...
1
vote
0answers
12 views

Rule of Product when choosing multiple items from sets

Suppose you have 4 sets, $S_{1}, S_{2}, S_{3}, S_{4}$ and you want to find out how many ways you can select a combination of A items from set 1, B number of items from set 2, C from set 3 and D from ...
1
vote
0answers
52 views

Sum involving binomial coefficient and gamma function

I was wondering if anyone has ever seen the following sum: \begin{equation} \sum_{j=0}^{n} \left(-1\right)^{j} \binom{n}{j}\frac{\Gamma\left(\mu+j\right)}{\Gamma\left(\mu+j+n+1\right)} ...
0
votes
2answers
23 views

total combinations of divisible sums of $3$

The first $12$ natural numbers are given. Two distinct numbers are selected. What's the probability that their sum is divisible by $3$? This looks very easy. I know answer is $1/3$ but in spite of ...
1
vote
0answers
24 views

Proportional probability of payouts with defined expected value.

Assume we have a lottery with payouts like this $(2,3,5)$ So you buy a ticket and you can win a pot which will multiply your ticket price by the numbers written ahead.The organizer expects a margin ...
0
votes
2answers
33 views

Number of monotonic ternary sequences of size $N$

I have ternary number. Its size is $N$. Monotonic sequence means every digit smaller or equal to the next digits in the number. $00122$ - legal monotonic sequence $1022$ - illegal What is the ...
-2
votes
2answers
51 views

Which is this series [on hold]

When m = 2, series is 1,2,3,4,5.. ...
5
votes
4answers
59 views

Combinatorial proof of summation of $\sum_{k = 1}^{n-1} {n \choose k}= 2^1 + 2^2 + 2^3 +\ldots+ 2^{n-1}$

I am looking for a combinatorial proof for it. I know how to prove it mathematically. Expanding $(1+x)^n$ and replacing $x$ with $1$ will give me the result but I am not able to explain it ...
1
vote
0answers
23 views

One dimentional random walk

I need to calculate the number of such trajectories of length $n$ (started at $0$ and end at $a$), that for giving $k$ substitute following rule: the maximum isn't greater than $a$, and for every ...
1
vote
0answers
30 views

Is it always possible to get MC/DC coverage on an $n$-input Boolean function with $n + 1$ test cases?

In software engineering, there is a coverage metric for testing called modified condition/decision coverage, or MC/DC for short. This metric is well-known in the avionics industry due to showing up in ...
1
vote
0answers
20 views

Show that any vertex $v$ of $P$ is half-integral.

Let $G$ be an undirected graph and define $$P=\{x \in R^{V}: x(u)+x(v) \leq 1 \:\:\text{for all edges}\:\: e=uv,\:\: x \geq 0\}$$ Show that any vertex $v$ of $P$ is half integral.
0
votes
1answer
32 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
21 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
29 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
37 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
18 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
27 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
43 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
27 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? [on hold]

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
20 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
25 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
41 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
24 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
51 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
27 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
40 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
91 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). ...
2
votes
1answer
41 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
53 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
43 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
35 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
35 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
28 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. ...