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.

0
votes
0answers
9 views

Linear Combinations of Solutions to a Search Problem

Let $P_1=(X_1,U_1)$ be a search problem with the domain of search $$X_1=\{x \in Z_2^n | wt(x)\leq k\}$$ and the set of admissable tests be $U=Z_2^n$ (where $wt(x)$ is the hamming weight of $x$). ...
0
votes
1answer
24 views

Proof of combinatorial set [duplicate]

How to give a combinatorial proof from $$\sum_{i=1}^n {n\choose i}^2={2n\choose n}$$ I have tried to give an argument with 2n set elements colored red but i got stuck on this Thanks in advance
0
votes
0answers
6 views

On the mod 2 inner product between an unbalanced 0-1 vector and a random m choose d 0-1 vector

There are $m$ balls with $(0.5-p)m$ black balls and others white, and we randomly select $d$ balls without replacement. What is the probability that an odd number of black balls are selected? While a ...
1
vote
1answer
27 views

Permutations of the word $\text{TRIANGLE}$ with no vowels together.

First of all, $\text{TRIANGLE}$ has $8$ distinct letters, $3$ of which are vowels($\text{I, A, E}$) and rest are consonants($\text{T, R, N, G, L}$). While attempting this, I came up with the idea of ...
1
vote
1answer
30 views

Selecting people to form a team of 6 from 8

The question says: We wish to select $6$ people from $8$, if the person $\text{A}$ is chosen, then $\text{B}$ must be chosen. In how many ways selections can be made? If we need to keep $\text{A}$...
1
vote
0answers
10 views

Expected maximal degree of vertice in uniform spanning tree

Inspired by this I am curious how to evaluate expected maximal vertices degree in uniform spanning trees. I am not able to add comments, therefore I had to ask a new question. Misha We can also ...
0
votes
1answer
16 views

Number of elements in the set of invertible lower triangular matrices over a finite field

Problem: Let $F_q$ be a finite field with $q$ elements. $T_n(F_q) := \{ A = (a_{ij}) \in F^{n \times n}$ | $a_{ij} = 0$ for $i < j,$ and $a_{ii} \neq 0$ $\forall i \}$. Determine ...
1
vote
2answers
43 views

Is this a counterexample for the Erdös-Szekeres Theorem?

As I understand, the Erdös-Szekeres theorem says that for every sequence $a_1$,$a_2$,...,$a_{n^2+1}$ of $n^2+1$ real numbers, there is a subsequence of length $n+1$ which is either increasing or ...
1
vote
2answers
44 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$?
1
vote
1answer
27 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 I thought I would first calculate all cases in ...
0
votes
1answer
22 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 ...
0
votes
1answer
31 views

Count ways to form an $n$ digit number such that adjacent digits 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
18 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 ...
5
votes
2answers
58 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
39 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
21 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
32 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
43 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
28 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
70 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}...
1
vote
3answers
57 views

What's the number of natural solutions of $x_1 + 2x_2 + 3x_3 = n$?

$$x_1 + 2x_2 + 3x_3 = n, \qquad x_1, x_2, x_3 \geq 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$. ...
0
votes
1answer
25 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
50 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
44 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
20 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
64 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
33 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 ...
4
votes
1answer
45 views
+50

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
57 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
28 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
80 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
17 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. ...