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.

40,151 questions
Filter by
Sorted by
Tagged with
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 (...
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, ...
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 ...
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 ...
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 ...
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.
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 ...
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$ ...
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)$ ...
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$ ...
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 ...
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 ...
24 views

52 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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$-...
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$?
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 ...
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 ...
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]$...
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$ ...