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
1answer
97 views

Combinations problem for all possible combinations

Ok, so the sample space of 3 coin flips has 8 outcomes: hhh, hht, hth, htt, thh, tht, tth, ttt If you can select any number (including 0) of outcomes to create an event, the total number of events ...
0
votes
1answer
102 views

How does one prove this equation?

How does one prove the following equation , I am getting confused about this, I can't seem to find any proving technique, I tried plugging in the Stirling's formula for factorials but to no avail - ...
4
votes
1answer
184 views

Intuition behind the Jacobi triple product

Jacobi's triple product identity states that: $\displaystyle \sum_{n = -\infty}^{\infty}z^{n}q^{n^{2}} = \prod_{n = 1}^{\infty}(1 - q^{2n})(1 + zq^{2n - 1})(1 + z^{-1}q^{2n - 1})$ I've seen a messy ...
1
vote
2answers
84 views

Ways of choosing k things from n in a straight line

How many ways are there of choosing $k$ things from $n$ in a line, one of the two ends is always chosen? For example, consider $1, 2, 3, 4, 5$ in a line. Let us choose $3$ numbers from them such that ...
3
votes
3answers
4k views

Roll five dice. What's the chance of rolling exactly one pair?

If I roll five dice, what's the chance that exactly two of the die show the same number? I know that the total number of possible outcomes is $6^5$ = 7776. I calculated the probability that at least ...
0
votes
1answer
87 views

Minimum number of money to make each element in list greater than or equal to 0?

Given list with positive and negative integers.We have to make each element greater than or equal to zero.There are two types of moves first increase all elements by 1 requires P unit of money, second ...
0
votes
2answers
357 views

Probability of a run of heads of length at least $2$ when flipping a coin $n$ times.

There are $2^n$ equally likely outcomes when flipping a fair coing $n$ times. The probability in question can be written: $$p_{2,n}=\frac{R(2,n)}{2^n}$$ Where the numerator, $R(2,n)$ counts the ...
1
vote
2answers
142 views

Prove combinatoric inequality: ${n \choose {j+k}}\le {n \choose j}{{n-j}\choose k}$

How can one prove the following combinatoric inequality? $${n \choose {j+k}}\le {n \choose j}{{n-j}\choose k}$$ My line of thought was: $n$ people applied for an interview for a company. (And the ...
0
votes
1answer
54 views

counting sequences with constraints

For any $m, n\ge0$. Is there a way to count the number of sequences of length $m$ such that $$a_1 = a_m = 0$$ $$\left | a_{k} - a_{k-1} \right | =1$$ $$0\leq a_{k}\leq n$$
1
vote
2answers
571 views

Algebraic proof of $\sum_{i=0}^k{{n \choose i}{m \choose {k-i}}}= {{m+n}\choose k}$

I can't figure out an algebraic proof for the following identity: $$\sum_{i=0}^k{{n \choose i}{m \choose {k-i}}}= {{m+n}\choose k}$$ Combinatorical solution: We can see that as choosing some from ...
0
votes
2answers
2k views

Number of combinations and permutations of letters

I am confused by the following exercise. Exercise. Find the number of (a) combinations and (b) permutations of 4 letters each that can be made from the letters of the word Tennessee. Ideas: We have: ...
2
votes
2answers
146 views

Combinatorical proof $\sum_{k=0}^n{{2n+1}\choose k}=2^{2n}$

How to prove the following combinatorical identity using a combinatorical proof? $$\sum_{k=0}^n{{2n+1}\choose k}=2^{2n}$$ I solved it with an algebric proof with Newton's binomial and the symmetry ...
0
votes
0answers
248 views

Number of pairs of Binary Strings of Length n with Hamming Distance b

What is the maximum number of pairs of $k\geq2$ distinct binary strings of length $n$, such that the strings in each pair are at Hamming distance $b$? In other words, given $k$ points on the ...
1
vote
2answers
63 views

Game with two players and 120 points in total

Assume the following game: The game has two players $P_{1}$ and $P_{2}$ and 15 rounds in which they play against each other. Each round gives an amount of points equal to its number, i.e. the ...
0
votes
2answers
382 views

Exercise in combinatorics

I look for solutions to the following problem. Exercise. How many different three-digit numbers can be made with 3 fours, 4 twos, and 2 threes. Unfortunately I don't have any idea how to approach to ...
0
votes
2answers
1k views

Combinations: combinations vs permutations in particular exercise

I am confused by the following exercise. First, I will present the exercise with solution, after that there is a problem that I have about this exercise. Exercise. From 7 consonants and 5 vowels, how ...
1
vote
1answer
82 views

Questions on Stirling Number of the second kind

I understand the concepts on Stirling number but I don't seem to be able to grasp and apply them to problems, such as this one: Let $|A|=10$. Find the number of partitions that A have, that contains ...
4
votes
2answers
915 views

Choosing numbers without consecutive numbers.

In how many ways can we choose $r$ numbers from $\{1,2,3,...,n\}$, In a way where we have no consecutive numbers in the set? (like $1,2$)
1
vote
2answers
79 views

Permutation Problem Please Help!

In how many ways can you arrange $4$ men and $4$ women in a row of $8$ seats if one man and a woman will insist not to be seated together?
1
vote
2answers
208 views

Nine digit sequences with exactly one zero, two ones, three twos

I'm working on a problem where I am to find the number of nine digit sequences when there are exactly one zero, two ones and three twos. I worked up a solution, but is it correct? Here's my line of ...
0
votes
1answer
92 views

matching problem

Suppose that there is an absented-minded secretary, there are $n$-letters and $n$-corresponding letter. The secretary puts the letters in any corresponding, and not necessary it's corresponding ...
3
votes
1answer
85 views

A combinatorial problem in probability.

A class has a set of students say N, the teacher passes the attendance roster to any one of the N students randomly. Now each student when given the roster, first checks if they already signed it, if ...
0
votes
1answer
83 views

Proving a graph must be connected [duplicate]

Let $G$ be a graph with $n$ vertices and $e$ edges such that $e>\binom{n-1}{2}$. Then $G$ must be connected. As usual, hints would be greatly appreciated. If it where$\binom{n}{2}$ then wouldn't ...
1
vote
0answers
68 views

Running the Greene-Nijenhuis algorithm backwards

Let $Y$ be a Young tableau of shape $\lambda:=(\lambda_1,\ldots,\lambda_n)$, where $\lambda_1\geq\lambda_2\geq\ldots\geq\lambda_n$ and $N:=|\lambda|:=\sum_i\lambda_i$. I'll be using the English ...
4
votes
1answer
84 views

Hall's marriage theorem for infinite system of finite sets

We have proved the Hall's marriage theorem for the finite system of finite sets; now I would like to show that it holds even for infinite system of finite sets. I have been trying to prove this ...
-2
votes
2answers
89 views

Where am i wrong?

Where does my logic for the answer of the 2nd part of the question goes wrong? Probability of sampling with and without replacement
0
votes
2answers
64 views

given a set of $10^n$ numbers how many will have all the digits $0$ through $9$?

I am trying to find out given $n$ how many numbers $k\in [1, 10^n] \cap \mathbb{N}$ will have all the digits $0$ through $9$?
1
vote
2answers
3k views

Probability of sampling with and without replacement

In sampling without replacement the probability of any fixed element in the population to be included in a random sample of size $r$ is $\frac{r}{n}$. In sampling with replacement the corresponding ...
5
votes
4answers
441 views

Multiplying the roots of polynomials using only their integer coefficients

I am trying to write a function that takes the integer coefficients of two polynomials and returns the coefficients of a polynomial that has a root for each way you can multiply a root from the input ...
1
vote
1answer
40 views

Arranging letters with terms

This is a question I found in an old test while I was preparing for a test I have in a few days. The lecturer didn't really show us how to arrange with certain terms, so I need help with solving this. ...
2
votes
1answer
56 views

Interpreting “or” in a combinatorics question

I've used this site a lot for help understanding problems in my other math classes. Although I never got around to actually asking a question since most were already asked. Today it's a simple one ...
8
votes
2answers
335 views

On the problem 1 of Putnam 2009

(This is adapted from problem 1 of Putnam 2009) Find all values of $n$ such that the following is true: There is a non-constant function $f : \Bbb{R}^2 \longrightarrow \Bbb{Z}_2$ such that for any ...
0
votes
2answers
90 views

Combinatorics identity question

I encountered this particular combinatorial identity ...
0
votes
2answers
81 views

Bits and counting problem [duplicate]

I'm stuck in figuring out a problem, and I can't quite figure out a way out right now. any suggestion is highly appreciated. we have a 10bit number(made up of 1s and 0s), and we do not know the ...
5
votes
5answers
9k views

Flipping heads 10 times in a row

If I flip a coin 10 times in a row, obviously the probability of rolling heads ten times in a row is $\left(\frac{1}{2}\right)^{10}$. However, I am not sure how to calculate the exact odds that I will ...
1
vote
2answers
403 views

Possible combinations of two sets of three into a set of two

I'm trying to find the mathematical term for a certain phenomenon and hopefully a more general way to solve such problems. Say there are two sets, each = {A, B, C}. I would like to know how many ...
3
votes
1answer
127 views

Creating rectangles on checkerboard with three colors

On a 40 by 40 checkerboard, prove that if red, black, and white checkers are laid down, there must be four checkers of the same color that create the corners of a rectangle. The rectangle has sides ...
1
vote
1answer
105 views

Learning as a combinatorialist

Sorry if this isn't appropriate for stackexchange, but I just have been curious. For a combinatorialist, is more effort spent learning specific tools in combinatorics or learning other areas of math ...
0
votes
1answer
154 views

How many sequences of a length = n

How many sequences of a length = n and values of the set {1...n} we can get if each number from 1 to k occur to them. I know that it will be at least k!
2
votes
2answers
538 views

Simple Combinatorics Problem

I've 'indirectly' studied combinatorics earlier in probability courses, but now it's part of the math course I'm taking. I always thought it was very hard, and well, here I am again... The problem ...
2
votes
2answers
458 views

The number of ways of seating 6 people around 2 (circular, indistinguishable) tables

In a textbook there is a problem asking for the number of ways of seating 6 people around 2 circular and indistinguishable tables. The textbook gives this answer: There are 3 cases to consider: 1)5+1 ...
0
votes
2answers
35 views

counting tuples in $\mathbb Z^{i}$

Let $d$ be a positive integer, let $\mathbb N$ denote $\{1,2,\dots\}$. What is the size of the following subset of $\mathbb Z^{i}$? $$ \{ (a_1, \dots, a_i) : a_j \in \mathbb N, ~and~ a_1 + \dots + ...
2
votes
0answers
184 views

Is it possible to find sum of this series?

I am trying to find the sum of the following series asked by my friend. $$n\cdot\left(\bigl\lfloor\tfrac{n}{2}\bigr\rfloor+ \bigl\lfloor\tfrac{n}{3}\bigr\rfloor+ \bigl\lfloor\tfrac{n}{4}\bigr\rfloor+ ...
0
votes
1answer
54 views

A map from the set of binary strings to $\mathbb{N}$

Suppose $B$ is the set of all finite strings of $0$'s and $1$'s. Define a binary relation $R$ on $B$ as follows: $$\sigma R\tau\quad\mbox{ iff }\quad\mbox{ $\sigma$ is a proper initial segment of ...
2
votes
0answers
70 views

Orthogonal Latin squares - Origin of the word “Orthogonal”

Is there any linear-algebraic link with the use of the word "orthogonal" in orthogonal latin squares? I thought about it a little bit and the closest I got to linear algebra was this definition : if ...
2
votes
0answers
136 views

How to Enumerate of all simple connected labeled graphs with prescribed degree sequence?

For v=4 vertices, there must be 7 possible graphic sequence (3,3,3,3)(3,3,2,2)(3,2,2,1)(3,1,1,1)(2,2,2,2)(2,2,1,1)(1,1,1,1). From (3,3,3,3), one simple graph(complete) can be found. From(3,3,2,2), 6 ...
6
votes
3answers
790 views

How many ways to choose $k$ out of $n$ numbers with exactly/at least $m$ consecutive numbers?

How many ways to choose $k$ out of $n$ numbers is a standard problem in undergraduate probability theory that has the binomial coefficient as its solution. An example would be lottery games were you ...
1
vote
2answers
174 views

Probability of a sorted sequence

Now I tried tackling this question from different sizes and perspectives (and already asked a couple of questions here and there), but perhaps only now can I formulate it well and ask you (since I ...
3
votes
0answers
165 views

$N$th term of sequence

I have a sequence: $$1,\;2,\;3,\;4,4,4,\;5,5,5,5,\;6,6,6,6,6,6,6,6,6,6,\ldots$$ In words the $i$th term of sequence is $$\min(k \;|\; k \le i \text{ and } \max(^kC_x)\ge i)$$ I want to find the ...
6
votes
1answer
175 views

Simple approximation to a sum involving Stirling numbers?

I have also posted this question at http://mathoverflow.net/questions/141552/simple-approximation-to-a-sum-involving-stirling-numbers#141552. I have an exact answer to a problem, which is the ...