Questions tagged [combinatorics]
For questions about the study of finite or countable discrete structures, especially 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.
39,152
questions
-2
votes
2answers
39 views
How many bit strings of length $20$ have exactly two 1’s and do not contain 11 as a substring? [on hold]
I'm not sure how to solve this. I know there are $2^{20}$ strings.
-1
votes
2answers
36 views
Formal Power Series multiplication
Compute the value of $[x^n] x^k(1-x)^{-k} $
For some reason I don't understand formal power series multiplication.
Am i suppose to use the property of A(x)B(x) = $\sum_{i=0}^∞ a_i x^i$ * $\sum_{j=0}^...
0
votes
1answer
31 views
Problem with combinatorics
I had the following problem:
We have the word BORBOTTIO. Find:
All the anagrams
All the anagrams that starts with BB
All the anagrams where the same letters are close together.
The first two ...
0
votes
1answer
25 views
expectation of number of hands shaken at round table
There are $x$ people from country A and $y$ people from country B. They sit around a table and shake hands with people on their left and right, but they only shake hands if they're from the same ...
1
vote
1answer
30 views
Even coin tosses, 2 players
The game consists of a sequence of independent plays for each of the two players. Each round I have probability $p$ of making a point and my opponent has probability $1-p$ of making a point. (so each ...
1
vote
0answers
31 views
A conjecture on tiling
Here's the problem:
An $L-tile$ is the one which looks like this, and covers $3$ square units:
A A
A
Now we will define a term called an $L_k-good$ rectangles where $k$ is a nonnegative ...
0
votes
0answers
14 views
Minimum difference between two subsets
This problem feels very basic, however I could neither google it nor solve it satisfactorily:
Given a set of positive numbers $X \subset \mathbb{R^+}$, find the minimal nonzero difference between two ...
1
vote
0answers
17 views
Why is the “q-Pochhammer Symbol” referred to as such, despite not being a q-analog of the Pochhammer symbol?
The q-Pochhammer symbol (for $k>0$): $(a;q)_k = \prod\limits_{j=0}^{k-1}\left(1-aq^j\right)$
The Pochhammer symbol / rising factorial: $(a)_k = \prod\limits_{j=0}^{k-1}(a+j)$
The falling ...
1
vote
1answer
19 views
Finding the general recursive formula to divide the pot fairly
In a game where each turn is made up of the roll of a die, player E gets one point when the die is even, and player O gets one point when the die is odd. The first player to accumulate 7 points wins ...
0
votes
1answer
21 views
Finding a good bound for a quadratic and exponential expression of integers
Suppose you have two collections of $k$ positive integers, $a_{1},\ldots,a_{k} \in \mathbb{N}$ and $b_{1},\ldots,b_{k} \in \mathbb{N}$. Suppose you have bounds on the sum $\sum_{i=1}^{k} a_{i} \leq A$...
1
vote
0answers
63 views
Equality like Pascal triangle
I have noticed the following is true.
Let's denote the equation below as (1)
$$\sum_{k=1}^{d+1}(-1)^{d+1-k}\frac{1}{(d+1)(k-1)!(d+1-k)!}\prod_{i=1}^{d+1}\Big(\frac{q}{h}+(k-i)\Big)\prod_{j=k}^{d+1}\...
3
votes
2answers
87 views
How many different 7-digit numbers there are with exactly two “8” and three “4”?
How many different 7-digit numbers there are with exactly two "8" and three "4"?
It is worth noticing that a number can not start with "zero", so:
0044488 is not a possible 7-digit number. This is a ...
0
votes
2answers
69 views
If you shuffle a deck of cards and then someone then shuffles it again is the deck more shuffled?
So we are having a discussion with my friends. One is saying that if he shuffles a deck of cards x amount of times and then somebody else shuffles it again, the deck after the second shuffle is more ...
1
vote
1answer
46 views
Win with positive probability implies there exists a strategy to win for sure?
Assume there are two players A and B who play a game on a finite game board (you can imagine it is some chess game or the position game. The key point is the total number of feasible sequences of ...
0
votes
1answer
16 views
What algorithms are there to partition graphs into bounded-diameter sets?
I'm working on a project in which I have a large graph, and I want to break it into clusters of nodes. Connected components turned out to be too loose a restriction, so I want to impose a diameter ...
0
votes
0answers
12 views
Recurrence Relation for the number of binary trees of order n [duplicate]
Looking to make a recurrence relation for the number of different binary trees of order n.
Some initial conditions
$a_0 = 1, a_1 = 1, a_2 = 2, a_3 = 5$
Say that I have a tree of order n, I have my ...
2
votes
1answer
44 views
Pigeonhole Problem: Prove that a subset's sum is divisible by 10
Given a sequence of $10$ integers, show that there is a subset of consecutive integers whose sum is divisible by $10$
Suppose I have subsets
$$\{a_1\}$$
$$\{a_1,a_2\}$$
$$\vdots$$
$$\{a_1,a_2,a_3,...
2
votes
0answers
69 views
Smallest number not expressible using all of the first $n$ powers of $2$ (once each), with $+$, $-$, $\times$, $\div$, and parentheses?
Motivation
Solution to this problem is a lower bound for a more general problem.
Problem
Given first $n$ powers of two: $1,2,4,8,16,\dots,2^{n-1}$ that all need to be used exactly once per number ...
1
vote
1answer
22 views
How many ID numbers exist? - check my solution
"An ID number is created as follows:
The first part must consist of at least one letter and at most of four letters (the alphabet is assumed to have 26 letters). The second part must consist of at ...
1
vote
0answers
16 views
Prove that the total number of ingredients in all $n$ divisions is equal $\sum _{k=0}^{n-1} P(k)r(n-k)$
Let $r(m)=\sum _{d|m} 1$ which is number of positive dividers $m$ and $P(a)$ which is number of possible divisions of $a$. Prove that the total number of ingredients in all $n$ divisions is equal $\...
0
votes
1answer
14 views
Different soccer pairings in quarter finals - check my solution
"How many different pairings are possible in the quarter finals of a world cup where 32 teams participate in?"
Is my solution correct?
Let $\Omega:=\{\{\omega_1, \omega_2\}\times \{\omega_3, \...
1
vote
1answer
39 views
Counting the number of ways to divide into teams - complicated
$n$ students are standing in a row. Teacher must divide them into smaller teams - it could be one team or more - (team must consist of students standing next to each other in a row) and choose in ...
0
votes
4answers
33 views
Combinatorics problem: How many ways this row can be filled?
A row measuring $N$ units in length has $M$ red blocks with a
length of one unit placed on it, such that any two red blocks
are separated by at least
one grey square. How many ways are there to ...
1
vote
0answers
50 views
How many conjugacy classes of subgroups of order $p$ does $\operatorname{GL}_{3}(\Bbb Z / p\Bbb Z)$ have?
It is well known that any two subgroups of order $p$ in $\operatorname{GL}_{2}(
\mathbb{Z}/p\mathbb{Z})$ are conjugate. Then there is one possible
semidirect product of the form $$(\mathbb{Z}/p\mathbb{...
4
votes
0answers
35 views
Marbles of different colors in a row.
We have 10 red marbles, 6 green and 5 blue (marbles of the same color are identical) and want to arrange them in a row in such a way that there are not any consecutive green marbles. In how many ways ...
0
votes
0answers
59 views
Winning strategies for games on the natural numbers
Define $$F=\{(l_n, k_n)_{n=1}^t: t,l_n, k_n \in \mathbb{N}, l_1<\ldots <l_t, m_1<\ldots <m_t\}.$$ Suppose that I have a collection $G\subset F$, which is a set of ''good'' sequences.
...
7
votes
2answers
183 views
Why does a bijection from a set to itself deserve the name “Permutation”?
Sorry for the long text; this is a nebulous question that has always been in the back of my mind, and I've had trouble putting into a short form.
"Natural" Definition
If someone on the street hears ...
0
votes
1answer
35 views
Compositions of a large integer
Let's say $n$ is the number of integers and $t$ is their sum and we want to find all the combinations of number $t$, such that there are $n$ components. See https://en.wikipedia.org/wiki/Composition_(...
0
votes
0answers
29 views
Combinatorial proof of a binomial identiity [duplicate]
Could anyone advise me how to prove the following using combinatorial proof?
$$r\left(\begin{array}{c}n\\ r\end{array}\right)= n\left(\begin{array}{c}n-1\\ r-1\end{array}\right), r \geq 1$$
Hints ...
0
votes
1answer
32 views
Explicit formulas for Stirling numbers of the first kind?
I am solving this problem:
What are the coefficients of particular powers of $x$ in polynomial $x*(x-1)*(x-2)*...*(x-k+1)$?
I know, how to start, how to get a recurrence relation, but I do not ...
0
votes
2answers
36 views
Number of integers less than $20000$ that contain digits $4$ or $7$ or both
What's the best way of finding the number of positive integers less than $20000$ that contain the digits $4$ or $7$ or both?
5
votes
2answers
103 views
Distinct balls into distinct boxes
We have $n$ distinct balls ($n>7$) and want to randomly (and independently) distribute them into $N$ distinct boxes ($N>n$) which are placed one next to the other.
a) What is the ...
1
vote
1answer
58 views
What is the number of possibilities to choose $~80~$ numbers out of the set $~\{10,11,\cdots,99\}~$ with repetition and no order significant
What is the number of possibilities to choose 80 numbers out of the set $~\{10,11,\cdots,99\}~$ with repetition and no order significant.
In which if an element that divides by $10$ with no Remain of ...
4
votes
1answer
41 views
Given $N$ different elements, how many different Possibility there are to Push and Pop all the elements to\from stack
Given $N$ different elements, how many different possibilities there are to Push and Pop all the elements to\from a stack?
In the beginning, the stack is empty and every element can be pushed to the ...
3
votes
2answers
42 views
Throwing a die three times - check my proof
"A teacher rolls a 6-sided die (numbers from 1 to 6) three times. The lowest number will be the grade of the student.
Calculate the probability of each grade."
My approach is:
Firstly we determine ...
0
votes
2answers
48 views
Probability & Combination. N pairs of shoes in closet.
7 pairs of shoes (i.e., 14 shoes) are in a closet. 4 persons whose shoes are among the 7 pairs randomly selected 2 shoes each from the closet.
What is the probability that exactly 2 persons selected ...
2
votes
3answers
69 views
Discrete Mathematics - Combinatorics proof
$\\$ I need to prove $\displaystyle\sum\limits_{k=0}^n\left(\frac{ 1^k+(-1)^k}{2}\right)\cdot\left(\begin{array}{c}n\\ k\end{array}\right)4^k=\frac{5^n+(-3)^n}{2}$
my Attempt below
$\displaystyle\...
0
votes
0answers
50 views
This question is based on basic counting. [duplicate]
How many 10- digit numbers containing digits 1,2&3 can be formed such that the first & the last digits are same and no two consecutive digits are same?
1
vote
0answers
29 views
Number of 3 colorings on grid with constraints [duplicate]
I am trying to figure out a way to do the following:
Given a $3 \times n$ grid, ($n \geq 2$) choose coloring by using $3$ colors (say, RGB), such that
any given column cannot have all grids of same ...
1
vote
1answer
76 views
Equation involving sum of binomial coefficients.
Solve for $x$ if $$\sum_{i=0}^{16} {16 \choose i} 5^i = x^8$$
Not sure what to do here. Should I somehow use the binomial theorem to manipulate this to solve for $x$, or is there another approach ...
0
votes
0answers
33 views
selecting numbers from the group [on hold]
What is the number of options for selecting 80 numbers from the group
{10.11 .... 99} with repetitions and no matter how orderly, each number that divides by 10 without residual is taken at least ...
2
votes
0answers
15 views
Bijective mapping to fixed image set
I need to reduce the amount of stored data in an Ethereum Smart Contract. Currently I am storing $n < 2^8$ strings in a mapping (i.e. a map data structure) and each string is mapped into $[0, n)$; ...
4
votes
2answers
32 views
How to get the bar and star formula?
I have this statement:
Prove the bar and star formula for positive integers $\binom{n-1}{k-1}$
My attempt was:
Imagine I have a certain equation:
$x_1 + x_2 + ...+x_k=n$
Now, i have:
$\...
1
vote
2answers
43 views
How many combinations of three dice given as a product an even number
I want to know how many combinations of three dice given as a product an even number. If these dice are different from each other the answer would be $6^3- 3^3$. What about if these dice are equal to ...
0
votes
0answers
24 views
Minimising the intersection of a collection of subsets of a set
This question specifically refers to a previous discussion from this website, namely, minimizing the intersection of three sets.
As per that discussion, let us consider a finite set N, and a finite ...
1
vote
1answer
33 views
Limitations on the difference of coprime composites less than $n^2$ for ascertaining primality?
Let $q$ be a prime where $n < q < n^2$.
Let $p_1, p_2, \ldots, p_k$ be all the primes $\leq n$.
Is it true that for any $q$, you can find two numbers $a,b$ where $a+b=q$ or $a-b=q$, such that $...
4
votes
0answers
19 views
Asymptotic Gilbert-Varshamov Bound Using Hilbert's Entropy Formula
I am reading Walker's book Codes and Curves and am having trouble proving this Lemma regarding the Asymptotic Gilbert-Varshamov bound.
Suppose that $q$ is a prime power and we define \begin{align*}
...
-1
votes
1answer
59 views
How many bit strings of length 20 have exactly five $1$’s and do not contain $11111$ as a substring? [on hold]
Recall that a bit string is a string composed of characters $0$ and $1$.
Can someone explain how the answer is:
${20\choose5} - 16$?
2
votes
1answer
77 views
Finding number of cycles in permutation corresponding to translation in a group [University Olympiad]
here is a question from our university olympiad practice manual which is intended to help us prepare for upcoming inter-university math Olympiad.
I think I can see, solution would be similar to Proof ...
1
vote
1answer
44 views
Commutative extension to Catalan's problem
Another question asks for the number of ways to multiply n matrices.
Matrices, however, are a rather special case, because although we are allowed to place parentheses in an arbitrary fashion without ...
