Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
1answer
29 views

How many ordered pairs $(A,B)$, where $A ,B$ are subsets of $\{1,2,3,4,5\}$, are there if |$A|+|B|=4$?

How many ordered pairs $(A,B)$, where $A , B$ are subsets of $\{1,2,3,4,5\}$, are there if $|A|+|B|=4$?
0
votes
0answers
9 views

N people are to be seated in a row. Four of them, A, B, C, and D cannot sit next to each other*. How many different sitting arrangements are possible?

N people are to be seated in a row. A, B, C, and D cannot sit next to each other*. How many arrangements are there? * No two of them can be adjacent * List item I thought of using the inclusion-...
0
votes
1answer
18 views

Maximal chains of nested subspaces

I need to answer the following question: Let $V_n(q)$ be $n$-dimensional vector space over $\mathbb {F}_q$ with $\mathbb{F}_q$ fields with $q$ elements. How many different maximal chains of ...
-1
votes
0answers
20 views

Count ways to form an $n$ digit number such that adjacent numbers are co-primes?

Eg. $X = 3$ (allowed digits $1-3$ and digit limit ($1-9$)) $N = 2$ $(12), (13), (11), (23), (21), (32), (31)$ ans $= 7$ I tried to calculate the answer but the complexity to find the answer is O(...
0
votes
0answers
13 views

Counting Nonempty Sets with Distinct Hitting Elements

If we can choose $k$ elements from $k$ given sets (exactly one element from each set) such that these elements are different from each other, we say these $k$ sets are "good". Let $f(n,k)$ be the ...
4
votes
2answers
46 views

Sum with Bernoulli numbers

How to prove that: $$\sum_{k=0}^n \binom n k 2^k B_k = (2-2^n)B_n$$ In this sum, $B_n$ is the Bernoulli number with $B_1 = -\frac 1 2$. Thanks for your attention!
0
votes
2answers
33 views

Determine the smallest number X such that…

Let $B = \{2, 3, \ldots , 50 \}$, where $B$ is the set of positive integers greater than $1$ and less than $51$. Determine the smallest number $x$ such that every subset of $B$ having $x$ ...
1
vote
2answers
18 views

Find the probability that no two among $A$, $B$, and $C$ are together when $12$ people are arranged in a circle

There are $12$ people including A,B and C. They are arranged in a circle. Find the probability that no two among A, B and C are together. I have solved problem where cases involving two person ...
0
votes
2answers
27 views

Number of distinct arrangements of the word $\text{MATHEMATICS}$

How many distict arrangements of the word $\text{MATHEMATICS}$ are there that contain no $A$'s in the first 7 spaces? I'm not quite sure how I would go about answering this. At first I thought I would ...
1
vote
1answer
29 views

Duration to guess password

I have been super stuck on this problem for a while and thought I turn to some expert help. My problem question: A password has length $8$ with a mix of $1$ uppercase letter (from $A$..$Z$), $5$ ...
1
vote
1answer
25 views

Subsequence Avoiding Sequences

An answer of mine disagrees with an answer in a math book I'm reading, and so I wanted to sanity check it to see if there's something obvious I'm missing. The book Foundations of Mathematical ...
2
votes
1answer
64 views

How many numbers with no common divisor are there?

There is quite general question. Let $A=\{1,2,3,...,n\}$ be a set. Calculate the following: $$W_{k}=\sum_{\substack{a_{1},...,a_{k}\in A\\ a_{i}\neq a_{j} \text{ if }i\neq j\\ \gcd(a_{1},...a_{k}...
0
votes
3answers
48 views

What's the number of natural solutions of the following equation :

$x_1 + 2x_2 + 3x_3 = n$ $x_1, x_2, x_3≥0$ Find a regression formula (or a recursive function, not sure how it's called in English) to calculate the number of solutions for all $n≥0$. Find the ...
0
votes
1answer
24 views

Is there a general formula for all the combinations of having at least a one in an N -tuple vector?

Let $x$=$[x_1 x_2 ... x_N]$, $x_i \in \{0,1\}$ and $\bar{x}_i = 1-x_i; \forall i$ and $\sum_m^N x_m$ not necessarily one (independent events) I'm trying to mathematically formulate the function g($...
6
votes
3answers
48 views

Number of onto functions from $Y$ to $X$ (JEE Advanced 2018)

Let $X$ be a set with $5$ elements and $Y$ be a set with $7$ elements. If $\beta$ is the number of onto functions from $Y$ to $X$ then the value of $\dfrac{\beta}{5!}$ is? My approach is: First I ...
3
votes
2answers
43 views

Prove identity $\sum^n_{k = 0} \binom {r+k} {r} = \binom{r+n+1} {r+1}$ using lattice paths

I am trying to prove the following identity $\sum^n_{k = 0} \binom {r+k} {r} = \binom{r+n+1} {r+1}$ by using lattice paths. My first approach was to draw the following scheme: Sketch indicating paths ...
0
votes
1answer
18 views

Total number of ways to arrange objects subject to constraint [duplicate]

Suppose that you are ticket collector in Cinema office. It cost 50 dollars to watch a movie. There are 20 people in line. 10 people in that line have exactly 100 dollar bills and 10 people have ...
0
votes
1answer
17 views

how many different words of length n over set A = {c, d,e, f,g, a,h} with exactly k occurrences of the character c?

how many different words of length n over set A = {c, d,e, f,g, a,h} with exactly k occurrences of the character c ? and how can i be able to solve those kind of problems ?
3
votes
1answer
57 views

Simplifying (and/or bounding) a sum of product of binomial coefficients

The question title is quite overused, but I hope I haven't duplicated something. Can this be simplified? $$\sum_{k=1}^{p} \binom{q-1}{k-1}\cdot\binom{n-1}{b-1+k-1}\cdot \binom{m-1}{a-1+k-1}$$ Edit: ...
-2
votes
1answer
31 views

How many subsets of {1, 2, 3, … 10} do not contain any pair of consecutive integers? [duplicate]

How would I solve this problem? Thanks in advance. Please just give the number for the answer instead of strategies, those are really unhelpful. If this is a duplicate please put a link for the ...
0
votes
1answer
16 views

Arrangements and Grouping

Find the number of ways in which a team of 3 men and 2 women can be selected from a group of 6 men and 5 women? Would the answer just be 6C3 x 5C2 ?
3
votes
2answers
36 views

How many ways can five people be arranged around a table if two people must sit together and two others must not sit together?

Imagine there are $5$ people around a round table: A, B, C, D and E. A and D must sit together. C and E must not sit together. How many different ways can they be seated? I know that with A and D ...
0
votes
3answers
29 views

How many possible groups can 6 people be divided into to sit in 3 different boats? [on hold]

So this was a statistics question in my A level math exam. I don't remember the exact wording but it went something like: 6 people are to sit in 3 boats. One of the boats can carry 3 people, one can ...
0
votes
2answers
18 views

Find number of different strings that can are formed from {a,b,c}

I need to find the number of different strings that need to be formed from {a,b,c} in which there needs to be at least one from each letter. The question is to find the number of strings with length 5....
0
votes
1answer
30 views

A string of odd and even numbers to group in three sets using combinatorics?

I need help with combinatorics problem. The task is this: There are 9 numbers which are: 1,3,5,2,4,6,8,10,12. I need to group these numbers in 3 sets with 3 elements in every set, but there is one ...
1
vote
3answers
35 views

In determining probability using 2 dice rolls why are permutations (x,x) not counted twice?

So I've been working in probability regarding dice rolls. I came across this problem: If you roll 2 dice, what is the probability the first die is a 6 given that you rolled an 8? This is clearly a ...
0
votes
1answer
40 views

$(a+b+c+d)^{10}$ expansion such that the powers are different from 2

We can rewrite the question as $x+y+z+w=10$ and $x,y,z,w \not=2$, how many integer values fulfill the condition ? i know how to solve the question when the constrain is $>$ and not $\not=$.
0
votes
0answers
35 views

Combinatorics: arranging $n$ balls in $k$ cell with condition

Im learning combinatorics, and I came across a question I couldn't find the answer to: I have $n$ identical balls and $k$ different cells, I want to find the number of ways to arrange the balls with ...
3
votes
2answers
24 views

Distinct Combinations of a word

An $11$ letter word has: $$4 \text{ A's}\\3 \text{ N's}\\2\text{ G's}\\ 1\text{ M}\\1\text{ T}$$ Find the number of distinct combinations of the word such that there are no A’s in the first six ...
0
votes
3answers
39 views

Coefficient problem in algebra

Find the coefficient of $ x^{8} $ in the expansion of $ (1+x^2-x^3)^{9} $ I know the problem is simple if we use multinomial theorem and I got an answer $ 378 $ using it. Can someone check it and ...
1
vote
4answers
43 views

If ${}^nP_{12}={}^nP_{10}×6$, than what is $n$? [on hold]

If ${}^nP_{12}={}^nP_{10}×6$, than what is $n$? I am at year 11. I do understand the concept of $^nP_r,{}^nC_r$. Once I know the $n$ I can calculate. I got stuck on this.
0
votes
1answer
43 views

How to find $R(4,3)$

How to find the Ramsey numbers?I am new in graph theory and I need help. By PHP,I have proved that $R(3,3)$=6.But I am finding difficulty when the numbers get bigger. Is their any particular method of ...
0
votes
0answers
22 views

Are these words legal in the Thue-Morse language?

We take the Thue-Morse word defined by the substitution $\sigma(0)=01, \ \sigma(1)=10$ on the binary alphabet. We consider the language $L_\sigma$ of $\sigma$-legal words, i.e. the collection of all ...
1
vote
2answers
28 views

How to find a generating function that has only coefficients $a_n \equiv 0~(mod~k)$ from the generating function for $\{a_n\}$?

I am trying to work through a few problems, and one asks to sum over the Fibonacci numbers which are even-valued (it is the Euler Project problem #2). I realized that (if we index like $\langle 1, 2, ...
0
votes
1answer
24 views

Probability that the given students are not sitting adjacent to each other

Please note that I am not looking for a complete answer, but only hints on how to start. If you want to add a complete solution to help others who might want to know it, please put it in spoiler tags ...
3
votes
1answer
37 views

Repeated incomplete Steiner Triplets

I'm not a mathematician, so I hope this question makes sense. As a hobby, I organize leagues for amateur volleyball teams. To minimize travelling costs the matches are played as small tournaments with ...
0
votes
1answer
31 views

How how many options are there to put the letters AAAABBBBCCCC (4 A, 4 B, 4 C) in a word so that there are at least 2 A next to each other?

how many option there are to put the letters AAAABBBBCCCC (4 A, 4 B, 4 C) in a word so that there are 2 A next to each other? for example AAAABBBBCCCC counts as an option. is there a way to think ...
1
vote
1answer
44 views

Inverse of a bijective function involving cases

In continutation to a question that i asked earlier and got answered here :Discretizing a mathematical equation This is a bijective mapping from the set of ordered tuples $(x,y,z)$ where each $x,y,z\...
2
votes
2answers
27 views

Anders, Bodil, Cecilia, and David shall receive 4 oranges. In how many ways is this possible if Anders should have at least one?

Anders, Bodil, Cecilia, and David shall receive 4 oranges. In how many ways is this possible if Anders should have atleast one? Correct answer: 29 My solution: How many solutions are there to $x_{...
2
votes
1answer
77 views

Ways of distributing passengers in ships

I need help with the following combinatorial problem. There are $ K $ passengers and $ K $ ships. The passengers are denoted by $ U_1, U_2, \dots, U_K $. The objective is to find in how many ways the $...
1
vote
1answer
24 views

Calculate the different apartment combinations

An apartment building is being divided up and converted into apartments. A large apartment takes up two stories of the building and a small apartment takes up one story of the building. Now I have ...
0
votes
0answers
16 views

Constructing monochomatic diagonal flag using $N \times 1$ flags that are colored using two colors

On some planet, there are $2^N$ countries$(N\geq4)$. Each country has a flag $N$ units wide and one unit high composed of $N$ fields of size $1 \times 1$, each field being either yellow or blue. ...
3
votes
2answers
37 views

Prove a sum of sums equals n choose k

In some research I'm doing, I've come across some coefficients I'm calling $\alpha^{n}_{j}$, where $$ \alpha^{n}_{j} = \sum_{k_1 = 1}^{n} \sum_{k_2 = 1}^{n-k_1} ... \sum_{k_j = 1}^{n - k_1 - k_2 -... -...
0
votes
1answer
18 views

Probability of Drawing Enough Numbers (Combinatorics)

Maybe you could help me with the following problem. Given a series of incremental numbers that is split in two, so $s = 1, 2, 3, ..., n_1$, $n_1 + 1, n_1 +2 ,..., n_2$. Also given a integer number $...
1
vote
2answers
32 views

Prove that every 3-regular (simple) graph has Vertex bipartition s.t. each vertex has at most deg=1 within partition class

Given a $3$-regular graph $G$, I want to show that I can partition the Vertex set into sets $A,B$ such that each vertex has at most one neighbor within its partition class. I have come up with two ...
2
votes
0answers
53 views

Combinatorial inequality in Erdös-Kac proof.

I am reading a proof of Erdös-Kac theorem, in Durrett, "Probability: Theory and Examples", fourth edition. In some point, it is stated that $(\sum_{m=1}^nEZ_{n,m}^2)^k - \sum_{i_j} EZ_{n,i_1}^2 . EZ_{...
1
vote
2answers
31 views

Calculating expectation and variance for having rolled 1 and 6 twice out of rolling a die 12 times

First i have calculated the probability to get each possible number $\{1,2,3,4,5,6\}$ twice from $12$ rolls ($A$). We have: $$Pr[A]=\frac{\binom{12}{2,2,2,2,2,2}}{6^{12}}.$$ Then there are 2 random ...
1
vote
1answer
19 views

Number of pairs of two numbers in a set - Math proof

I have a set of 11 numbers {0,3,6,9,12,15,18,21,24,27,30}. I am currently grouping numbers with a spacing of 9. I did this by hand - {0,9},{3,12},....{21,30} of total 8 pairs. The answer is 8. But I ...
0
votes
0answers
28 views

In how many outcomes can we get 5 balls in 10 balls in any order?

In order to enter the Lottery, you choose five different numbers in the range 1 to 53, and write them, in an order of your choice, on an entry form. ''' You win Prize 3 if your five numbers occur ...
0
votes
1answer
15 views

Inclusion-exclusion with anagrams

How many are the permutations of the letters of the word PROPOR in which are not consecutive letters equal? How to approach this problem through the principle of inclusion-exclusion?