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

Number of translated cubes covering a given hypercube in $\mathbb{R}^n$

Let $\Omega \subset \mathbb{R}^n$ be open and bounded, and let $Q \subset \Omega$ be a hypercube. Furthermore, denote by $D$ the $n$-dimensional unit cube $(0,1)^n$. Let $k \in \mathbb{N}$ be big, ...
1
vote
2answers
986 views

The number of monomials of a given degree [duplicate]

I'm trying to understand why the number of the monomials of degree $d$ in $n+1$ variables is $C_{n+d,n}$. If someone could help me to remember how to solve this, I would be glad. Thanks.
0
votes
1answer
372 views

Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
1
vote
5answers
62 views

Proof $x$, $1+nx≤ (1+x)^n$ [on hold]

Prof using the binomial theorem: for all integers $n ≥0$ and for all nonnegative real numbers $x$, $1+nx ≤(1+x)^n$. Don't have a idea to start this one. I don't know how to use math induction yet, ...
1
vote
4answers
63 views

Number of monomials of degree $m$ [duplicate]

The formula for the number of monomials in variables $w,x,y,\ldots,z$ of degree $m$ (where e.g. $x^iy^jz^k$ degree $m=i+j+k$) is $$\binom{m+n-1}{n-1},$$ where $m$ is degree of monomial and $n$ is the ...
5
votes
2answers
716 views

Number of monomials of certain degree

Wikipedia says that the number of different monomials of degree $M$ in $N$ variables is $$\frac{(M+N-1)!}{M!(N-1)!}\; .$$ Can anyone explain why this is true?
10
votes
2answers
163 views

Using two coins to select a person fairly.

Good evening, I would like to know if the solution to this problem, I know it can be solved because it is from a Hungarian Olympiad. The problem is as follows: You need to fairly select a person ...
6
votes
1answer
489 views

Different Perspectives of Multinomial Theorem & Partitions

There are 2 important interpretations of the multinomial theorem and coefficients. 1: Determining the number of ordered strings that can be formed using a set of letters. For example, with 1 m, 4 ...
1
vote
0answers
22 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?
0
votes
0answers
32 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
25 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$? ...
8
votes
1answer
252 views

Hatcher 2.1.10…

Hatcher asked a question in chapter $2$ (a) Show the quotient space of a finite collection of disjoint $2$-simplices obtained by identifying pairs of edges is always a surface,locally homeomorphic ...
2
votes
2answers
39 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
72 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 ...
10
votes
2answers
160 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, ...
2
votes
1answer
52 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
1answer
39 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 $ ...
0
votes
1answer
37 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 ...
0
votes
1answer
22 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
2answers
40 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 ...
1
vote
1answer
37 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
1answer
18 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
0answers
9 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
47 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 ...
1
vote
0answers
15 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
69 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)} ...
2
votes
2answers
109 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 ...
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 ...
5
votes
4answers
66 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 ...
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 ...
-2
votes
2answers
54 views

Which is this series [on hold]

When m = 2, series is 1,2,3,4,5.. ...
0
votes
1answer
15 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
0answers
27 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
26 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.
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 ...
0
votes
0answers
30 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
1answer
36 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
2answers
441 views

Number of binary search trees on $n$ nodes of height up to $h$

How can I find the number of binary search trees up to a given height $h$, not including BSTs with height greater than $h$ for a given set of unique numbers $\{1, 2, 3, \ldots, n\}$? For example, if ...
1
vote
0answers
31 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
39 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
22 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
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
0answers
31 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 ...
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 ...
12
votes
3answers
469 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, ...
0
votes
1answer
99 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, ...
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
1answer
46 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
25 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 ...