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.

Filter by
Sorted by
Tagged with
0
votes
1answer
20 views

Distribution of items among two people, from PSS by Arthur Engel.

The following question is from Arthur Engel's Problem-Solving Strategies: $2n$ objects each of three kinds are given to two persons, so that each person gets $3n$ objects. Prove that this can be done ...
0
votes
0answers
20 views

Find number of matrices $B$ with no common row and no common column with a given matrix $A$

We are given a matrix $A$ with $n$ rows and $n$ columns and it's elements are $1,2,...,n^2$ (each element appears once). Find the number of matrices $B$ whose elements are $1,2,...,n^2$ that does not ...
0
votes
1answer
27 views

Number of Combinations for a Password

I am looking to find how many combinations of an $8$-$10$ character password there are with the following stipulations: $1.$ There must be at least $1$ lower case letter. $2.$ There must be exactly $...
0
votes
1answer
39 views

Permutations on circular table so that i cannot go to i or i+1.

Suppose $n$ objects are placed in a circular table in clockwise order. Find the no of permutations where $i$ cannot go to $i$ or $i+1$. i.e. $1$ cannot be mapped to $1$ or $2$, $2$ cannot be mapped to ...
-1
votes
0answers
15 views

Finding minimum disjoint sets from a collection of overlapping sets

I have multiple sets which have overlapping elements. e1, e2, e3, e4 e7,e9,e10 e1,e4 e2,e7 e3,e9 e10,e11,e12 e11,e12 I want to divide the above sets such that ...
6
votes
2answers
200 views

Walking on an infinite grid

I am sure someone has asked a similar question already, but I wasn't able to find it. So lets get started: We have an infinite grid with coordinates out of $ \mathbb{Z} $. Lets say the first ...
1
vote
0answers
42 views

Is there a closed form for the recurrence with $N(r,1)=N(r,r)=1$ and $N(r,c)=cN(r-1,c)+N(r-1,c-1)$ for $1<c<r$?

I'm trying to find if there is a closed form solution to the recurrence relation (where $1 \leq c \leq r$): $$ N(r,c) = \left\{ \begin{array}{lll} 1, & \text{if} & c=1,r, \\ c N(r-1,c) + N(r-...
0
votes
0answers
89 views

Project Euler #239 Java [closed]

A set of disks numbered 1 through n are placed in a line in random order. What is the probability that we have a partial derangement such that exactly k prime number discs are found away from their ...
2
votes
1answer
68 views

Probability that “abcdef” appears without “abcd” and “cdef”

Suppose there is a random character generator which generates each character (from "a" to "z") with equal probability $\frac{1}{26}$. We generate characters and concatenate them to form a string until ...
1
vote
0answers
24 views

Problem about when a person can definitely win a game of painting cells in a table.

There is a natural number n given and a table with 2n x 2n cells, which are all white. A and B play the following game. First A paints m of the cells in red. Then B chose n rows and n columns and ...
0
votes
1answer
35 views

Combinatorics and Latin squares

Let's have two Latin squares, in this case, the two which are shown in this question. If we superimpose them we get 34 different combinations, with two repetitions, namely 4B and 1E. Can someone find ...
2
votes
1answer
48 views

Combinatorics Question - Boys selecting candies from a bowl

I'm seeking help with solving this problem. There are two boys: Mike and Dan. There is a lady with a bowl containing $7$ different candies (e.g: M&M, Kitkat, etc.). The lady tells the boys that ...
1
vote
2answers
41 views

Find the probability of getting the second ace as the $n^{th}$ card is picked from $52$ cards.

Cards are drawn one by one at random from a well shuffled full pack of $52$ cards. Find the probability of the second ace being the $n^{th}$ card. For this what I did was, for the $n-1^{th}$ ...
1
vote
1answer
45 views

Let $A$ be a set of $n$ residues $\pmod{n^{2}}$. Prove that there exists a set $B$ of of $n$ residues $\pmod{n^{2}}$ …

Let $A$ be a set of $n$ residues $\pmod{n^{2}}$. Prove that there exists a set $B$ of of $n$ residues $\pmod{n^{2}}$ such that $A + B = \{a+b|a \in A, b \in B\}$ contains at least half of all the ...
0
votes
2answers
24 views

problem on division among persons. [closed]

In how many ways is it possible divide $6$ identical blue , $6$ identical green and $6$ identical red items among $2$ people such that each gets equal number of items. I tried but I do not get any ...
3
votes
2answers
98 views

In how many ways can $14$ people be seated in a row if there are $8$ men and they must sit next to one another?

In how many ways can 14 people be seated in a row if: a.) there are 7 men and 7 women and no two men or two women sit next to each other? My attempt: Since no two men or women can sit next to each ...
1
vote
0answers
22 views

Can this recurrence be simplified?

Let $A$ be the set of elements $\{0,1,2,\dots,n-1\}$ and $B_i=\{T(i,1),T(i,2),\dots,T(i,k)\}$ be the subset of $A$, which represent $i$-th combination without repetition of elements of the $A$. Then ...
4
votes
1answer
50 views

Erdos-Turan theorem for normal subgroups?

Suppose $G$ is a finite group and $N \triangleleft G$. Let’s define the relative commuting fraction as $$cf(G, N) := \frac{|\{(g, h) \in G \times H| [g, h] = e\}|}{|G||H|}$$ Does there exist such $\...
2
votes
1answer
32 views

Distribute $13$ identical balls in $6$ cells. Find the number of distributions such that at least $10$ balls will be in the first 3 cells together

Let $13$ identical balls be distributed in $6$ cells. Find the number of distributions in which there are at least $10$ balls in the first $3$ cells together. My attempt: First I'll divide into ...
4
votes
0answers
68 views

Source for MODERN combinatorial topology

I have basic background in algebraic topology (Up to and including homology chapters of hatcher). I recently saw a couple of papers that seem very interesting- https://arxiv.org/pdf/math/0312482.pdf ...
1
vote
1answer
45 views

Count Subsets of size less than equal to k [duplicate]

This is a variation of question asked on this site before. Consider a set with $𝑎_1$ 'distinct' 1s, $𝑎_2$ 'distinct' 2s, ... , $𝑎_𝑛$ 'distinct' ns. You have $𝑎_1+1$ choices for the 1s (including ...
3
votes
3answers
54 views

How to find effective partition of $n$ into $k$?

Here is a type of question that I find quite often on MO sites, that I couldn't quite solve: How many ways can I put $n$ identical balls into $k$ identical boxes, with $n>>k$, such that each ...
0
votes
1answer
297 views

distinct sequence

We are given a group of distinct K characters. Now we have to construct a sequence of length N such that: No two consecutive positions contains same character The odd position in the sequence can ...
-4
votes
2answers
44 views

How to count the number of subsets of a set with property 'X'? [closed]

We are given a set of positive numbers. How to count the number of subsets of size $<='k'$ which have all distinct elements in it ? It is guaranteed that the given set of numbers have atmost 1000 ...
0
votes
1answer
19 views

Number of three-digit even numbers with no repeat condition.

I have to find the total number of three-digit even numbers where no digit can be repeated. I tried and got answer $9 \times 9 \times 5$, but it is wrong. There is something weird with $2$ digits. I ...
3
votes
1answer
54 views

What is the cardinality of the result of concatenating two languages?

Question: The cardinality of an n-fold Cartesian product upon a language $L$ is simple: $|L|^{n}$. Is there a simple solution to the cardinality of language concatenation? For example, is there a ...
1
vote
1answer
33 views

Number of r-tuples with integer entries in a given interval

This is probably an easy question, but I couldn't figure it out. Let $n$ and $r$ be positive integers with $n \geq r$. Then the number of elements of the set \begin{align} \{(a_1,a_2,...,a_r) : 0 \...
0
votes
0answers
23 views

Prove that a condition is false for a 3 elements subset of given subset of a group

On a math competition the students were solving n problems and every student solved three problems. For each pair of students there is at most one problem solved by both of them. Prove that if $s$ is ...
0
votes
0answers
45 views

Flea jumping 5units on the x-y plane

A flea starts at the origin of the xy-plane and makes three jumps. Each time the flea jumps 5 units and lands at a lattice point (that is, a point with integer coordinates). How many different final ...
2
votes
1answer
68 views

If there are 20 students in a class, in how many ways can a professor give out $4$ A's, $3$ B's ,$4$ C's, and $9$ F's?

If there are $20$ students in a class, in how many ways can a professor give out $4$ A's, $3$ B's ,$4$ C's, and $9$ F's? What I did was use the binomial theorem: $\frac{20!}{4!\cdot 3!\cdot4! \...
3
votes
2answers
99 views

How many ways can $2$ different history books, $5$ different math books, and $4$ different novels be arranged on a shelf if …?

This is my first class in probability so I just wanted verification as to my attempted solution. Question: In how many ways can $2$ different history books, $5$ different math books, and $4$ ...
4
votes
0answers
50 views

“Non-trivial” solutions to equal products of consecutive integers

$\bullet\ \textbf{Question}$ One can find equivalent products of consecutive integers such as $$8\cdot9\cdot10\cdot11\cdot12\cdot13\cdot14=63\cdot64\cdot65\cdot66.$$ Other solutions of this have been ...
1
vote
1answer
22 views

Urn without Replacement, all balls the same

There's an urn with 12 balls: 5 white, 7 black. 4 balls are picked without replacement. What are the odds that all balls picked are white? I know part of the answer involves the term $\frac{7}{12}*\...
0
votes
0answers
77 views

$200n$ diagonals are drawn in a convex $n$-gon. Prove that one of them intersects at least $10000$ others.

$200n$ diagonals are drawn in a convex $n$-gon. Prove that one of them intersects at least $10000$ others. Attempt: Choose at random and uniform a diagonal with a probability $p={1\over 200n}$ and ...
2
votes
1answer
34 views

An upper bound of the girth of a simple graph with $n$ vertices and $n+1$ edges

An answer is $\lfloor(2n+2)/3\rfloor$ and I was asked to prove it. I am new to graph theory and I really have no idea how to relate girth with the number of edges in a graph. The next problem is to ...
1
vote
0answers
27 views

Reference request on “Simplicial” sets with all maps instead of only monotone ones.

Let $[n]=\{0,\dots,n-1\}$, $[0]=\emptyset$ and $\Sigma_{mn}$ be a set of all maps from $[m]$ to $[n]$, ($\Sigma_{0n}$ consists of a single map and $\Sigma_{no}=\emptyset$ for all $n>0$). Also let $[...
-2
votes
0answers
23 views

How many non-bingo combinations are there? [closed]

In a 5x5 game of Bingo, how what is the maximum number of squares you can fill in without winning? How many different ways can you arrange this number of squares on a 5x5 grid without winning, such ...
1
vote
2answers
26 views

How many ways can a tennis player be scheduled to play $4$ matches in $8$ days, with at most one match per day?

Should I use combinations or permutations? How many ways can a tennis player be scheduled to play $4$ matches in $8$ days, with at most one match per day? Currently, I work mostly in combinatorics ...
3
votes
2answers
84 views

How many numbers are between $1$ and $9999$ in this case?

How many natural numbers between $1$ and $9999$ have the sum of the digits: $a)$ equal to $9$. $b)$ equal to $16$ My atempt: So for $a)$, I did $\dbinom {9+4-1} {4-1} = 220$ For $b)$, I ...
0
votes
0answers
20 views

Putting Entries in Young Diagram to make Tableaux

I was reading the book on Young Tableaux by Fulton. On first page of notations, he defined Young diagram to be left justified rows of boxes, weakly decreasing downwards. Then, he defines Young ...
3
votes
0answers
61 views

Formula for the $j$th base-$n$ digit of $n^{d+1}-\sum_{i=1}^{n}i^d$

Let $k,n,d \in \mathbb{N}$ and $n>1$. Converting $k$ in a base $n$, $$k = (n_{ l} ~ n_{l-1} ~\cdots~ n_j ~\cdots~ n_2~ n_1)_{n} \quad\text{where}\quad n_{l} \ne 0$$ if $$k = n^{d+1} - \sum_{...
3
votes
0answers
57 views

Combinatorics on a string of letters

Define a word to be any distinct rearrangement of $AAAABBBCCDE$. There are four $A$'s, three $B$'s, two $C$'s, one $D$, one $E$. (a) How many words have all the $B$'s together? (b) How many words ...
3
votes
0answers
48 views

How many 10 digit numbers begin with (652)- and contain no zeroes?

I'm slightly confused, but I answered it as $9^7$. My reasoning is that the area code isn't relevant to how many numbers are possible, which leaves it as $7$ digits with $9$ possibilities each (since ...
0
votes
0answers
35 views

Upper bound for event occuring N times without another event occuring

I needed to compute an upper bound for a probability that I think is small but can't quite prove it. Let's say I have a sequence of events of lenght M, all independent, and with probabilities: $A : ...
-4
votes
1answer
72 views

How many digits in the sequence 1,2,4,8,16,…,2^150? [closed]

I know how to calculate number of digits if the sequence is linear growth, for exmaple, 3,6,9,...,3333 3,6,9 --> 1*3 = 3 digit 12,...,99 --> 2*((99-12)/3+1) = 60 digit 102,...,999 --> 3*((999-102)/...
0
votes
1answer
25 views

Probability that exactly $r$ tables are occupied if $k$ people randomly select a table

There are $n$ tables with infinite capacity. Each of the $k$ guests randomly (with uniform distribution) and independently select a table to sit next to. What is the probability that exactly $r$ ...
2
votes
3answers
51 views

Incorrect combinatorics reasoning

There are $5$ cows, $8$ roosters, and $10$ pigs on a farm. The farmer wants to pick $4$ animals, and at least $1$ needs to be a cow. He asked his (alleged) prodigious son Smarty how many ways it can ...
0
votes
1answer
32 views

Arranging the $26$ English letters in a row given two constraints

In how many ways can we arrange the $26$ English letters in a row so that no two vowels are adjacent to each other, and each block of consonant(s) (between $2$ vowels) is/are in alphabetical order?...
0
votes
2answers
41 views

Number of arrangements of the letters of the word NEEDLESS in which the three E's are together but the two S's are separated

Find the number of ways in which all eight letters of the word NEEDLESS can be arranged if the three Letters E must placed together and the two letters S must not be placed together? What I have ...
0
votes
1answer
53 views

Subspace equipped with combinatorial structure?

Given a vector space with tensor structure $V\otimes V\otimes V....\otimes V$, it is naturally (at least for us people doing many-body physics) to think that its subspaces are also equipped with some ...