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
1
vote
0answers
25 views

Probability that the picked hand will have at least one sequence in a game of Rummy with two standard decks

QUESTION: The game of Rummy is usually played with two standard decks of cards each containing 52 cards.Both of the deck contain four suits -hearts(h), diamond(d),club(c) and spade(s) comprising of ...
-2
votes
0answers
18 views

Combinatorial Proof Question [on hold]

Combinatorial Proof Question I know I need to count strings with n entires, where each entry must lie in {0,1,2}. Just need further hint.
0
votes
0answers
10 views

Paths from source to destination in directed bounded in-degree bipartite graphs?

Given $n$ vertex $m$ edge bipartite graph on condition that each vertex has in-degree at most $1$ (out-degree unbounded) is there upper bound on number of paths between a source and a destination?
0
votes
1answer
60 views

If 8 (indistinguishable) blackboards are to be divided among 4 schools, how many divisions are possible if each school must receive 2 blackboards?

I attempted to come up with a solution. Please verify that it is correct or explain if there is anything wrong with it. Solution: Since each school must receive exactly 2 blackboards, we draw the ...
0
votes
3answers
69 views

Divide 10 kids into 2 teams of 5 [on hold]

Given 10 kids divide into team A and team B of 5 kids each. Ans. (10!)/(5!5!) Given 10 kids divide into teams of 5 each. Ans. (10!)/(5!5!2!) Why? What's the difference
1
vote
1answer
67 views

Prove $\binom{2n}{n}\geq\frac{4^n}{2n}$ [duplicate]

I want to prove that$$\binom{2n}{n} \geq \frac{4^n }{ 2n}$$ I tried to solve with Stirling formula and got to $$\binom{2n}{n} \geq C*\frac{4^n}{ 2n}.$$ I'm not sure how to continue since $C$ could ...
4
votes
1answer
107 views

Throw 40 dice and arrange them in a row - check my proof

Assume you throw $40$ dice and arrange them in a row so that you got a $40$-tuple. Then you throw antoher die. The result of this die indicates the number of the starting die of the $40$-tuple. E.g. ...
2
votes
1answer
52 views

How to prove $[x^n]C^m(n)=\binom{2n+m-1}{n}-\binom{2n+m-1}{n-1}$

Recently I founded that $$ [x^n]C^m(x)=\binom{2n+m-1}{n}-\binom{2n+m-1}{n-1} $$ where $C^m(x)$ means the $m$-th power of the generating function of Catalan numbers, that is $$ C(x)=\frac{2}{\...
0
votes
0answers
38 views

okay a very common problem is the number of arrangements of letters such that no two vowel letters are adjacent [duplicate]

what i want to know how the solution to this problem makes the answer valid how we are sure that every time we choose using ncr the vowels will not be adjacent okay i will provide a problem with ...
1
vote
2answers
46 views

Perfect matching for a particular type of bipartite graphs

Let $G = (V_1 \cup V_2, E)$ be a connected and bipartite graph such that: (1) The number of vertices of $V_1$ is equal to the number of vertices of $V_2$, i.e., $|V_1| = |V_2| = N$ for some $N \in \...
0
votes
1answer
30 views

Inclusion exclusion involving distribution.

This question was in my book in the inclusion-exclusion principle section. I really don't see how to apply it here. Any tips? A candy maker distributes 3 types of coupons in the packages of Breakfast ...
2
votes
2answers
47 views

Probability of N consecutive characters in a row

I want to find the probability of a specify substring will occur in a string of random characters. Just simplify the question with numbers. 5 numbers are drawn randomly from 1 to 5 independently. The ...
5
votes
2answers
60 views

Box with chocolates probability

I am given a box with 20 chocolates, all of them identical from the outside but 5 of them are with cherry filling, 7 with cream and 8 with nuts. I ate 10 at random. What is the probability I ate at ...
0
votes
1answer
28 views

Stars and Bars Reference

Essentially what stars and bars framework allows us to do is to draw one to one correspondents between sets $$\left\{ (x_1,x_2,\ldots ,x_n)\; \colon \; \sum_{i=1}^nx_i=t, \ x_1,x_2,\ldots ,x_n\in \...
2
votes
3answers
48 views

A question about weights [on hold]

I have a question, but I'm not sure if this question is for this group or another ( I seem to remember there's another group for this kind of questions though ): A guy has $100$ stones, and they're ...
2
votes
1answer
39 views

N person picks K slots from a pool of total S slots, what's the probability of conflicts

Suppose there are $S$ slots in a cluster and $N$ individuals would pick $K$ slots each randomly from $S$. What's the expectation of the number of conflicts (each slot can only be picked by at most 1 ...
4
votes
3answers
430 views

Why isn't $26^6 - 24^6$ the number of possible permutations of the alphabet without “a” and “b”?

The question is "How many strings of six lower case letters from the English alphabet contain the letters $a$ and $b$?" Why doesn't $26^6 - 24^6$ work? $26^6$ is all the possible permutations of $...
0
votes
0answers
23 views

Is there a closed form expression that gives, for a integer n, the number of the first row of pascal triangle that has some entries higher than n?

I'm interested in finding a closed formula for the index of the first row of the triangle that contains an integer greater than $n$. Alternatively: What is the dimension of the smallest hypercube ...
2
votes
3answers
54 views

In how many ways can 20 persons be seated round a table if there are 9 chairs?

The problem given is in the title: In how many ways can $20$ persons be seated round a table if there are $9$ chairs? I tried solving it as follows: I can fix one person to one of $9$ chairs. I ...
0
votes
3answers
75 views

Probability of throwing every throw is larger than the previous one for a dice.

Suppose there is a 10 sided die, and we throw it 5 times. Then, to obtain each throwing being larger than the previous one, the first roll must be less than or equal to $6$. If $6$ is the first roll,...
3
votes
1answer
23 views

Some relations between multi-trace combinations

I recently checked a relation between three $2 \times 2$ matrices $\mathrm{A,B,C}$. $$\text{tr (ABC)}+\text{tr (ACB)}+\text{tr(A)tr(B)tr(C)}=\text{tr(A)tr(BC)}+\text{tr(B)tr(AC)}+\text{tr(C)tr(AB)}$$ ...
0
votes
0answers
12 views

bivariate frequency over product of both marginalized frequencies

Say that I have two random variables $(X, Y)$. The joint frequency $f(X=x,Y=y)$ tells me how many times they get a given value $(x^*, y^*)$ contemporary. This is clear to me. Say now that I define ...
3
votes
3answers
82 views

Derive a Combinatorial Identity

An urn exists with $x$ red balls and $y$ green balls. Draw $n$ balls without replacement. Derive a combinatorial identity for nonnegative integers $n$, $x$, and $y$, satisfying $1 \leq n \leq x + y$ ...
0
votes
0answers
36 views

How many ways can letters of BANANAS be arranged such that B and A are always beside each other? [on hold]

I solved it like (6!·2)/(2!·2!) = 360. Am I missing out some important details, my answer just doesn't seem right.
2
votes
1answer
43 views

Bijective proof of a combinatorial recurrence

This question is inspired by one asked yesterday. What is the number of cyclic permutations of $[n]$ with no number followed by it's successor? ($1$ is counted as the successor of $n$.) Matthew ...
0
votes
1answer
33 views

There are 16 chess players, how many games occur, if every player should play against another each one time?

My thought was, that we have in general $16 \cdot 16$ games and then we should subtract $1+2+3+4+\ldots 16$ from it because if you take for example the first game: player $1$ has $15$ opponents, if ...
0
votes
1answer
32 views

In how many ways can 2k people be seated on a table such that there are n couples, and each couple must sit together?

Edit: The table is ROUND. By sitting together, I mean that the husband and wife must sit together. I think we should first fix one husband, giving us two options for the wife. We should then ...
0
votes
0answers
24 views

Generating Function for Weighted Words

I'm interested in computing a generating function for words made from an alphabet of 3, say $\{x_1,x_2,x_3\}$ letters with a certain set of rules. If a given letter in the word $x_1$ is followed by ...
0
votes
1answer
28 views

Roll Dice Cash a day maximiz returns [on hold]

You roll a dice each day for a total of ten days. On each day, you have the option of me giving you the amount you rolled in cash. That is, on day 2, if you roll a 5, and choose to cash that day, I ...
-1
votes
0answers
24 views

Filling a 5*5 grid. [closed]

A 5x5 array is to be filled with numbers from 1 to 5 such that, no number is repeated again in the same row or same column. How many such arrangements are possible?
-1
votes
0answers
28 views
0
votes
0answers
37 views

How to split three woman and seven men into two 5-person groups

Three woman and seven men split into two 5-person. We wish to form the groups so that each group has at least one woman and at least one man. In how many ways can the women be divided? In how many ...
4
votes
1answer
39 views

Conjugacy classes in free groups

Let $F = F_k$ be a free group of finite rank $k$. The length of a conjugacy class is defined to be the word-length of a shortest representative. Given a number $n$, how many conjugacy classes of ...
0
votes
2answers
41 views

Distributing $n$ candies to 3 people with restriction

Thor, Captain America and Spiderman split $2001$ candies among themselves. Due to seniority perks, Thor must get strictly more candies than Captain America, who must get strictly more candies than ...
-2
votes
1answer
31 views

Indexes of disjoint sets

Let's call an index of a set $A$ a function $$I_A(x) = \begin{cases} 0 &\quad x \notin A\\ 1 &\quad x \in A \end{cases}$$ Now, suppose $A$ and $B$ are two disjoint sets. Is it always true ...
0
votes
3answers
55 views

Please help to untangle very difficult probability problem.

There are three sacks filled with stones of three colores - black, white and grey. The first sack contains 21% of black stones, 31% of white ones, the rest are grey. The second sack contains 41% of ...
1
vote
1answer
25 views

Calculating the minimum number of extra votes a presidential candidate would need to flip an election

I was pondering today whether U.S. presidential elections could be quantified in closeness by the smallest number of extra votes the losing candidate would need to add to select states in order to win ...
2
votes
1answer
63 views
+50

Distributing identical objects between distinct groups with limited capacity: Gaussian approximation

Consider the problem of counting the number of ways one can distribute $k$ identical objects between $g$ distinct groups, such that no group has more than $c$ objects. The solution of this counting ...
1
vote
2answers
29 views

Number of bit strings of length four do not have two consecutive 1s

I came across following problem: How many bit strings of length four do not have two consecutive 1s? I solved it as follows: Total number of bit strings of length: $2^4$ Total number of ...
0
votes
0answers
40 views

How many ways can 1…32 balls be placed inside 8 distinct boxes where each box has a capacity of 4?

The question asks that you can have a range of different number of indistinguishable balls from 1 to 32. How many ways are there to distribute them inside 8 distinct boxes? Each box has a maximum ...
0
votes
0answers
17 views

Combinatorial Argument for $n+1 \choose k+1$ [duplicate]

I'm trying to think of a good combinatorial/counting argument for $n+1 \choose k+1 $= $n \choose k $+...+$k+1\choose k$+$k\choose k$, but for whatever reason it's just not clicking for this one. For ...
0
votes
0answers
16 views

number of ways of selecting n balls from m buckets with each having different number of balls [duplicate]

Imagine you have been given n different colored balls and a task to choose at most k balls from them such that none of the same colored balls is selected for any given sequence and considering same ...
0
votes
0answers
14 views

Proving weaker version of Stirling's approximation?

I am trying to prove that, $$\lim_{n \to \infty} \frac{n!}{n^{n + 1/2}e^{-n}} = C$$ (i.e. a weaker version of Stirling's approximation.) Let \begin{align*} d_n &= \log[\frac{n!}{n^{n + 1/2}e^{-n}...
0
votes
3answers
71 views

Group $n$ numbers in $\mathbb{R}$ into $k$ clusters

Let $x_1\leq x_2\leq...\leq x_n$ be a sequence of real numbers in $\mathbb{R}$. If we want to group the numbers into $k$ groups such that the sum of the within group squared error is minimized, it ...
2
votes
1answer
24 views

Recurrence relation for number of relations with length $n$ from symbols $0,1$ and $2$ [duplicate]

i have a problem with recurrence relations problem.. I need to find a recurrence relation for a number of strings with length $n$ ranging from symbols $0,1$ and $2$ that do not contain two consecutive ...
0
votes
0answers
14 views

Distributing marbles into a box

Suppose there are $4$ indistinguishable boxes and we want to place $10$ indistinguishable marbles into the boxes in such a way that each box has at least one marble. In how many ways can this be done? ...
0
votes
1answer
19 views

Flag colouring problem (n horizontal stripes)

I have the following problem: “A flag is to be made with n horizontal stripes by using the colours yellow, blue, green and red in such a way that none of the adjacent stripes have same colour, and ...
2
votes
1answer
26 views

How many ways to distribute humans into rooms?

How many ways can we distribute $10$ humans into $4$ rooms if: Rooms $1$ and $2$ need $3$ humans. Rooms $3$ and $4$ need $2$ humans. I guess there are ${10\choose 3}$ ways for picking the humans in ...
0
votes
1answer
23 views

Arranging 15 acrobats in a specified order

There are $15$ acrobats who want to take acrobatics classes. Each of the $15$ acrobats are of different skill level. Assume acrobat $1$ has skill level equal to $1$, acrobat $2$ has $2$ skill level ...
2
votes
2answers
33 views

Counting the number of functions restricted by cardinality

Let $n\geq4$ be a positive integer and let $S=\{1,2,\ldots,n\}$. Find the number of functions $f:S\to S$ whose image has cardinality at most $n-3$. I'm trying to do this using inclusion-exclusion. ...