The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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.

Filter by
Sorted by
Tagged with
0
votes
1answer
9 views

Confusion with multichoose: choosing 9 elements from a pool of 2 with repitition. 2 multichoose 9 is 10, but the answer is $2^9$

Let's say we're looking for the number of 9-digit strings made up of only 1s and 0s. For each digit, we have two choices, so the answer is $2^9$. We can also think of this as choosing $9$ elements (...
1
vote
1answer
25 views

16 people around a round table

There are 16 people around a round table for a meeting. Every hour there is a new session. In each session, the people whose neighbors in the previous session are both sitting or standing will sit, ...
2
votes
1answer
47 views

Show that $G$ has a 4-colouring

Without using the four color theorem, prove that if $G$ is a planar graph such that every proper subgraph of G has a 4-coloring and such that G has a vertex of degree 4, then $G$ has a 4-coloring. I ...
0
votes
1answer
10 views

Combinatorics: Sitting Order Thought Process

Let's say we have a group of 7 children and 13 adults (each one is unique and can be picked once), and 20 chairs(each one is unique and can be picked once). Question 1) How to find the number of ways ...
0
votes
0answers
36 views

Find total number of non negative integral solutions $5a + 6b + 9c + 2d + e = n$ with constraints

We want to find the total number of non negative integral solutions with the additional constraint that $$a + b \geq c + d$$ The value of $n = \mathcal{O}(10^6)$ and $a, b, c, d, e \geq 0$ I could ...
1
vote
1answer
32 views

Points inside rectangle

Maybe someone can help with this problem: Inside a rectangle with sides 4 and 5 are given six points. Prove that the distance between some two points is less than 3. Thanks.
1
vote
1answer
56 views

Number Of Solutions (Find number of solutions)

Let $x_i \in Z$ , such that $|x_1| + |x_2| + \dots + |x_{10}| = 100$. Find number of solutions I think the answer is in the form of an alegebric summation instead of a number, right? If yes then ...
4
votes
1answer
1k views

Expected value when die is rolled $N$ times

Suppose we have a die with $K$ faces with numbers from 1 to $K$ written on it, and integers $L$ and $F$ ($0 < L \leq K$). We roll it $N$ times. Let $a_i$ be the number of times (out of the $N$ ...
1
vote
2answers
41 views

String numbers with $\{0,1,2\}$

My answer here is $405$... but Im wondering if my answer is correct or not. Any idea? QUESTION: how many string composed of 6 numbers can be formed from $\{0,1,2\}$ without having $(0,1,2), (1,0,2)$ ...
1
vote
0answers
117 views

Find integer $n$ modulo composite.

Suppose we want to find a positive integer $n < M$ where $M$ is a constant value of which we know a good approximation. For every prime $p$, an oracle gives us a set $B_p$ of residuals modulo $p$ ...
0
votes
0answers
12 views

A class of 46 form groups each of which contains exactly three members so that any two groups have at most one member in common. Prove that…

Students in a class form groups each of which contains exactly three members such that any two distinct groups have at most one member in common. Prove that, when the class size is $ 46$, there is a ...
0
votes
0answers
47 views

Five letters are to be chosen from the word 'TOADSTOOL'. Find the number of possible selections given that there should be at least 2 O's and 1 T.

Five letters are to be chosen from the word 'TOADSTOOL'. Find the number of possible selections given that there should be at least 2 'O's and 1 'T'. I had this question on my exams today and some ...
1
vote
0answers
24 views

Ways of ordering for a distinctive pack of cards

Suppose we have a pack of $52$ cards. Each card has a number from $1$ to $13$ and there are $4$ identical cards for each number. We are searching for the number of the different ways we can put those $...
1
vote
2answers
41 views

quick way to count

Suppose we have 10 sticks with length 1-10, respectively. Pick three from them, how many triangles can we form? I counted one by one and got 50. Is there a quick way? Any help would be appreciated.
0
votes
0answers
8 views

Assignment Problem that maximizes norm of sum of vectors

I have the following assignment problem \begin{align} \text{Maximize: }\quad &\left|\left|\sum_{i=1}^{n}\sum_{j=1}^{n} \boldsymbol{v}_{ij} x_{ij}\right|\right|_2^2\\ \text{such that: }\quad &...
4
votes
1answer
98 views

Find the number of different $10$ digit numbers having no digit repeated and divisible by $99$.

Find the number of different $10$ digit numbers having no digit repeated and divisible by $99$. Obviously the number is divisible by $9$ because $0+1+2+3+4+5+6+7+8+9=45$ and $45$ is divisble by $9$. ...
0
votes
1answer
13 views

Average frames to send

I am stuck on a problem. -- Question Source - Tannenbaum . Question : An upper-layer packet is split into 10 frames, each of which has 80% chance of arriving undamaged. If no error control is done ...
0
votes
1answer
27 views

How many species of regular 100-sided polygons are there?

I saw a resolution that showed the general case starting at $ n = 8 $. It has been found that the polygon species should be prime numbers relative to $ 100 $ and less than $ 50 $. Why should it be ...
-2
votes
1answer
20 views

Coding position of all possibilities. [on hold]

Let's consider partialy ordered set $$S=(\mathcal{P}_{k}(\{1,...,n\}),\le^{*})$$ Where $\mathcal{P}_{k}(\{1,...,n\})$ is set of all subsets of set $\{1,...,n\}$ so that each subset has cardinality $k$....
2
votes
2answers
113 views

Number of possible polynomials

Let $a,b,c,d$ be four integers (not necessarily distinct) in the set $\{1,2,3,4,5\}$. Find the number of polynomials of the form $x^4+ ax^3 + bx^2 + cx +d$ which is divisible by $x+1$. My Try: Let $...
0
votes
1answer
52 views

Expected value of $2$nd highest draw from uniform dist out of n draws

Jane wants to auction off an item, but does not know where to go to find bidders. David offers to find bidders for her, but will charge her $\$10$ per bidder he gets to show up. Each bidder will ...
0
votes
0answers
12 views

Cardinality of the set of elementary outcomes of a full dominos game when taking out a single domino

I am looking at an online course on probability, this is one of the questions. No knowledge of domino game rules is required to answer this question, only how the dominos look: [ | ], [ | 1], [ | 2], ...
0
votes
0answers
21 views

Find General Formula for Combinations about Blackjack

I was recently thinking about the following combination problem for pokers and I got stucked. Consider blackjack games, where Ace is either 1 or 11. Card 2~9 is just 2~9 and card 10, J, Q, K are ...
1
vote
2answers
187 views

$PGL_d(F)$ is 2-transitive but not 3-transitive if $d > 2$

An exercise asks to prove that: If $d > 2$, then the projective general linear group $PGL_d(F)$ of dimension $d$ over a field $F$ is 2-transitive but not 3-transitive on the set of points of the ...
3
votes
2answers
47 views

Number of natural numbers when multiplied having 1000 divisors

All natural numbers are coloured using $100$ different colours. Prove that one can find several (no less than 2) different numbers, all of the same colour, that have a product with exactly $1000$ ...
1
vote
1answer
119 views

Hierarchical digraph partition

Given a digraph, the following problem, informally, is to find a partition of its vertices into an ordered list of sets, such that the direction of edges connecting vertices in different sets ...
1
vote
1answer
40 views

Find the value of infinite series.

I'd like to find the value of $\sum_{n=0}^{\infty} \binom{2n}{n}(\frac{1}{12})^n$ And $\sum_{n=0}^{\infty} \binom{3n}{n}(\frac{2}{27})^n$. I've tried to use the identity $\binom {2n} n$=$\sum_{k=0}^{...
1
vote
3answers
21 views

Combinatorial reasoning behind Hypergeometric distribution

My textbook, Introduction to Probability by Blitzstein and Hwang, says the following when discussing the Hypergeometric distribution: Story 3.4.1 (Hypergeometric distribution). Consider an urn with ...
3
votes
1answer
32 views

Gaussian binomial coefficients, lattice paths, and vector spaces

The Gaussian binomial coefficient ${n+k \choose k}_q$ gives a probability generating function for the number of lattice paths from $(0,0)$ to $(n,k)$ enclosing an area $a$ in the upper-right quadrant ...
1
vote
2answers
24 views

What is the probability that 5 boys and 5 girls line up such that neither gender is in an uninterrupted block?

Just for reference, the exact question is: "Ten children (five boys and five girls) are standing in line. Assume that all possible ways in which they might line up are equally likely. What is the ...
0
votes
1answer
11 views

Number in boxes of different sizes

Let us consider that I have $1,2,\ldots,\log n$ many numbers. I do the boxing of the numbers as follows. In the first box put $1$ only, in the second put $2$ elements ($2$ and $3$), in the third box ...
0
votes
1answer
43 views

Exponential and Natural Log Power Series [duplicate]

I am asked to prove $$e^{Y\log(1+Z)} = (1+Z)^Y$$ using power series definitions for both the exponential function and natural log. I am really stumped on this. Our hunt was using the nth derivative ...
2
votes
3answers
41 views

How to split a set into two disjoint subsets in a special way?

Suppose $S$ is a finite set (the number of its members is not large). The set $\Sigma=\{s_1, \ldots, s_N\}$ is a set of subsets of $S$, i. e. $s_i \in S$. Is it possible to split $S$ into disjoint ...
0
votes
0answers
22 views

Is the Union-Closed Sets (Frankl's) conjecture still open for power sets?

I am an undergraduate and like reading about different math problems, and recently I have been reading about Frankl's Union Closed Sets conjecture. What is unclear to me upon reading about it is if ...
3
votes
0answers
30 views

How many commuting pairs of unitriangular matrices are there in $GL_{n}(F_{p})$?

I've been doing some work counting commuting pairs of unitriangular matrices over $GL_{n}(F_{p})$. So far, I believe that for $n=2$, there are $p^2$ such pairs, and for $n=3$ there are $p^5+p^4-p^3$ ...
18
votes
3answers
9k views

Show by combinatorial argument that ${2n\choose 2} = 2{n \choose 2} + n^2$

So i was given this question. Show by combinatorial argument that ${2n\choose 2} = 2{n \choose 2} + n^2$ Here is my solution: Given $2n$ objects, split them into $2$ groups of $n$, $A$ and $B$. $2$-...
2
votes
1answer
52 views

Number of subgroups of $\mathbb Z _m \times \mathbb Z_n$

Let $\mathbb Z_m$ denote the additive group of residue classes modulo $m$. Is there a closed form for the number of subgroups of $\mathbb Z_m\times\mathbb Z_n$?
1
vote
0answers
26 views

Is this selection with repetition?

While preparing for GMAT I came across one of the questions. I have been able to apply concepts to 4 out of 5 sub questions but even after spending a day trying to look for similar questions and ...
0
votes
0answers
17 views

Question about determining a sequence from equations.

I do some research about certain sequence. I would like to determine its values using only some equations, but first of all i wonder whether there is only one solution. Here is the problem: There ...
1
vote
2answers
131 views

Find $\lim_{n\to \infty}\mathbb{P}(N_{I}(n)=k)$ which is a random color point in interval

Divide the interval $[0,1]$ into $n$ equal-sized subintervals. Suppose that each endpoint of the intervals is colored red with probability $p_n=\lambda/n$ independent. For any interval $I\subset [0,1]$...
0
votes
1answer
42 views

what is the probability of $\mathbb{P}(Y=r)$ where $Y$ is the number of the colored coin

For the i.i.d Bernoulli processes $X_{i}, i=1,...,n$, which is $$\mathbb{P}(X_{i}=1)=1$$ ($X_{i}=1$ means the coin is head and $X_{i}=0$ is tail). Now adding another i.i.d Bernoulli processes $Y_i=1$ ...
1
vote
2answers
40 views

Greatest common divisor of all products of successive odd numbers of a given length

Let $n\geq 1$ and $f_n(x)=(2x+1)(2x+3)\ldots(2x+2n-1)$ ; so $f_n(x)$ is the product of $n$ successive odd numbers. Let $g_n$ denote the (positive) greatest common divisor of all the $f_n(x)$ for $x\in ...
4
votes
1answer
6k views

The number of words in which the relative order of vowels and consonants remain unchanged.

If as many more words as possible be formed out of the letters of the word $DOGMATIC$ then compute the number of words in which the relative order of vowels and consonants remain unchanged. Since the ...
1
vote
1answer
32 views

Find a recurrence relation for the number of distinct ways that a amount of $n$ cents can be made?

So we have 4, 6 and 10 cents and we can use that to make $n$ cents. In how many ways can we do that if order doesn't matter? so I tried to solve it and got $T(n) = T(n-10) + T(n-6) + T(n-4) - c$ it ...
0
votes
1answer
23 views

How to determine the amount of n possibilities of a word?

I am defining a word by a n character sequence. In English (for the purposes of my paper), I am assuming the following: The alphabet is only the 26 characters ...
-1
votes
0answers
53 views

Could we prove this relation by mathematical induction [on hold]

Could the following relation be proved using mathematical induction? $${n\choose r} + {n\choose r-1} = {n+1\choose r} $$ I get stuck at the induction basis when $n=1$, negative factorial starts to ...
7
votes
2answers
219 views
+100

Say $E_1,…E_n\subset\{1,2,…,k\}= K$, each $|E_i|=4$ and each $j\in K$ appear in at most $3$ sets $E_i$.

Say $E_1,...E_n\subset\{1,2,...,k\}= K$, each $|E_i|=4$ and each $j\in K$ appear in at most $3$ sets $E_i$. We choose from each $E_i$ one number. Prove that we can do that so that a set of all choosen ...
0
votes
1answer
19 views

Combination of weighted prices such that the sum equals a fixed price

I have a weighted prob question. How do you find the combinations of weighted probabilities whose sum is equal to a fixed number? For example: suppose you are given a basket of fruits that have ...
4
votes
1answer
67 views

Evaluation of sum $\sum\sum_{0\leq i<j \leq n}j\cdot\binom{n}{i}$

Evaluation of sum $\displaystyle \sum{\hspace{-0.3 cm}\sum_{0\leq i<j \leq n}}j\cdot \binom{n}{i}$ $\bf{My\: Try::}$ We can write it as $$\displaystyle 1\cdot \binom{n}{0}+2\cdot \left[\binom{n}{...
0
votes
1answer
21 views

Multinomial theorem problem

I am supposed to determine the coefficient of $$x^{2}z^{3}$$ of expression:$$(x+y+z)^{5}$$. What I did: $$\sum _{i=0}^{5}\binom{5}{i}x^{5-i}\left ( y+z \right )^{i}=\sum _{i=0}^{5}\binom{5}{i}x^{5-i}\...