Tagged Questions
This tag is for basic 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. ...
0
votes
0answers
5 views
How to find all maximal chains and antichains in a finite bounded lattice
Is there a (possibly efficient) algorithm to find all maximal chains and antichains in a finite bounded lattice?
1
vote
1answer
8 views
How many different eight note melodies within a single octave can be written if black/white keys alternate.
An octave contains 12 distinct notes(on a piano, five black keys and seven white keys). How many different eight notes melodies within a single octave can be written if the black keys and white keys ...
0
votes
2answers
16 views
A coke hand in bridge from deck of cards.
A coke hand in bridge is one where none of the thirteen cards is an an ace or is higher than a 9. What is the probability of being dealt such a hand?
Attempt: Suppose the thirteens cards are amoung ...
0
votes
0answers
11 views
Triples with even intersection
Let $\mathfrak M=\{M_1, \ldots , M_s\}$ be a collection of triples of natural numbers from $1$ to $n$, such that $|M_i \cap M_j| \ne 1$ (or, equally, $|M_i \cap M_j|$ even for $i \ne j$. How large can ...
0
votes
0answers
10 views
Claim regarding Stirling numbers of the first kind
Claim: $$\sum\limits_{m = k}^{n} s(n,m) {m \choose k} = s(n+1,k+1)$$
My attempt at a proof is the following:
I wanted to use induction and a particular recursive identity we have for these beasts -
...
0
votes
4answers
78 views
Prove that $(x + y + z)!$ is divisible by $x!y!z!$
I am posting this question for Abdo, who asked it but had it closed because some people thought it was unclear what he was asking. However, I understood what he was asking and was ready to answer. So ...
0
votes
1answer
22 views
Five cards selected out of 52 cards. Find probalbilty sum of the faces is 48 or more.
Five cards are dealt from a standard 52 card deck. What is the probability that the sum of the faces on the five cards is 48 or more?
Attempt: Five cards can be selected out of 52 cards by 52_C_5 ...
1
vote
1answer
28 views
What are chances that not all S's will be adjacent given a phrase at random.
IF the letters in the phrase A ROLLING STONE GATHERS NO MOSS are arranged at random, what are the chances that not all the S's will be adjacent.
Attempt: Given there are 6 letters that appear twice, ...
0
votes
3answers
16 views
Combinatorics/probability dinner party type problem
At a banquet, 9 women and 6 men are to be seated in a row of 15 chairs. If the entire seating arrangement is to be chosen at random, what is the probability that all of the men will be seated next to ...
0
votes
2answers
19 views
Lottery problem - Chance of 4 out of 5 balls matching?
In a lottery, an urn contains 40 balls that are numbered 1, 2, ..., 40. Each week, 5 balls are drawn from the urn without replacement. To enter, one chooses 5 numbers. Anyone who correctly predicts ...
1
vote
1answer
17 views
A bridge hand (13 cards) is dealt from a standard 52 card deck. Given events A and B, find $P(A \cup B)$.
A bridge hand (13 cards) is dealt from a standard 52 card deck. Let A be the event that the hand contains four aces. Let B be the event that the hand contains four kings. Find $P(A \cup B)$.
Attempt: ...
1
vote
2answers
31 views
Computing a large coefficient in a power series expansion
What is the coefficient of $x^{1000}$ in the power series expansion of
$$\frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{25})}?$$
This is the number of ways to break ten dollars into pennies, nickels, dimes, ...
4
votes
2answers
32 views
Number of Fibonacci series that contain a certain integer
In my question, I consider general Fibonacci sequences (sequences satisfying the recurrence relation $F_{n+2}=F_{n+1}+F_n$ independent of their starting value). Given two arbitrary different integers, ...
0
votes
1answer
28 views
Which combinatorics formula should I use for this question?
I know about four combinatorics formulas:
$$\begin{array}{lcc}
& \text{with ordering} & \text{without ordering} \\[5pt]
\text{with replacement} & n^k & \binom{n+k-1}{k} \\[5pt]
...
0
votes
1answer
14 views
Biggest consecutive block-repeating in a binary string
in a binary string like $S="01011010101010101110111101001"$ you can ask that what is the size of the biggest consecutive block-repeating. for example in $S$ we have bellow blocks:
$"1"$ : repeated 4 ...
0
votes
1answer
32 views
How to solve this *without* handshake theorem?
Suppose $45$ handshakes occurred in a room, how many people were in the room?
Someone asked me this question and I was going to answer him using graph theory and my knowledge of the number of ...
0
votes
1answer
16 views
Suppose that we have 4 white and 7 black balls - Probability Question [on hold]
Suppose that we have 4 white and 7 black balls in a bowl, and randomly select three of the balls. We are interested in knowing the probability that one of the balls is black and the other two white.
...
0
votes
1answer
27 views
Combinatorics Question Help; # of ways to choose 4 distinct officials from a city?
there are $n \ge 4$ people in a city. And the city has its officials, consisting of 1 mayor and 3 vice-mayors. The entire board consists of 4 distinct students. Prove that by counting. In 2 different ...
3
votes
3answers
54 views
divisibility of number of solutions of $x_1+\cdots+x_k=n$
I observed that the number of solutions in positive integers $x_1,\ldots,x_k$ of
$$x_1+\cdots+x_k=n$$
for fixed $k$ and $n$ is always a multiple of $k$ as long as $\gcd(k,n)=1$. For example,
...
0
votes
0answers
16 views
Bound for a quotient of two binomial coefficients
I need to find a function g(k), such that:
$$ \frac{\binom{u}{k}}{\binom{v}{k}}=\frac{u(u-1)...(u-k+1)}{v(v-1)...(v-k+1)} < (\frac{u}{v})^{k}.\frac{1}{g(k)} $$
We also know that $u<v$ and ...
2
votes
1answer
19 views
Compute Card$(\{(m_1,m_2,m_3)\in\{0,\cdots,75\}^3: m_1+m_2+m_3=75\})$.
This question arose from this one, Ewan Delanoy solved my problem. Now I just want to know how can I compute the cardinal of $$\{(m_1,m_2,m_3)\in\{0,\cdots,75\}^3: m_1+m_2+m_3=75\}$$ (curiosity).
Any ...
0
votes
0answers
24 views
Number of ways to shuffle a cardset with fixed top 4 while ignoring the suit
I am interested in the number of possible orders in a standard 52 card deck. There are $52!$ possible orders, if I care for suit and type. If I don't care for the suit / color of the card there are
...
0
votes
1answer
40 views
Finding polynomials question (combinatorics)
I have two generating series $F(x)$ and $G(x)$ such that $g_n=f_n+a_1f_{n-1}+\cdots+a_nf_{n-k}$ when n>=k are the coefficients of $G(x)$ and $f_n$ are the coefficients of $F(x)$. I need to find two ...
2
votes
2answers
52 views
Number of integer solutions to the equation $x_1 + x_2 + x_3 = 28$ with ranges
Find the number of integer solutions to the equation $x_1 + x_2 + x_3 = 28$, where $ 3 \leq x_1 \leq 9$, $0 \leq x_2 \leq 8$, and $7 \leq x_3 \leq 17$
I'm having problems with this question.
1) I ...
0
votes
0answers
33 views
counting the good numbers
We need to calculate Good Numbers in range from $A$ to $B$ (Both inclusive).
A number $N$ is said to be a good Number if it satisfy following conditions :
If we extract every $2$-digit number of $N$ ...
1
vote
3answers
27 views
Why is $1 \times 3 \times 5 \times \cdots \times (2k-3) = \frac{(2k-2)!}{2^{(k-1)}(k-1)!}$
In order to find out the Catalan numbers from their generating function you have to evaluate the product above.
Here is what I thought:
\begin{align*}
1 \times 3 \times 5 \times...\times (2k-3) ...
1
vote
0answers
22 views
Ordering objects with repetitions
Apologies if this has been asked before, but I honestly can't work out how to describe this succinctly so I can search for it.
I have two distinct objects, call them red and blue balls, and I have N ...
0
votes
0answers
38 views
Find a closed form for this relation [on hold]
How evaluate the sum $$\sum\limits_{k=0}^n\binom{2k}{k}\binom{2n-2k}{n-k}k^m$$
For m=1,2,3,4,5,...
GillesJ user 178256
1
vote
1answer
24 views
How many binary string are there such that there are no k consecutive characters are the same?
Given number $n$ and $k$. Count the number of string with length $n$ such that there are no $k$ consecutive characters are the same.
Example with $n = 3, k = 3$, the answer is $6$. ($110, 001, 101, ...
1
vote
0answers
14 views
Maximizing dot-product score by asking queries
Let $a>b>0$, and let $T=\{a,b\}^n$ be the set of all $n$-tuples each entry of which is $a$ or $b$. Let $X\subseteq\{0,1\}^n$ with $|X|>1$, and let $f:T\rightarrow X$ be a function. For each ...
2
votes
3answers
80 views
What is wrong with this calculation of $\binom{\frac{1}{2}}{k}$?
The reason I ask this question is that I want to show that:
\begin{equation*}
\binom{\frac{1}{2}}{k} = -2\frac{1}{k}\binom{2k-2}{k-1}\left(-\frac{1}{4} \right)^k
\end{equation*}
\begin{align*}
...
1
vote
1answer
48 views
How many ways different sets of values can be chosen for the $x_s$ , if $x_1 + x_2 + x_3 = 20$?
Your statistics teacher announces a twenty-page reading assignment on Monday that is to be finished by Thursday morning. You intend to read the first $x_1$ pages Monday, the next $x_2$ pages ...
0
votes
1answer
27 views
How many ways can a twelve member cheerleading be pair up.
Problem: How many ways can a twelve member cheerleading squad(6 men and 6 women) pair up to form 6 male-female teams? What might the number 6!6!2^6 represent? What might the number 6!6!2^6*2^12 ...
2
votes
0answers
25 views
Discrete Analogue of the Poincaré Conjecture and Simple Connectedness
I apologize if this question is badly worded or obvious, but I have no formal topology background. I have put some effort into trying to find something, but nothing turned up, perhaps due to my lack ...
1
vote
1answer
61 views
Prove this equality
I do not know how to make the LHS = RHS. I have tried $(36^n-26^n) = 10^n $ which is $x$ in the RHS, but I don't know what to do with the $26^{n-k}$ after I have gotten rid of the $26^n$ on the right. ...
0
votes
1answer
13 views
Proving overlap when distributing certain number of balloons to forty children.
Sorry for the title, couldn't think of a better way to phrase it. The problem is this:
Forty children go to a carnival. Twenty-five are given a blue balloon, 30 a red balloon, 35 a green, and 33 a ...
1
vote
0answers
19 views
Bijections of fixed point free involutions that preserve descents
$\omega \in S_n$ is an FPFI (fixed point free involution) (also called a matching) if $\omega^2 = 1$ and $\omega(i) \neq i$ for all $i$.
For $\omega \in S_n$, a descent occurs at $i$ if $\omega(i+1) ...
1
vote
2answers
51 views
Give a combinatorial proof to show the following for all integers $n \geq 2$.
$$2^{n-2} n (n -1) = \sum\limits_{k=2}^n k (k - 1) \binom{n}{k}.$$
I'm completely stumped. I just have no idea how to do this. What I've tried so far has been simplifying the right hand side slightly ...
2
votes
0answers
26 views
Books with probabilistic/combinatorial/graph theoretical methods to solve problems from other branches
I am searching for some books that describe useful probabilistic/combinatorial/graph theoretical methods to solve problems for other branches of mathematics, for example, elementary number theory, ...
2
votes
1answer
35 views
proving that the number of painting options is $\binom{n-k-1}{k-1}\cdot \frac{n}{k}$
$n>k\geq 2$ are integers.
Around a round table there are $n$ chairs: $n-1$ identical chairs and one taller chair.
We want to paint $k$ from $n$ chairs in red so that there won't be $2$ red ...
0
votes
0answers
13 views
Set family closed under symmetric difference
I have been looking for information on (finite) set families $\mathcal F$ such that if $X,Y \in \mathcal F$ then $X \,\triangle \,Y \in \mathcal F$.
Are these kind of families (possibly with extra ...
0
votes
1answer
20 views
Counting number of two pair hands in poker (not standard)
I was doing number counting problem and wanted to check if my result was correct.
Problem description:
From a standard deck of cards(52 cards, 4 suits, 13 numbers in each suit) there are 5 cards ...
0
votes
1answer
21 views
show existence of subsequence $\{a_{i_b}\}_b^{n+1}$
Suppose $\{a_n\}_{n=1}^{m^2+1}$ is a strictly increasing sequence of $n^2+1$ positive integers, show that there exist a subsequence $\{a_{i_b}\}_b^{n+1}$ of length $n+1$ such that $a_{i_k}$ is ...
0
votes
1answer
58 views
Please explain this explanation to me; Discrete Math: Counting
This is a counting solution to which selections of object which are not all distinct.
The basic premise is that the number of non-negative integer solutions to $x_1+x_2+x_3+...+x_k = n$ is equal to ...
0
votes
1answer
18 views
Number of ways for a k-letter word to have no repeat letters.
Assuming a standard English 26-letter alphabet, and $k<26$, what's the number of $k$-letter words where the letters don't repeat? So for example 'house' has no repeat letters, while 'rolls' has a ...
0
votes
2answers
26 views
Understanding a combinatorial relation.
I would like some insight as to why the following expression is true.
$$\sum_{i=0}^n {{n}\choose{i}} 2^{n-i} = 3^n $$
I arrived at this relation in solving a subset problem, and I understand the ...
0
votes
0answers
12 views
What is a combinatorial structure?
I keep seeing the phrase used but unlike with algebra, topology, measure, etc., it's not obvious what sort of "structure" allows combinatorics to be performed on a set.
0
votes
1answer
36 views
Where did I go wrong in this combanitorics question?
The question is as follows:
A fancy bed and breakfast inn has $5$ rooms, each with a distinctive color-coded decor. One day $5$ friends arrive to spend the night. There are no other guests that ...
1
vote
1answer
43 views
Find $a_{n}$ from a convolution formula
Suppose that $c_{n}$ satisfies the recurrence formula below: $c_2=\alpha$, and
$$c_{2n}+c_{2n-2}=\frac{(\alpha)_n}{n!},n\geq2.$$
were $(\alpha)_n = \alpha(\alpha-1)·\cdots·(\alpha-n+1)$ and $\alpha$ ...
0
votes
0answers
25 views
How to denote combinations of differences?
Let $ \mathcal{A} $, $ \mathcal{B} $ and $ \mathcal{C} $ be sets defined by $ \mathcal{A} = \{ A_k \} $, $ \mathcal{B} = \{ B_k \} $ and $ \mathcal{C} = \{ C_k \} $ where $ k \in \{1 , 2 , \ldots , ...
