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
2answers
15 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
27 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
2answers
19 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
38 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
31 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 ...
2
votes
2answers
18 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
38 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
5answers
38 views

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

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
35 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
20 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
27 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
22 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 ...
0
votes
0answers
17 views

Question on $\sum\limits_{\overrightarrow{k}}[d^{-n}\binom{n}{\overrightarrow{k}}]^{2}$

I am try to prove that for $d\geq 3$ the simple symmetric random walk on $\mathbb Z^{d}$ is transient. And in part of the proof, it is said without justification that: for $n \in \mathbb N$: $\sum\...
3
votes
1answer
26 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
40 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
25 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
59 views

How many different ways of distributing people in ships

I need help with the following combinatorial problem. There are $ K $ persons and an equal number of ships. The objective is to find in how many ways the $ K $ persons can be distribuited among the $ ...
1
vote
1answer
22 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
36 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
29 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
49 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
26 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?
0
votes
1answer
19 views

Play Cards Game Tournament Algorithm

I am currently trying to find algorithm to minimize the total time of a tournament. The game requires $2$ teams of $2$ players in each team (total $4$ players). Then, the perfect number of ...
0
votes
1answer
26 views

Inclusion-exclusion with distribution

In how many ways can we distribute $15$ different books to $15$ children (one for each one) then collect the books and again distribute so that no child will get the same book previously received? ...
0
votes
1answer
34 views

Principle of inclusion exclusion

In a class of 30 children, 20 studied Portuguese, 14 studied English and 10 studied French. If 8 study none of these 3 languages ​​and none study the 3 languages, how many children study English and ...
2
votes
1answer
46 views

University clubs - Counting two ways

Consider a university with 2000 male and 2000 female students. Suppose that none of the 4000 students signed up for 100 or more clubs (Each student signed up for at most 99 clubs). You also know that ...
0
votes
1answer
31 views

Areas of Applied Combinatorics

I love combinatorics, but do not really want to do pure math exclusively. I like the format of pure math (that is the theorem-proof-theorem-proof format), but would also like what to do research that ...
0
votes
0answers
18 views

Flipping coins - Counting in two ways [duplicate]

There are 100 coins, all of them showing heads. One turn consists of flipping exactly 93 coins (from heads to tails or the other way around). How many turns are needed so that all coins are showing ...
-1
votes
1answer
34 views

Is this a permutation or variaton or combination? [on hold]

The task is: You have two letters A and B, how you can order it with repetition ? I know the result is 2 x 2 but I have no idea what category is it. I've made some theory that it should be a ...
2
votes
1answer
51 views

Let $R,S \subseteq A \times A$ be transitive binary relations. If $R\circ S=S\circ R$ then $R\circ S$ is also transitive. [duplicate]

My attempt to prove is the following: Suppose $(x,a) \in R$ and $(a,y) \in S$, since $R\circ S=S\circ R$ then $(a,y) \in R$ and $(x,­a) \in S$. Suppose $(y,b) \in R$ and $(b,z) \in S$, since $(a,y) \...
0
votes
2answers
21 views

In how many ways can the votes of n voters be split among k candidates?

Suppose there are n voters and k candidates. In how many different ways can the vote be split among the candidates? To be clear,...
1
vote
2answers
38 views

Counting strategies Exam Question

How many different ways can people finish in i) a $4$ person race, ii) a $6$ person race, iii) a $10$ person race What I did: $4^4 = 256$ $6^6 = 46,656$ $10^{10}$ as there are $4$ people and ...
3
votes
2answers
28 views

Circular permutation with constraints

If four boys and four girls play tricks, how many ways can they join hands, provided that at least two girls are together? My plan is to determine the circular permutation of the eight (boys + girls),...
1
vote
1answer
34 views

Proof of $\sum_{k=n-1}^{n+p-1} {k \choose p}={n+p \choose p}$ using the equation $x_1 + x_2 + \dots + x_n = p$

So we consider the following equation: $$x_1 + x_2 + \dots + x_n = p$$ We dnote the set of solutions (lists of $\{0, \dots ,p \}$) by $A(n,p)$. If we write $p=1+1+\dots+1$ then the problem can be ...
2
votes
2answers
20 views

Wrong analysis in counting distinct balls into distinct boxes

Let's suppose I have 3 balls numbered 1 to 3 and 3 boxes numbered 1 to 3. I have here a case where I need to put 3 distinguishable balls into 3 distinguishable boxes. I know that I can count how many ...
3
votes
2answers
36 views

How many toys can be chosen?

There are 3 red, 5 blue, 2 yellow and 4 green toys in the box. In how many different ways can 6 toys be chosen if one of them should be blue and the other one - yellow? I came up with a solution but i ...
-1
votes
0answers
24 views

batch factoring

The table below illustrates a snapshot of results for a potential way to factor particular integers. Each C value denotes a particular "curve" of the method. The index value logged to the respective ...
2
votes
1answer
54 views

How many dismentals of set A exists?

Let A be a set, let n be a natural number and let $\langle B_0,B_1,...,B_{n-1} \rangle$ series with $n$ length of subsets of set A. We say $\langle B_0,B_1,...,B_{n-1} \rangle$ is dismental of set A ...
1
vote
2answers
27 views

How many ways can x and y people be arranged in z seats arranged in a circle? If z > x + y and y arrive after x

For the question How many ways can x and y people be arranged in z seats if z > x + y and y people arrive after x? I got (zCx)*((z-x)Cy) if we only want to count combinations, but (zCx)x!((z-x)Cy)y!...
2
votes
2answers
67 views

Seeking a closed expression for a combinatorial sum [on hold]

Is there a simple closed expression for the following sum? $$\sum_{i=0}^{\lfloor\frac n2\rfloor}{n\choose i}{n-i\choose i}$$ I can see that this is the constant term in $\big(\frac 1x+1+x\big)^n$. ...
0
votes
2answers
76 views

An Extension to a problem of IMO 1986 [duplicate]

To each vertex of a pentagon, we assign an integer $x_i$ with sum $$s=\sum x_i>0$$ If $x$, $y$, $z$ are the numbers assigned to three successive vertices and if $y<0$ , then we replace $(x, y, z)...
-2
votes
1answer
25 views

Ludo Competition Probability Problem [on hold]

Twelve competitors have entered a Ludo championship where 4 players can play at the same time. Each competitor is scheduled to play every other person once. How many games are scheduled for the ...
1
vote
1answer
22 views

Proof of $A_3(n)$ in Stanley's Enumerative Combinatorics Exercise 14, Chapter 2

The question is stated as follows: Let $A_k(n)$ denote the number of $k$-element antichains in the Boolean algebra $B_n$, i.e., the number of subsets $S$ of $2^{[n]}$ such that no element of $S$ is ...
-1
votes
0answers
50 views

Countability and Proof

An infinite set is $\textbf{countable}$ if There exists a bijective function from the naturals to set. Want to prove: Let A be an infinite set. A is countable $\iff$ $A=$ $\{$ $a_1,a_2......$ $\}$, ...