Stack Exchange Network

Stack Exchange network consists of 174 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.

1
vote
0answers
13 views

Solution using multinomial theorem raised to a negative power

The number of ways of selecting exactly 4 fruits out of 4 apples, 5 mangoes, 6 oranges is... A) 10 B) 15 C) 20 D) 25 I did the solution writing all the possible ways, I am getting 15, which is ...
-1
votes
1answer
18 views

$5$ prizes are distributed among $20$ students. What is the probability that a particular student receives $3$ prizes?

There are $5$ prizes that are to be distributed among $20$ students. What is the probability that a particular student receives $3$ prizes ?
1
vote
0answers
13 views

spaghetti hoops combinatorics variation

You may have heard about the classic spaghetti hoops combinatorics problem, which has been stated like this: "You have N pieces of rope in a bucket. You reach in and grab one end-piece, then reach in ...
0
votes
1answer
13 views

Number of times I will get b balls from the bag

I have 'n' identical balls and 'k' distinct bags. So total number of ways I can put balls with no restriction in bags is ${k+n-1 \choose k-1}$. So I want to know the number of times there were exactly ...
0
votes
1answer
20 views

Number ways of arranging dots and lines with restriction

I have this problem where I need to calculate the following: For x dots and y lines, how many arrangements are possible such that no more than n dots are together? Can anyone help me out?
0
votes
3answers
18 views

Counting Permutation of a set with the condition that $a_1 < a_2$

I'm not sure how the answer is a. How I approached this is: For $a_1$ < $a_2$ we can select $a_2$ to be $n$ (1 way) and then we have no choices for $a_1$ because it has to be less than $a_2$. Or ...
1
vote
3answers
39 views

Sumin rolls three distinct dice and gets a, b, and c. Find the probability of 2a + b + c = 10.

Sumin rolls three distinct dice and gets a, b, and c. Find the probability of 2a + b + c = 10. My answer: a b c 4 1 1 3 2 2 2 3 3 1 4 4 3 3 1 3 1 3 2 1 5 2 5 1 2 4 2 2 2 4 1 5 3 1 3 5 total ...
1
vote
0answers
12 views

Relation between partitions of $n$ into $k$ distinct parts and partitions of $n$ into at most $k$ parts

I'm working on a problem that I'm completely stuck on: Let $Q(n,k)$ be the number of partitions of $n$ into $k$ distinct (unequal) parts. Prove that the number of partitions of $n$ into at most $k$ ...
4
votes
1answer
33 views

Half of Vandermonde's Identity

We know Vandermonde's Identity, which states $\sum_{k=0}^{r}{m \choose k}{n \choose r-k}={m+n \choose r}$. Does anyone know what happens if we walk bigger steps with k? Say we skip all the odd ks, ...
2
votes
1answer
31 views

Show that no asymmetric graph $G$ exists with $1 < \big|V(G)\big| \leq 5.$

Show that no asymmetric graph $G$ exists with $$1 < \big|V(G)\big| \leq 5\,.$$ I tried listing all the possibilities for $\big|V(G)\big| \leq 5$ to prove this statement. I did all for $2$ and $3$,...
0
votes
1answer
36 views

Verifying solution: Twelve fair coins are flipped

I need to know if I did this problem correctly or incorrectly. Twelve fair coins are flipped. (a) What is the expected number of heads that will be obtained? if a coin is tossed 12 times, the ...
0
votes
0answers
20 views

Probability and averages dice

If you know the odds of something happening, say a particular set in a roll of 3 dice is 1/64 odds then how does one calculate the average number of rolls to produce this outcome?
0
votes
0answers
13 views

Constructing solutions for a given series to make it convergent

I would like to find a function f such that $$y_i=f(i) \geq 0$$ such that: $$\sum_{i=0}^n y_i = C(1-\frac{3p}{4})^{n(1-\frac{3p}{4})}(\frac{3p}{4})^{n(\frac{3p}{4})},$$ where $$C > 0, 0 \leq p \...
0
votes
0answers
20 views

How to eliminate redundant logic term using combinatoric expressions.

This expression is right according to Karnaugh Map Is it possible to eliminate extra term using combinatorics? Map:
-1
votes
0answers
25 views

Runtime of computing the coefficient of a product of multinomials?

Suppose I have $k$ variables, $ x_1, x_2, ... x_k $ and $m$ expressions in the form $ (1 +$ the product of some subset of $x_1 ... x_k)$ – for instance, $(1 + x_1)$ or $(1 + x_1x_2x_5)$ could be one ...
0
votes
0answers
8 views

Lower bound for matchings hypergraphs

I found a lower bound on matchings in hypergraphs in Pikhurkos paper: Perfect Matchings and $K^3_4$-Tilings in Hypergraphs of Large Codegree The bound is obtained by the following construction. We ...
0
votes
0answers
18 views

Probability of linear independency of vectors under finite field

How can I compute the probability of linear independency of m vectors under finite field? The vectors length assumed to be equal to n and vector elements to be random uniformly distributed. Thank you ...
1
vote
2answers
39 views

If $12$ distinct points are placed on a circle and all the chords connecting these points are drawn, at how many points do the chords intersect?

If $12$ distinct points are placed on the circumference of a circle and all the chords connecting these points are drawn, at how many points do the chords intersect? Assume that no three chords ...
4
votes
0answers
34 views

Sum of All Combinations of Products of Two Matrices

Suppose that $\mathbf A$ and $\mathbf B$ are square, diagonalizable matrices. Consider the following infinite sum of all combinations of these two matrices: \begin{align} \mathbf S = \mathbf I &+\...
-2
votes
2answers
40 views

How to calculate the sum?..

How to calculate the sum? If $\sum_{i=1}^{p-1} m_i = X$ then what is the value of the following sum in terms of $X$? $\sum_{i=3}^{p-1}\sum_{k=1}^{i-2} m_k m_{i-k-1}$
-1
votes
0answers
32 views

Formal proof for this problem: https://codeforces.com/problemset/problem/478/B

Problem: https://codeforces.com/problemset/problem/478/B I intuitively realised the solution easily, that the distribution of binomial expansion has minimum on the ends and maximum in the middle, but ...
5
votes
0answers
79 views

Identify a truth-teller among a group of truth-tellers and (honest) liars.

This question is inspired by this thread. In that thread, a liar may both tells lies and truths. However, in my version, liars always lie. Main Question. A group of people consists of $m$ truth-...
2
votes
0answers
33 views

Standard term for “dense” subset of a graph

Let us temporarily say that a subset $A$ of (the set of vertices of) an undirected graph $G$ is dense when each vertex of $G$ is adjacent to an element of $A$. In other words, the (distance-$1$, open)...
1
vote
1answer
21 views

Enumerating first arrivals to the opposite corner of $N$-cube

Number of walks from $(0,0,\dots, 0)$ to $(1,1,\dots, 1)$ along the $N$-cube's edges is enumerated by $\sinh^N$ and loops from a vertex to itself by $\cosh^N$ so why isn't the first arrivals to the ...
4
votes
2answers
172 views

Proof for this binomial coefficient's equation

For $k, l \in \mathbb N$ $$\sum_{i=0}^k\sum_{j=0}^l\binom{i+j}i=\binom{k+l+2}{k+1}-1$$ How can I prove this? I thought some ideas with Pascal's triangle, counting paths on the grid and simple ...
0
votes
0answers
23 views

The number of trials which maximizes the expectation of difference between the number of red balls and blue balls?

There are $N$ balls with $K$ red balls and $N-K$ blue balls. It means that the probability that the red ball is drawn with one draw is $K/N$. There is a random variables $X$ = the number of red ...
0
votes
0answers
25 views

Counting with repetition, how to determine which one is r and which one is n

* I know and understand that there are $\binom{n+r-1}{r-1}$ or $\binom{n+r-1}{n}$ ways to distribute n identical candies to r children. But sometimes, I can't determine which one is r and which one is ...
2
votes
1answer
39 views

How to solve a recurrence relation with generating functions?

I don't really understand how to solve (with generating functions) for the recurrence relation of $$a_n = a_{n-1}+2(n-1)$$ with initial conditions of $a_1 = 2$ when $n \geq 2$ This is what I was ...
2
votes
1answer
30 views

In how many ways can k bishops be placed on an k×k chessboard such that no two can threaten each other?

Not sure how to start this solution. I thought about proving by induction with a base case of k=2. In this case there are 4 ways that 2 bishops can be placed on a 2x2 board without threatening each ...
3
votes
2answers
249 views

Combinatorics Proof?

How would I prove $$\sum_{b=0}^a \frac{(2a)!}{b!b!(a-b)!(a-b)!} = \binom{2a}{a}\binom{2a}{a}$$ I am familiar with the identity $$\binom{2n}{n}=\sum_{k=0}^n\binom{n}{k}\binom{n}{n-k}=\binom{n}{k}^2$$ ...
0
votes
0answers
29 views

Why can’t we use multinomial theorem here?

We have $10$ white, $9$ green and $7$ black balls. All balls are identical except for colour. While the solution for selecting number of ways in which one or more balls can be selected from these ...
10
votes
2answers
759 views

Error in solution of Peter Winkler “red and blue dice” puzzle?

This question relates to the solution give in Peter Winkler's Mathematical Mind-Benders to the "Red and Blue Dice" problem appearing on page $23.$ You have two sets (one red, one blue) of $n\ n-$...
0
votes
1answer
21 views

Probability of Same Consecutive Digits Two / Three / Four Times

For work I have a device that generates a 'random' 8 digit code, with digits ranging from 0-9. The code can start with 0. For example: 01234567 76925951 93508862 I am looking for the probability of ...
0
votes
1answer
29 views

If there are four bakeries that each close one day a week, how many schedules are possible if at least one bakery is open each day?

I’m self studying for a probabilities and statistic exam so unfortunately, i don’t have anyone to ask. So the question goes, we have 4 bakeries and 7 days in a week. Each bakery closes once a week. a)...
0
votes
2answers
58 views

Evaluate $\sum_{n=1}^N n {n \choose k}$ and get a closed form solution

Find a closed form of $\displaystyle\sum_{n=1}^N n {n \choose k}$. 1) Firstly, is it valid to simplify this equation to: $\sum_{n=k}^N n {n \choose k}$ because ${n \choose k} = 0$ for $n < k$? 2)...
0
votes
0answers
54 views

Evaluate $\sum_{n=1}^N {n \choose k} $ [duplicate]

Evaluate to get a closed form solution. I encountered this by rearranging the below equation which I also need some help solving: $\sum_{n=1}^N n {n \choose k} $ I'm not very good at solving ...
3
votes
3answers
33 views

In how many ways can the letters in the word “PROBABILITY” be arranged using the following restrcitions [on hold]

In how many ways can the letters in the word "PROBABILITY" be arranged if the first letter must be "B" and the last letter cannot be an "O", "A", or "I"?
1
vote
1answer
27 views

How many ways are there? [on hold]

How many ways are there to put 14 identical objects in 3 distinct boxes with at least 8 objects in one box? What is the thinking procedure of the similar question type?
0
votes
1answer
24 views

How many ways can a number be written as a sum of two non negative integers?

How many ways can a number be written as a sum of two non negative integers? For example there is $4$ way for $7$. $ 7=0+7=1+6=2+5=3+4$ I think there is $[ \frac{N}{2}]+1$ way for number$N$. Is ...
0
votes
1answer
39 views

probability of groupings of people around a table

assuming X people sit down around a (round) table, Y people have black shirts and X-Y people have white shirts, what is the probability that the two clusters of shirts are grouped together (i.e., all ...
0
votes
2answers
54 views

Find number of five digit natural numbers using digits $1,2,3,4,5$ such that consecutive digits do not appear together

Find number of five digit natural numbers using digits $1,2,3,4,5$ without Repetition such that consecutive digits do not appear together I just tried in by listing the possibilities in a sequential ...
-1
votes
0answers
38 views

I'm not too great with inclusion-exclusion so any help would be appreciated

Use inclusion-exclusion to count the number of length k lists (where repetition is allowed and k ≥ n) whose elements are chosen from the set [n] where all of the elements in [n] appear at least once.
-5
votes
1answer
43 views

Give a combinatorial proof for the following identity: $1 · 1! + 2 · 2! + · · · + n · n! = (n+ 1)! − 1$. [on hold]

I need a combinatoric proof for this. I've seen a lot of induction proofs but can't find any help with this question and a combinatoric proof. Thanks for any help!
6
votes
1answer
76 views

How many colors is necessary so that a rectangle always covers no color more than once?

If we have an infinite grid, and we color each cell, how many colors do we need so that a $m \times n$ rectangle always covers at most 1 of each color no matter how it is placed? (Rotation of the ...
0
votes
0answers
17 views

Define $[n,k]$ as the number of $(n+k)$-lists of the form $a_1+a_2+..+a_i$ where n of the elements are $1$s and k of them are $-1$s

Define $[n,k]$ as the number of $(n+k)$-lists of the form $(a_1+a_2+..+a_i)$ where n of the elements are $1$s and k of them are $-1$s and where for all i , the sum of the first i entries is non-...
0
votes
0answers
17 views

in how many ways can 3 different copper coins and 3 different silver coins be arranged in a line so that the silver coin may be in odd places [on hold]

This is a permutations problem. I’ve tried it over and over again and now I couldn’t find any solution. So is there anyone else who can answer this for me ?
2
votes
3answers
43 views

Number of divisors of $10!$

Determine the amount of divisors of $10!$ This is a question in my combinatorics textbook, so I need to somehow reduce this to an elementary counting problem like combinations, permutations with or ...
1
vote
2answers
60 views

Arranging $n$ balls in $k$ bins so that $m$ consecutive bins are empty

This question is inspired by the following problem: Randomly place seven balls into ten bins, with no bin containing more than one ball. What is the probability that there will be (at least) two ...
1
vote
0answers
25 views

What does the 8 stand for in the Cantor pairing function?

What does the "8" stand for in the Cantor pairing function (which assigns a natural number to each pair of natural numbers)? Can I change it, or is it constant? The other function for getting the ...
0
votes
0answers
39 views

Infinite balls, infinite groups with finite number of balls of each value [on hold]

You have N balls of value 0, N of value 1, N of value 2, etc., N of each value up to infinity. They are separated into a group of X balls with total value 1, another group of X with total value 2, ...