For questions about the study of finite or countable discrete structures, specifically 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.

learn more… | top users | synonyms (4)

0
votes
2answers
264 views

Probability question involving playing cards and more than one players

I've been struggling with this problem for a while, so I have to ask you guys for a little mental push. My problem involves a full deck of playing cards and 4 players, but I'll simplify it to 4 cards ...
0
votes
1answer
24 views

Number of paths in a MxN matrix

Given a MxN grid, how many paths can there be to reach the bottom right cell from the top left cell? The only constraints are one cannot visit a cell more than once, I tried checking the other ...
2
votes
1answer
26 views

Probability that a set of $n(n+1)/2$ elements will contain $1… n$ elements, respectively, of $n$ possibilities

We opened a 'fun size' bag of Skittles this afternoon, and it contained 5 yellow, 4 red, 3 blue, 2 green, and 1 purple Skittle. If the Skittles only come in these 5 colors, they are chosen randomly ...
2
votes
5answers
390 views

How to simplify this triple summation containing binomial coefficients?

$$ \large\sum_{i=0}^{n} \sum_{j=i}^{n} \sum_{k=j}^{n} \binom{i+m-1}{m-1}\binom{j+m-1}{m-1}\binom{k+m-1}{m-1} $$ How to solve it when this involve more than thousand summation ?
7
votes
3answers
61 views

How many different arrangements are there problem

How many different arrangements are there of all the nine letters A, A, A, B, B, B, C, C, C in a row if no two of the same letters are adjacent? First I tried to find how many ways to arrange so at ...
1
vote
0answers
16 views

What are some properties of posets that are preserved or not preserved by a Dushnik-Miller embedding

The Dushnik-Miller dimension of a (discrete) poset, $P$, involves embedding $P$ into $\mathbb{N}^d$, for $d$ minimal. Inherent in the construction is that the embedding preserves the order of $P$. ...
2
votes
5answers
69 views

How many $3$ integer subsets have no consecutive integers, where integers are less than $20$?

I have to determine how many integers between $1$ and $20$ are possible if no two consecutive integers are in a set. I've thought it has something to do with a combination of an element $(a,a+2,a+4)$ ...
3
votes
1answer
34 views

Link between tetrahedral numbers and combinatorics problem?

So I was trying to figure out a combinatorics problem involving the number of unique paths between two coordinates (can't move backwards such as from (1,1) to (0,1)) and I got stuck. I decided to draw ...
6
votes
1answer
130 views

ordered pairs in binomial coefficients

Find the number of ordered pairs $(n,r)$ which satisfy $\binom{n}{r} = 2013$. Find the number of ordered pairs $(n,r)$ which satisfy $\binom{n}{r} = 2014$. My Attempt for $(1)$: By ...
4
votes
2answers
65 views

Confusing probability problems based on product rule and combinations

I am going thru probability exercise. Faced first problem: Book Q1. Ten tickets are numbered 1,2,3,...,10. Six tickets are selected at random one at a time with replacement. What is the ...
6
votes
2answers
43 views

Integer Tetrahedra

The points $\{(0, 0, 0), (12, 27, 44), (48, 0, 20), (48, 0, -64)\}$ have the property that All vertices are on the integer grid, All edge lengths are integers and different $\{51, 52, 53, ...
6
votes
2answers
67 views

How many routes are there from $A$ to $B$ that cross every node exactly once?

Imagine an $n \times n$ grid, we start on one corner of the grid in square $A$, and need to reach the opposite corner to square $B$. The rules are, you can only move to an adjacent square, you can't ...
0
votes
1answer
46 views

If $N$ is a $4$ digit number $x_1x_2x_3x_4$, then prove that $\frac{N}{x_1+x_2+x_3+x_4}\le1000$

So $N=1000x_4+100x_3+10x_2+x_4$ $0<x_4\le 9$ $0\le x_3\le 9$ $0\le x_2\le 9$ $0\le x_1\le 9$ $0<{x_1+x_2+x_3+x_4}\le 36$ What should be my approach?
3
votes
2answers
49 views

Bijection between $\Bigl\{1, 2, \dots, \frac{N(N+1)}{2}\Bigr\}$ and $\{ (i, j) \in \mathbb{N} : i \le j \le N\}$

Let $N$ be some positive integer and $A$ be the following set $\{ (i, j) \in \mathbb{N}^2 : 1 \le i \le j \le N\} = \{ (1, 1), (1, 2), \ldots, (1, N), (2, 2), (2, 3), \ldots, (2, N), \ldots, (N, N) ...
0
votes
3answers
35 views

Combinatorics - Coloring a 3x3 chess with a restriction.

Let's imagine a 3x3 chess with 9 elements and every element can be colored with red and blue paints.We have a restriction, that we must have at least 1 square 2x2 painted red.How many ways we have? ...
0
votes
1answer
26 views

N balls having M different colors in a box, how many times do I need to pick to get one particular color?

There are $N$ balls of $M$ different colors in a box i.e $c_1$ balls of color $1$ and so on. $c_1 + c_2 + \dots + c_M=N$, $c_1, c_2, \dots, c_M$ are known. We are looking for a ball of a particular ...
4
votes
1answer
67 views

Binomial coefficients identity [duplicate]

Prove algebraically or otherwise: $$\sum \limits_{r=0}^n {2r \choose r} {2n-2r \choose n-r} = 4^n $$ where ${n \choose r}$ denotes the usual binomial coefficient. I think there is a combinatorial ...
0
votes
0answers
18 views

Relations between binomial polynomials (umbral calculus)

In the field of umbral calculus binomial polynomials are called such $p_n(x) : \text{deg} \> p_n = n$ that satisfy the binomial identity: $$p_{n}(x+y) = \sum_{k=0}^n \binom{n}{k} p_{k}(x) ...
1
vote
1answer
452 views

What is number of perfect matchings in a bipartite graph

Let's $G=(U,V,E)$ be a random balanced Bipartite graph graph which $|U|=|V|=n$. What is the number of random graphs that has a perfect matching? I think that the number of possible graphs is ...
4
votes
1answer
104 views

Consecutive numbers in rows of Pascal's triangle …

The fourteenth row of Pascal's triangle has an interesting property. $$\begin{align} \binom{14}{4}+\binom{14}{5} &= 1001+2002 \\ =\binom{14}{6} &= 3003 \end{align}$$ This begs the ...
-3
votes
0answers
27 views

combinatorics : there are 20 Boxes , you choose balls from 6 different colors , picking some, all or none and randomly place in the boxes. [on hold]

there are 20 Boxes , you choose balls from 6 different colors , picking some, all or none and randomly place in the boxes. Does there exist 2 different balls (different colors) such that these 2 are ...
2
votes
3answers
361 views

A combinatorial inequality

How can I prove $$ \log \binom nk \leq k \left(1 +\log\frac{n}{k}\right) $$ where $\binom\cdot\cdot$ stands for combination. I tried to use stirling approximation but I couldn't get the inequality.
2
votes
2answers
82 views

Simplifying Sum

How would one show that $$ \sum_{i=0}^n\binom{n}{i}(-1)^i\frac{1}{m+i+1}=\frac{n!m!}{(n+m+1)!} ? $$ Any hint would be appreciated. Note: I tried to recognize some known formula, but since I don't ...
1
vote
1answer
13 views

The number of quadrilaterals formed from collinear and non-collinear points.

There are $25$ points on a plane of which $7$ are collinear . How many quadrilaterals can be formed from these points ? I did this $^{25}C_{4}-^{7}C_{4}=12615$ quadrilaterals. But the book is ...
2
votes
3answers
81 views

Sum of increasing integer numbers

Please help me to calculate this sum: $$ \sum\limits_{1\leq i_1 < i_2 <\ldots i_k \leq n} (i_1+i_2+\ldots+i_k). $$ Here $n$ and $k$ are positive integer numbers, and all the numbers $i_1, i_2, ...
4
votes
3answers
59 views

Algebraic and combinatorial proof of an identity

For any two integers $2 \le k \le n-2$, there is the identity $$\dbinom{n}{2} = \dbinom{k}{2} + k(n-k) + \dbinom{n-k}{2}.$$ a) Give an algebraic proof of this identity, writing the binomial ...
3
votes
3answers
280 views

Prove $\sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k}$

Let $n$ be a nonnegative integer, and $k$ a positive integer. Could someone explain to me why the identity $$ \sum_{i=0}^n\binom{i+k-1}{k-1}=\binom{n+k}{k} $$ holds?
3
votes
1answer
46 views

Picking K counters out of K buckets containing NK counters, N of each different colour, up to N in each

This is a generalisation of a question that recently came up while solving a TopCoder problem. Suppose we have N blue counters, N red counters, N white counters, and so forth, K colours in total. We ...
1
vote
1answer
51 views

The ant is moving through the coordinate system, Started at $(0,0)$ to $(4,4)$. What is the probability that the ant will find food at $(3,2)$?

The path to the $(3,2)$ is $3+2 \choose 3$ or $3+2 \choose 2$. Total path is $4+4 \choose 4$ And the probability is : $ \frac{3+2 \choose 3}{4+4 \choose 4}$ = $ \frac{5 \choose 3}{8 \choose 4}$ = ...
0
votes
1answer
22 views

Solution of recurrence relation for roots having multiplicity $ \ge 1 $

If there is a recurrence relation of the form $ a_n = c_1 a_{n-1} + c_2 a_{n-2}+ ... + c_k a_{n-k} $, then if b is a non zero complex root of the recurrence relation with multiplicity t, $t \ge 1 $, ...
2
votes
1answer
29 views

Birhdays: find the probabilities for the various configurations of the birthdays of 22 people

Let S,D,T,Q stand for simple,double,triple and quadruple, respectively: So, for example: the probabilities of 22 simple birthdays(22 person have birthdays in different days) are $ P(22S) = ...
10
votes
3answers
644 views

Distinguishable painted prisms with six colors (repetition allowed)

Fraleigh(7th) Ex17.9: A rectangular prism 2 ft long with 1-ft square ends is to have each of its six faces painted with one of six possible colors. How many distinguishable painted prisms are ...
8
votes
3answers
118 views

Probability of rolling a dice 8 times before all numbers are shown.

What is the probability of having to roll a (six sided) dice at least 8 times before you get to see all of the numbers at least once? I don't really have a clue how to work this out. Edit: If we are ...
0
votes
2answers
56 views

Combinatorics: How many 6 digit numbers have AT LEAST one '9' among them?

The Question is pretty simple and straight forward when we try to find the count of numbers without 9 and Subtracting that with Total arrangement of numbers [9*10^5] - [8*9^5]. But how do you ...
3
votes
1answer
149 views

How many ways to arrange 12 identical apples and five distinct oranges in a row so no two oranges are side by side?

My first intuition to solve this problem was to use the separator technique with the apples acting as separators. $$_1_1_1_1_1_1_1_1_1_1_1_1_$$ Since there are now 13 blank spaces for the oranges to ...
3
votes
1answer
74 views

How to count the number of substrings in this combinatorics problem?

Let's say I'm making a string of $A$s and $B$s, where the number of $A$s and $B$s are $a$ and $b$ respectively. A total of $a+b \choose a$ such strings are possible. Now, I wish to know the total ...
3
votes
1answer
66 views

Probability: 12 students choose a major

12 students must choose a major from 6 options (math, biology, physics, chemistry, psychology and architecture). a) what is the probability that exactly 3 students choose physics? b) what is the ...
3
votes
1answer
36 views

Probability of at most two aces

I am dealt 7 cards from a standard pack. I want to find the probability of being dealt at most two aces by using combinations. I believe the calculation looks like this: $$\frac{\binom{4}{2} ...
2
votes
0answers
29 views

Properties of a specific antichain of a lattice formed by the cartesian product of finite ordered sets

Introduction Let $X$ be a poset of all $n$-tuples, $x = (x_1, x_2, ..., x_n)$, where $0 \leq x_i \leq m_i - 1$ for $i = 1, ..., n$ together with the relation $x \prec y$ defined so that for ...
3
votes
2answers
45 views

Alternative interpretation of ball and urns problem

Suppose an urn has r red balls and b black balls. They are withdrawn one at a time at random until a total of k, k $\leq$ r, red balls have been withdrawn. Find the probability that a total of n balls ...
3
votes
1answer
27 views

Simplifying a Taylor polynomial that involves Stirling numbers of the second kind

I am currently trying to evaluate a complicated function $f$ at a point $x+a$ using a high order Taylor polynomial about the point $a$. The polynomial has the standard form: $$\sum_{n=1}^k ...
0
votes
3answers
48 views

What is the sum of nine dates in a month? [on hold]

9 dates in a certain month are enclosed by a rectangle as following: 7 8 9 14 15 16 21 22 23 Let $n$ be the number at the top left hand corner of the rectangle. Express the sum of the ...
5
votes
2answers
63 views

Proof that $2^n-(n+1) $ equations are necessary to establish the independence of n events.

Suppose $A_1,A_2,\cdots,A_n$ are $n$ events, we say that they are all independent if for all $\{i_1,\cdots, i_m\}\subset \{1,2,\cdots,n\}$(where $m\ge 2$), we have $$\mathrm{Pr}[A_{i_1}\cap ...
0
votes
1answer
21 views

Say we have a double-decker Lazy Susan with two levels that can be turned independently. If we have n + k dishes in total, how many ways

Say we have a double-decker Lazy Susan with two levels that can be turned independently. If we have n + k dishes in total, how many ways is that solution is correct ???
1
vote
2answers
2k views

Probability of n balls in n cells, one remaining empty

Counting problems have always intrigued me, and I'm working on some out of interest. The other thread on this topic had unsatisfactory answers, because they don't match the answer in my book. My ...
1
vote
1answer
16 views

How can I generate a set of unique groupings of a set (e.g. a set of pairings of students such that everyone works with everyone)?

How can I generate a set of unique groupings of a set (e.g. a set of pairings of students such that everyone works with everyone)? I'm starting with a class of a given size and a group of a giving ...
2
votes
1answer
34 views

Numbers between $200$ and $1200$ that can be formed with the digits $0,1,2,3 $

How many numbers between $200$ and $1200$ can be formed with the digits $0,1,2,3 $ (repetition of digits not allowed ) ? $a.)\ 6\\ b.)\ 8\\ c.)\ 16\\ \color{green}{d.)\ 14}$ I divided it in ...
3
votes
1answer
30 views

Optimizing number of 6-digit strings differing in at least two places

A certain province issues license plates consisting of six digits (from 0 to 9). The province requires that any two license plates differ in at least two places. (For instance, the numbers ...
0
votes
2answers
404 views

calculate all combination of indistinguishable objects

I am thinking a question of picking $k$ objects out of $n$($n>k$). But among the $n=4m$ objects, only $m$ distinguishable objects. For example, a deck of poker cards, total $n=52$ cards, but we ...
5
votes
4answers
118 views

How many ways to write $2010$?

Let $ N$ be the number of ways to write $ 2010$ in the form $ 2010 = a_3 \cdot 10^3 + a_2 \cdot 10^2 + a_1 \cdot 10 + a_0$, where the $ a_i$'s are integers, and $ 0 \le a_i \le 99$. An example of ...