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
12 views

How 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?

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 about ...
0
votes
1answer
23 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\...
1
vote
2answers
22 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_{...
1
vote
0answers
31 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
14 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
12 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
33 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
16 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
26 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
27 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
26 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
25 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
24 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
33 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
42 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
2answers
49 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.

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
37 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
22 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
43 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
1answer
21 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
65 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$. ...
2
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
49 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......$ $\}$, ...
0
votes
1answer
25 views

What is the probability that a random walk starting at 0 will reach +2 in 2 steps, 3 step, 4 steps, etc.? [duplicate]

The random walk I am referring to is a symmetric, unbiased, 1D random walk. In an answer given in the link below, the probabilities are given for S1, but I am trying to find out what it is for S2, ...
0
votes
1answer
42 views

Pigeonhole Principle: Showing that there are at least two holes with the distance between their centres less than $10\sqrt{2}~\text{cm}$

I'm having trouble regarding the application of the Pigeonhole Principle. I understand $f:A \to B$ but I don't know how to apply it in questions that require it. Example: Ten bullets are all shot on ...
0
votes
1answer
33 views

How is $\binom{2n}{n} \sum_{k=0}^{n}\binom{n}{k} \binom{n}{n-k}=(\binom{2n}{n})^{2}$ [duplicate]

I have been trying to make out how: $\binom{2n}{n} \sum_{k=0}^{n}\binom{n}{k} \binom{n}{n-k}=\binom{2n}{n}^{2}$ so in essence, showing that $\sum_{k=0}^{n}\binom{n}{k} \binom{n}{n-k}=\binom{2n}{n}$ ...
3
votes
3answers
90 views

How many solutions are there to $x_{1} + x_{2} + x_{3} + x_{4} = 15$

How many solutions are there to (I think they mean non-negative integer solutions) $x_{1} + x_{2} + x_{3} + x_{4} = 15$ where $1\leq x_{1} \leq 4$ $2 \leq x_{2} \leq 5$ $7\leq x_{3}$ $2\leq x_{4}$...
1
vote
2answers
49 views

How to obtain the identity $\sum_k\frac{(m-k)!}{(n-k)!} = \frac{(m+1-k)!}{(m+1-n)(n-k)!}$

Hereby $$\sum_k\frac{(m-k)!}{(n-k)!} = \frac{(m+1-k)!}{(m+1-n)(n-k)!} =: SOL(k)$$ is supposed to be similar to the way of writing antiderivatives. In complete form it should be like this: $$\sum_{k=a}^...
1
vote
1answer
30 views

How many ways to put kids in 4-seated benches when only one is fully taken

Was just thinking if my solution is correct. I have 60 kids, and 20 benches with 4 seats each - 80 different seats. While order in each bench is important, how many ways to place kids when only one ...
1
vote
2answers
47 views

What's the underlying combinatoric idea behind $(k-1)!\binom{n}{k}=\sum_{i=1}^{n-k+1}\frac{\left(n-i\right)!}{n-k+1-i}$?

According to my CAS the following identity holds: $$(k-1)!\binom{n}{k}=\sum_{i=1}^{n-k+1}\frac{\left(n-i\right)!}{(n-k+1-i)!}$$ Here we can set $$\left|\binom{\{1,..,n\}}{k}\right| = \binom{n}{k}$$ i....
1
vote
1answer
57 views

Product of binomial coefficients and interesting properties

I recently encounter the following quantity \begin{eqnarray} \frac{n^+!n^-!}{n!}\frac{k!}{k^+!k^-!}\frac{l!}{l^+!l^-!} \end{eqnarray} $n^\pm,n,k^\pm,k,l^\pm,l$ are all non-negative integers. There ...
0
votes
3answers
34 views

What is the Inclusion-Exclusion Principle for five sets?

Anyone know where I can find the Inclusion-Exclusion Principle for five sets? I tried to use google but found nothing. Inclusion-Exclusion Principle for 4 sets are: \begin{align} &|A\cup B\cup C\...
1
vote
4answers
42 views

Combinatorial proof for $\sum_{k=0}^p {p+q\choose k} {p+q-k\choose p-k}=2^p {p+q \choose p}$

I'm looking for a combinatorial proof of the identity: $$\sum_{k=0}^p {p+q\choose k} {p+q-k\choose p-k}=2^p {p+q \choose p} \text{ (1)}$$ I'm especially curious about its relationship with this ...
0
votes
0answers
31 views

How to show $1+c_n ^2-a_n ^2-b_n ^2\geq 0$?

$$c_n=(1-2t_n+2t_{n-1}-...+2t_1)~,~b_n=1-2t_j+2t_{j-1}-...)~,~a_n=(1-2t_i+2t_{i-1}...)$$ $0<t_1<t_2<t_3....<t_n<1$ and $j\in J$ and $i\in I$ and $I\cup J=\{1,2,3,...,n\}$ and $I\cap J=\...
0
votes
1answer
41 views

Number of ways to form a list from $\{1,2,3…k\}$ such that sum of the numbers is $n$, and one of the numbers is at least $d$. [on hold]

For example, $k = 3$, $n = 4$, and $d = 2$, So we have to form a list from$\{1,2,3\}$ such that sum of the numbers is $4$ and one of the numbers is at least $2$. Possible lists are $\{1,1,2\}$, $\{1,2,...
0
votes
1answer
23 views

Number of isosceles triangles formed with 12 equally spaced points lying on the circumference of a circle [on hold]

How many isosceles triangles can be formed with 12 equally spaced points lying on the circumference of a circle? The answer should be 52, but I have no idea how to solve it. Please help!
1
vote
1answer
30 views

How many integers between 2001 and 3000 inclusive are not divisible by any of the three prime numbers 3, 7 and 13?

I approached by finding the number of integers between 1 and 3000 inclusive and the number of integers between 1 and 2000 inclusive, finding the difference between these and subtracting it from 1000 (...