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.
39,634
questions
0
votes
1answer
6 views
How changing parameters on a sigma notation affects your position on Pascal's Triangle
Below is a proof claiming to prove that the sum of a row on Pascal's Triangle is equal to 2x the sum of the row before it. The key here was to use Pascal's Identity.
I understand the general concept, ...
0
votes
1answer
22 views
counting proof for $\sum$
I was hoping someone could help me come up with a combinatorial proof, one with an easy to understand 'story' for $\sum_{k=0}^{n-1} 2^{k} = 2^n - 1$. For instance I understand that $2^n$ is the number ...
0
votes
1answer
9 views
ice cream flavors, cones, and toppings. A counting question.
There are 5 distinct ice cream flavors, 5 distinct cones, and 5 distinct toppings. I gather all 15 distinct supplies. There are 5 people. Each person has to get a cone, flavor, and topping, and I can ...
1
vote
2answers
18 views
Symmetric random walk that does not hit $0$
Suppose a random walk $\{X_n\}_{n\in \mathbb Z^{\ge 0}}$ on the integer number line, $ \mathbb {Z}$ , which starts at $0$ and at each step moves $+1$ or $−1$ with equal probability. The increments ...
2
votes
1answer
21 views
Counting number of valid strings
Call a length $n$ string "valid" if it is formed from the set $\{A, B,
C, D, E, F, G\}$ and it contains at least one of A, B, C, D
Find the number of valid strings using Principle of Inclusion-...
2
votes
1answer
24 views
How many binary strings of length $n$ contain $k$ flips?
If I have say the string $1010010001010101$, which has a length of $16$ and there are $12$ flips. My thoughts are to just count the number of ways I can stick a $10$ in the there so ${n-1 \choose 0.5k}...
0
votes
1answer
17 views
Counting distinct functions
I would like to get help with the following question:
A and B are integers (A ≤ B). How many distinct functions exist from
the type of [A...B] → [A..B] such that f(x) ≤ x for all x in the
...
1
vote
2answers
35 views
How to calculate the complement of rolling dies?
I'm having a hard time trying to picturing the complement rule on this one. Can someone please enlighten me?
You roll 10 times of a fair 12 sided die. Find the probability of rolling two or more 12's ...
0
votes
0answers
15 views
Why is $\mathcal{P}$ = SET($\mathcal{Z}$)?
in the book Analytic Combinatorics, where the symbolic method is described, they say that $\mathcal{P}$ = $SET(\mathcal{Z})$ and therefore $\hat{P}(z) = exp(\hat{Z}(z))$.
$\mathcal{P}$ denotes the ...
1
vote
1answer
21 views
Generating functions (with symbol method) of special partitions of natural numbers
I want to show that the generating function of the number of partitions where every summand appears at most twice of every natural number n equals the number of paritions of n into summands which are ...
0
votes
1answer
19 views
Number of steps in special graph algorithm.
First of all to avoid misunderstanding i am going to describe what will i call a algorithm in my graph-theoretic problem.
algorithm is a set of pairs, where first coordinate is natural number - a ...
0
votes
1answer
20 views
Number of possible ways n people can meet for lunch on a circular table such that each day no two people sit together who have sat together before?
So i started studying this book on graph theory by Nar Singh Deo, and fairly early on the following problem gets introduced:
n people decide to meet for lunch every day, however they decide that they ...
0
votes
0answers
11 views
Selecting 'r' objects from different groups of alike objects
From 4 red, 3 black and 2 white balls, in how many ways can one select 3 balls? Also answer for the case when at least one black ball must be selected.
0
votes
1answer
44 views
Proving a square number
a)
Decide (without the help of a calculator) which of the following numbers
$t = 1 125$, $u = 1 225$, $v = 111 225$ and $w = 112 225$ square numbers.
If necessary, specify the numbers whose squares ...
4
votes
3answers
252 views
There are 51 natural numbers between 1-100, proof that there are 2 numbers such that the difference between them equals to 5
This question relates to pigeonhole principle, but I couldn't find what the holes need to be. How should I prove this сlaim?
2
votes
2answers
43 views
A question on combinatorics: if $p + q + r = 10$, find the number of possible combinations where the condition holds true.
If $ p + q + r = 10 $, find the number of possible combinations satisfying the equation. ( $p,q,r ≥ 0$)
PS -
As suggested by Brian Moehring, I used the 'stars and bars' method.
We need the sum as $...
0
votes
1answer
19 views
Maximizing probability of winning with urn of 30 balls, 20 white and 10 black. white gives +1, black gives -2
An urn contains 20 white balls and 10 black balls. If you draw a white ball, you get 1 dollar, but if you draw a black ball, you lose 2 dollars.
How many balls should you draw in order to maximize ...
0
votes
1answer
24 views
Number of ways in which 3 numbers in Arithmetic progression can be selected from 1,2,3…n is?
Initially i thought of dividing the sequence into groups of 3 that is 1,2,3,4,.. gets divided in to consecutive groups which means there are a total of $n\over 3$ groups and hence the total was of ...
2
votes
1answer
20 views
Arrangements around a square, People not sit across diagonally - Extension
The first two parts of this question are exact same as the Counting the arrangements of 8 people around a square table? and have already been answered but my struggle is in the final part of my ...
0
votes
1answer
20 views
Ice cream, cones, and toppings. How many ways can I make the order?
There are five orders of ice cream. Each ice cream order has a distinct cone, distinct ice cream flavor, and distinct topping. I have to put on a cone before I can put on ice cream, and I have to put ...
0
votes
0answers
16 views
How to prove following identity in measure of integral?
We have a point $P$ in $\mathbb{R}^2$ having coordinates $(x_+,x_-)$. Let $\xi$ be a path from the origin to $P$ consisting of polygonal path parallel to $x$ and $y$ axis. Let $l_i^+$ denote the ...
0
votes
0answers
7 views
Real World Application of Dominating Sets and Total Dominating Sets [on hold]
Are there any basic applications of dominating sets and total dominating sets?
0
votes
2answers
32 views
Counting with Venn Diagrams
How many arrangements are there of MURMUR with no pair of consecutive letters are the same.
This problem is from Alan Tucker's book: applied combinatorics.
3
votes
2answers
53 views
Number of words with two “$A$” using two letters from “$RATA$” and three letters from “$TIERRA$”
Find the number of words with two "$A$" using two letters from "$RATA$"
and three letters from "$TIERRA$".
What I did:
There are two cases, one where I choose both $A$ from $RATA$ and the rest of ...
2
votes
0answers
42 views
How many five digit numbers can be formed from the integers 1,2,..,9 with one digit appearing at max thrice?
The problem is in the title of the question, repeated below:
How many five digit numbers can be formed from the integers 1,2,..,9 with one digit appearing at max thrice?
I have two solutions as ...
1
vote
1answer
34 views
In how many ways can $n$ unique books be arranged on $m$ shelves if at least one shelf is empty?
In how many ways can $n$ unique books be arranged on $m$ shelves if at least one shelf is empty?
I am pretty sure that this is a question asking about objects and dividers, but I'm not sure how to ...
2
votes
0answers
27 views
Need help with Möbius function
Suppose I need to find total subset of numbers of length $K$ in range $1$ to $N$ such that their $\gcd$ is $g$. How can I utilize Möbius function for that.
So approach is we can choose $K$ numbers ...
-1
votes
2answers
30 views
L-stones with quadrat [on hold]
Figure A 591014 a gives a square of 25 fields. This figure should be designed with (congruent) L-stones, whereby a special field is removed beforehand.
An L-shaped stone consists of three square ...
-1
votes
1answer
42 views
Probability of balls in urn
For a random experiment, four red and four blue balls are available. In the beginning, four of the eight bullets are placed in one urn, the other four serve as a supply. In each step of the random ...
1
vote
2answers
30 views
Three different numbers from the set {1, 2, 3, 4, 5, 6}. In how many ways can he do this so that the three numbers are not consecutive?
Three different numbers from the set {1, 2, 3, 4, 5, 6}. In how many ways can he do this so that the three numbers are not consecutive?
So it's C (6,3)=20
There are 4 types that are consecutive (1,2,...
0
votes
1answer
12 views
How many different combinations can be put to decorate the room? [on hold]
Suppose there are 4 identical dolls, 6 identical toys, 9 identical pillows and we can use any amount to decorate a room. In how many different ways can you decorate the room given that the room cannot ...
1
vote
1answer
19 views
How much 3x4 matrix with integer numbers (every num >= 0) , which in every row the sum is 3 , and there no column of zero's?
I tried to answer the question and get a result of 7998 options , that is right?
from my way of solution , there are 20^3 3x4 matrixes which sum of every row is 3, and then i tried to substract num ...
1
vote
0answers
22 views
Forming n digit numbers out of 1,2,…,9 such that k digits can repeat
I came across following two problems:
(1) How many 5-digit numbers can be formed from the integers 1,2,…,9 with only one digit appearing twice?
(2) How many 5-digit numbers can be formed from ...
1
vote
3answers
64 views
How many solutions does the rebus have? [on hold]
How many 8 digit (its digits from left to right are labeled a through g) satisfy the following constraints:
$a_1 < a_2 < a_3 < a_4$
$a_4 > a_5$
6
votes
3answers
66 views
Symmetric matrix as a sum of symmetric matrices
Let matrix $M \in \mathbb{N}^{5 \times 5}$ be symmetric with non-negative integer entries and zeros on the main diagonal and having the property that the row sums are equal to $2r$ for some $r \geq 2$....
0
votes
1answer
25 views
Grouping Combination Probability
$9$ buses are being sent to $3$ airports such that $3$ go to Airport $1$, $5$ go to Airport $2$, and $1$ goes to Airport $3$. Assume that the buses are sent to the airports at random.
$1$) In how ...
0
votes
2answers
26 views
Permutation allowing repetition
Jeff is going to eat dinner out each day from Monday to Friday in a certain week, with each dinner being at one of his $15$ favorite restaurants.
$1$) How many possibilities are there for Jeff's ...
5
votes
4answers
56 views
A question on giving prizes when there is no restriction on the number of prizes per person
A group consisting of $3$ men and $6$ women attends a prizegiving ceremony. If $ 5$ prizes are awarded at random to members of the group, find the probability that exactly $3 $ of the prizes are ...
0
votes
0answers
15 views
Combination-Counting problem [duplicate]
How many different ways can 200 coins be distributed among 10 people so that:
1)everyone gets 0, or more, coins?
2)everyone gets 5, or more, coins?
I know how to do question it they have an exact ...
1
vote
0answers
16 views
Generalized Gessel-Viennot-Lindstrom Lemma to Hyperdeterminants of Multinomial Coefficients
A consequence of the Gessel-Viennot-Lindstrom lemma is that if $A$ and $B$ are collections of points in $\mathbb{Z}^2$, that the number of non-intersecting lattice paths (counted with a sign) from the ...
1
vote
1answer
54 views
A combinatorics equality(need help proving it)
show that $\binom{n-1}{\frac{1}{2}(n+b)-1}-\binom{n-1}{\frac{1}{2}(n+b)}=\binom{n}{\frac{1}{2}(b+n)}\frac{b}{n}$. Assuming $b>0$ and $b<n$
Just by thinking combinatorically, I don't see why the ...
3
votes
2answers
48 views
Which is the importance of Young’s tableaux in mathematics?
I don’t know much about combinatorics, I’m just getting started on this. I want to know, why Young’s tableaux are important? and why it is important to relate them to matrices?
Thank you very much.
1
vote
1answer
51 views
To Prove $ |Y_{n,k}|=(n/k)*{n-2k-1 \choose k-1}$
To prove, $$ |Y_{n,k}|=\frac{n}{k}{n-2k-1 \choose k-1}$$
Where, For $k,n \in N$, let $Y_{n,k}$ be the collection of $k-element$ subsets $A \subset [n]$ , given that,
$i-j$ is not congruent to 1 or ...
0
votes
0answers
20 views
How many ways can balls be picked from a box? [duplicate]
Suppose you have $a$ orange, $b$ pink, and $c$ purple balls in a box. How many ways can 3, where $c < a, b, c$ balls be selected such that at least one of the three is purple?
I think you just ...
0
votes
0answers
42 views
Drawing balls from $n$ numbered balls $k+1$ times with replacement
Consider:
$E_j$: the maximum of the values obtained on $k+1$ draws is $j$, $j=1,\ldots…,n$,
$F_j$: all the draws are done on $\{1,\ldots,j\}$, $j=1,\ldots,n$
$F_0 = \emptyset$.
Calculate P($E_j$)...
0
votes
2answers
33 views
Find the number of four-letter words that use letters from {A, B, C} in which no three consecutive letters are the same.
Case 1: (3)(3)(2)(3)=54. In the first two spots the letters can be any of A,B, or C. The third spot is where we risk having a third consecutive letter, so there are only 2 choices. Now the fourth spot ...
1
vote
0answers
24 views
Accessible sources providing an intuitive, elementary intro to Hopf algebras/monoids
Motivation:
I'm interested in understanding the role that noncrossing partitions play in Hopf algebras/monoids (HAs) as the components of the power series of the compositional inverse of formal ...
0
votes
1answer
80 views
Prove Pascal's formula by induction [on hold]
I have Pascal's identity: $$\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}.$$ How can I prove this using mathematical induction?
This is an exercise from Section 5.5 of Alan Tucker's Applied ...
0
votes
0answers
19 views
Statistics question about different combinations [on hold]
Consider a 6 vs 6 youth soccer team (i.e., teams field 6 players at once) with 9 players.
(a) How many different combinations of players can the team field?
(b) If the team has exactly one goalie (who ...
3
votes
4answers
126 views
How many integral solutions does $2x + 3y + 5z = 900$ have when $ x, y, z \ge 0$?
Solution: Let $2x + 3y = u.$ Then we must solve $\begin{align} u + 5z = 900 \tag 1 \\ 2x + 3y = u \tag 2 \end{align}$
For $(1),$ a particular solution is $(u_0, z_0) = (0, 180).$ Hence, all the ...
