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
2answers
13 views

How many 10-digit decimal sequences (using 0, 1, 2, . . . , 9) are there in which digits 3, 4, 5, 6 all appear?

So i was given this question. How many 10-digit decimal sequences (using 0, 1, 2, . . . , 9) are there in which digits 3, 4, 5, 6 all appear? My solution below (not sure if correct) Let $A_i$ = set ...
3
votes
1answer
20 views

solve for variable in combination

i have the combination ${n\choose 11}=12376$ and am looking to solve for $n$. it turns out to be $17$. of course can use brute force approach where just plug numbers in for $n$ but am looking for a ...
0
votes
2answers
25 views

What is the probability that when a deck of cards is shuffled and dealt, exactly 3 of the 4 aces will be dealt within the last 20 cards?

I am trying to figure out this problem, I think that it is a "permutations with repetition" type of question.
1
vote
2answers
28 views

Number of ways of selecting 3 numbers from $\{1,2,3,\cdots,3n\}$ such that the sum is divisible by 3

Find the Number of ways of selecting 3 numbers from $\{1,2,3,\cdots,3n\}$ such that the sum is divisible by 3. (Numbers are selected without replacement). I made a list like this: The sum of ...
1
vote
1answer
18 views

Give a recursion for the number h(n) of strings in S of length n.

Let S be the set of strings on the alphabet {0,1,2,3} that do not contain 12 or 20 as a substring. Solving this I got: $$ h(n) = 4h(n-1) - 2h(n-2)$$ with $h(0) = 1, h(1) = 4,h(2) = 14 $. When I did ...
2
votes
1answer
16 views

Probability: Finding the Number of Apples Given Two Scenarios

You have a bag containing 20 apples, 10 oranges, and an unknown number of pears. If the probability that you select 2 apples and 2 oranges is equal to the probability that you select 1 apple, 1 ...
1
vote
1answer
23 views

How many ways are there to place 10 distinct people within 3 distinct rooms with exactly 5 people in the first room and 2 people in the second room?

So I was given this question. How many ways are there to place $10$ distinct people within $3$ distinct rooms with exactly $5$ people in the first room and $2$ people in the second room? I have ...
0
votes
0answers
17 views

Looking for mathematical/combinatorial and computational explanation regarding adding values in a $5 \times 4$ (matrix?) with a constraint.

Given the following matrix (not sure if I should call it that): Matrix $5 \times 4$ I want to add all possible combinations of values such that each Horse gets but one value from each Bookie. What I ...
-2
votes
2answers
36 views

Number of words of length $n$ on the alphabet $a,b,c$ recurrence. [on hold]

Let $a_{n}$ be the number of words of length $n$ on the alphabet $a,b,c$ such that $b,c$ are not adjacent. What is the recurrence relation for $a_{n}$.
1
vote
0answers
17 views

Small tree containing smaller trees

Given $n$, what is the smallest number $N=N(n)$ with the property that there exists a tree on $N$ (unlabelled) vertices that contains a copy of every tree on $n$ vertices? That such $N$ must exist is ...
0
votes
1answer
18 views

Find the recursive definition for the number of strings on 0, 1, 2 avoiding the substring 012?

This is the question $a(n)$ the number of strings on $0, 1, 2$ avoiding the substring $012$ and the answer is $$a(n)=3a(n−1)−a(n−3)$$ with $$a(0)=1,a(1)=3,a(2)=9$$ My question is how to you get this ...
2
votes
3answers
52 views

Abstract Combinatorics

In a library there is a sequence of $n$ books. There is someone that never wants to take books that are neighborhoods of each other. How many possibilities are there, for him, to take $k\le n$ books? ...
1
vote
3answers
56 views

How many different integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 21$ with restrictions

So i was Given this question. How many different integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 21$ $0 \leq x_i \leq 9$? I just assumed it would be ${21+4-4-1 \choose ...
2
votes
2answers
17 views

Why use C(n,r) instead of P(n,r) when considering how many strings can be formed in which a specific letter appears before another specific letter?

I am dealing with a problem in which I must determine how many strings can be formed by ordering the letters ABCDE subject to the conditions given. The condition that I am given is that A appears ...
3
votes
0answers
20 views

Extremal set theory problem concerning translations of a set of integers

Let $A$ be a subset of $B = \{1, 2,\ldots,n\}$. Suppose that $F$ is a family of subsets of $B$, each of which is a translation of $A$ and no two of which intersect more than once. What is the maximum ...
0
votes
3answers
38 views

Combinatorics president and votes

There are 5 candidates for presidency and 11 people that can vote at most one of them (so they can decide not to vote). How many combinations of votes are there if no candidate can recieve more than 5 ...
0
votes
1answer
10 views

Expanding Restricted Compositions formula

I recently started to look into restricted compositions and I found a formula for a problem that I was trying to solve, the Formula E at page 441 of this document. In my case I have n =8, k=3, t=1 ...
1
vote
2answers
41 views

Proof $\dbinom{n}{0} - \frac{1}{2}\dbinom{n}{1} + \cdots + (-1)^n\frac{1}{2^{n-1}}\dbinom{n}{n-1}$

For all $n \ge 1$, $$\binom{n}{0} - \frac{1}{2}\binom{n}{1} + \frac{1}{2^2}\binom{n}{2} - \frac{1}{2^3}\binom{n}{3} + \cdots + (-1)^n\frac{1}{2^{n-1}}\binom{n}{n-1} = 0,$$ if $n$ is even               ...
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, ...
-5
votes
2answers
56 views

Given any 40 people, at least four of them were born in the same month of the year [on hold]

Given any 40 people, at least four of them were born in the same month of the year. Why is this true?
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, ...
2
votes
0answers
40 views

Counting integers from $1$ to $n$ with an odd number of divisors in {1,2,3,…,k}

Question Given $n,k$ find the number of integers between $1$ and $n$ that have odd number of divisors in {1,2,3,...,k} Example If $n=10$ and $k=3$, the numbers $1(1),5(1),6(1,2,3),7(1)$ have odd ...
1
vote
0answers
21 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?
2
votes
2answers
38 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
68 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
31 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
23 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
37 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
21 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
15 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
35 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
34 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
46 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
50 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
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
59 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
27 views

Proportional probability of payouts with defined expected value.

Assume we have a lottery with payouts $(2,3,5)$. So if you buy a ticket you can win a pot which will payout your ticket price multiplied by one of those numbers. The organizer expects a margin profit ...
0
votes
2answers
38 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
53 views

Which is this series [on hold]

When m = 2, series is 1,2,3,4,5.. ...
5
votes
4answers
63 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
26 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
43 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
25 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
33 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
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
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 ...