# 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
Filter by
Sorted by
Tagged with
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, ...
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 ...
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 ...
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 ...
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-...
24 views

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 ...
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 ...
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 ...
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 ...
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 ...
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?
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.
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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,...
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 ...
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 ...
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 ...
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$
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$....
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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.
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 ...
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 ...
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$)...
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 ...
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 ...
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 ...
### 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 ...