This tag is for basic 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)

3
votes
0answers
67 views

Amount of matrices produced by mirroring

Given an $n \times n$ matrix whose entries are pairwise distinct, how many different matrices can you generate by: exchanging columns $i$ and $n-i+1$ exchanging rows $i$ and $n-i+1$ mirroring the ...
3
votes
1answer
180 views

What's the reasoning for this recurrence on $q$-multinomial coefficients?

I'm familiar with the recurrence for binomial coefficients based on Pascal's triangle. However, in general, there is the recurrence for $q$-multinomial coefficients given by $$ ...
0
votes
2answers
79 views

What is the generating function for these word types?

I'm curious to see what the generating function is for numbers of some words with a few constraints. Let's fix some $m$, and I'll denote by $[m]$ the set of $m$ symbols, say $\{1,2,\dots,m\}$. Now ...
2
votes
1answer
374 views

Combinatorial interpretation for the identity $\sum\limits_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}$?

A known identity of binomial coefficients is that $$ \sum_i\binom{m}{i}\binom{n}{j-i}=\binom{m+n}{j}. $$ Is there a combinatorial proof/explanation of why it holds? Thanks.
1
vote
1answer
2k views

If a die is rolled thrice, what are the possible different outcomes.

I have a single die, and it is rolled thrice. What could be the total possible different outcomes, I guess if I have the number of possible outcomes for each rolled die, then I would use it for other ...
1
vote
3answers
461 views

Binomial inequality

Show that we have: $$ \binom{n}{s}\leq n^n $$
1
vote
1answer
194 views

Unique factorization less than 100

How do I approach this problem using unique factorization?... How many numbers are product of (exactly) $3$ distinct primes $< 100$? edit: Just to add to that, How does unique factorization ...
3
votes
3answers
226 views

Combinatorial proof of $\binom{n}{k} = \binom{n}{n-k}$

How do I prove this combinatorially? $$\displaystyle \binom{n}{k} = \binom{n}{n-k}$$
2
votes
4answers
125 views

“Down-Closed”, “Down Ideal”, Something Else?

Let $X$ be an a set and let $\mathcal{C}$ be a collection of subsets of $X$ satisfying the following property: If $A$ and $A^\prime$ are subsets of $X$ with $A \in \mathcal{C}$ and $A^\prime ...
2
votes
1answer
612 views

How many unique pairs of integers between $1$ and $100$ (inclusive) have a sum that is even?

How many unique pairs of integers between $1$ and $100$ (inclusive) have a sum that is even? The solution I got was $${100 \choose 1}{99 \choose 49}$$ I don't have a way to verify it, but I figured ...
29
votes
3answers
1k views

A combinatorial proof of $n^n(n+2)^{n+1}>(n+1)^{2n+1}$?

The statement is simply that the sequence $\left(1+\frac{1}{n}\right)^n$ is increasing. Since the numbers $n^m$ have quite natural combinatorial interpretations, it makes me wonder if a ...
2
votes
2answers
2k views

Probability with Combinations (Coin Toss)

Toss a fair coin six times. What is probability of : a- all heads b- one head c- two heads d- an even number of heads e- at least four heads. I have the answers so I ask if you could explain how ...
1
vote
0answers
88 views

Gift exchange problem [duplicate]

Possible Duplicate: What's the General Expression For Probability of a Failed Gift Exchange Draw 4 couples are doing a gift exchange. Names are drawn randomly. Everyone gets a gift, but ...
1
vote
2answers
235 views

Let $G$ be a singular graph with $n=10$ and $|E|= 28$. Show that $G$ contains a cycle of length $4$

Let $G = (V(G),E(G))$ be a singular graph with $n=10$ and $|E|= 28$. Show that $G$ contains a cycle of length $4$. The question says it all. Our teacher gave us the hint that it is similar to ...
4
votes
1answer
273 views

Combination with repetition with an upper bound

I am trying to calculate the number of ways to divide $30$ oranges between $10$ kids, with the restriction that each kid will get no more then $5$ oranges. So, as far as I know I need to use the ...
1
vote
2answers
554 views

Simple Combinations with Repetition Question

In how many ways can we select five coins from a collection of 10 consisting of one penny, one nickel, one dime, one quarter, one half-dollar and 5 (IDENTICAL) Dollars ? For my answer, I used the ...
0
votes
1answer
77 views

A question about combination

Here is the question: Let $k,m,n$ be positive integers and $k\leq m\leq n$. Compute $$\sum_{\substack{a_1+\dots+a_n=m,\\ 0\leq a_i<k, \text{for } i=1,2,\ldots,n}}\frac{m!}{a_1!a_2!\cdots ...
4
votes
1answer
261 views

The generating function for permutations indexed by number of inversions

For $\sigma\in S_n$ an inversion is a pair $(\sigma_i,\sigma_j)$ such that $i<j$ and $\sigma_i>\sigma_j$. Could you help me to prove that the generating function of $S_n$ by number of ...
2
votes
0answers
113 views

Elementary symmetrical polynomial equations, whose solutions are known to be natural numbers.

Let $n_1,n_2,\dots,n_k$ be natural numbers (excluding 0), and for each $1\leq i\leq k$ let $\sigma_i(n_1,n_2,\dots,n_k)$ be the elementary symmetrical polynomial consisting of the sum of all products ...
6
votes
2answers
289 views

Different ways of coloring a $4 \times 4$ game board

In how many ways a $4 \times 4$ game board can be colored using four colors (red, green, blue, yellow) in such a way that each small square has a single color and the board looks exactly the same from ...
5
votes
1answer
213 views

Is there a name for this problem I can search for approaches on

I have a collection of a collection of numbers that I need to find the smallest number of groups to put them into whereas the distinct set of numbers in each set does not exceed a threshold. For ...
4
votes
1answer
108 views

random walk along edges of tetrahedron — which face gets hit last?

Suppose we have a tetrahedron $abcd$, and start at edge $ab$. Now walk to any "adjacent" edge (i.e. in this case any edge other than $cd$), each with equal probability $1/4$. This gives a stationary ...
6
votes
1answer
209 views

Laguerre polynomials and inclusion-exclusion

Does anyone know a reference for the solution of the generalized derangement problem via Laguerre polynomials? The Wikipedia article here says that this is an application of inclusion-exclusion, but ...
1
vote
0answers
45 views

How to solve this problem about discrete mathematics (Probability) [duplicate]

Possible Duplicate: Number of ways of spelling Abracadabra in this grid Determine the number of ways of spelling “mathematics” in the array below by following a path from top to bottom in ...
1
vote
1answer
458 views

Count the number of ways of four distinct numbers showing up when six dice are rolled

Suppose we roll six fair dice, how many ways can four distinct numbers show up?
4
votes
5answers
2k views

Count the number of integer solutions to $x_1+x_2+\cdots+x_5=36$

How to count the number of integer solutions to $x_1+x_2+\cdots+x_5=36$ such that $x_1\ge 4,x_3 = 11,x_4\ge 7$ And how about $x_1\ge 4, x_3=11,x_4\ge 7,x_5\le 5$ In both cases, ...
2
votes
3answers
216 views

Calculate the number of strings without more than two succeeding occurrences of any character

Problem: Given an arbitrary, finite alphabet $\Sigma$ with $|\Sigma| > 1$, define the language $\qquad L = \{w \in \Sigma^* \mid w \text{ has no subword of the form } aaa, a \in \Sigma\}$. Let ...
2
votes
1answer
177 views

graph avoiding cycle of length 4

let $G$ be a simple graph on $n$ vertices such that $G$ has no cycle of length $4$. show that $e(G)\le \frac{n}{4}(1+\sqrt{4n-3})$ where $e(G)$ denotes the number of the edges of the graph $G$.
3
votes
2answers
583 views

How many chips drawn with replacement until a duplicate is found?

Note - this problem is not homework. I'm studying for an exam and this problem is in our text (A First Course in Probability by Sheldon Ross) with no listed solution. The problem is: A jar ...
11
votes
4answers
1k views

Famous uses of the inclusion-exclusion principle?

The standard textbook example of using the inclusion-exclusion principle is for solving the problem of derangement counting; using inclusion-exclusion (and some basic analysis) it can be shown that ...
3
votes
3answers
206 views

Do these special power functions generate all homogeneous symmetric polynomials?

Over rational numbers, the set of all power functions up to a certain degree generate all symmetric polynomials in that degree. My question is as follows. To be succinct, let's say we have four ...
1
vote
2answers
110 views

Every number $n^k$ can be written as a sum of $n$ distinct odd numbers

I wish to prove that for $n,k\in\mathbb{N} > 1$, we can always write $n^k$ as a sum of $n$ odd positive integers. I have an idea of how to approach this, but my method seems to cumbersome. I am ...
2
votes
3answers
2k views

In how many ways can I climb down ten stairs, taking as many steps at a time as I like?

I want to climb down a flight of ten stairs, taking one or many steps at a time. In how many ways can I do this if I am able to take as many steps at a time as I like? I don't know the answer; I am ...
2
votes
1answer
139 views

How many integers less than $300$ is such that the sum of any two of them is not divisible by $3$?

Pam chose some numbers from $1$ to $300$ and wrote them down. As she observed her list, she noticed a peculiar fact that no two numbers on this list added up to a multiple of $3$. What can be ...
0
votes
1answer
1k views

Positive integers less than 1000 without repeated digits

How many integers from 1-999 do not have any repeated digits? The answer is explained in this link, but why is the last set 9*9*8? Why not 9*9*9?
7
votes
2answers
2k views

Algorithm wanted: Enumerate all subsets of a set in order of increasing sums

I'm looking for an algorithm but I don't quite know how to implement it. More importantly, I don't know what to google for. Even worse, I'm not sure it can be done in polynomial time. Given a set of ...
8
votes
1answer
1k views

Number of ways to put $n$ unlabeled balls in $k$ bins with a max of $m$ balls in each bin

The number of ways to put $n$ unlabeled balls in $k$ distinct bins is $$\binom{n+k-1}{k-1} .$$ Which makes sense to me, but what I can't figure out is how to modify this formula if each bucket has a ...
0
votes
3answers
67 views

Prove how many distinct elements in the set $\{ax \pmod{m}:a\in\{0,…,m-1\}\}$

There are $\dfrac{m}{\gcd(m,x)}$ distinct elements in the set $\{ax \pmod{m}:a\in\{0,...,m-1\}\}$ I have only known these by using a computer to generate the number of distinct elements. But I am not ...
8
votes
1answer
146 views

Probability of a number appearing in another number , like 31 in 2315?

How likely is it that a number of consisting of n digits, contains a number consisting of n digits or less? I though that perhaps I could multiply the number of permutations by the chance of such a ...
1
vote
1answer
1k views

Probability of a number being greater than A and less than B?

Let's say I will be presented with a random number from 0-9 (so 10 possibilities), but I am asked beforehand if I can make a prediction about its value. If I think it's greater than 2 I have 70% ...
3
votes
1answer
472 views

Combinatorial Argument

Can you give a Combinatorial argument that $$\binom{3n}{3}=3\binom{n}{3}+(3)(2)\binom{n}{2}\binom{n}{1}+\binom{n}{1}\binom{n}{1}\binom{n}{1}?$$
2
votes
3answers
98 views

Count points and lines in $\mathbb{A}^2(\mathbb{F}_p)$

Let $p$ be a prime, then $\mathbb{F}_p$ is a finite field. $\mathbb{A}^2(\mathbb{F}_p)$ is an affine plane. Number of points in $\mathbb{A}^2(\mathbb{F}_p)$ is $p^2$. I look at a line equation ...
6
votes
1answer
192 views

How many states in the game of hex?

I am trying to calculate how many unique states are possible to be in during a game of hex. The upper bound for an $n\times n$ board is $3^{n^2}$. This is ignoring gameplay and simply considering ...
5
votes
1answer
288 views

Counting barcodes

This certain problem is related to different combinations of strips in a barcode. The question is that how many different codes are possible in a barcode, reading from left to right, according to ...
3
votes
0answers
188 views

Expected value of the minimum of a random set of distances

You are given a rectangular $n_1\times n_2$ grid with one light bulb $b_i$ at every node. Each bulb is on or off with probability $p$ and $1-p$, respectively, and furthermore you know that exactly $m$ ...
8
votes
1answer
177 views

Two formulas for the minimal eigenvalue of a graph

Hello again everybody, I'm reading Fan Chung's monograph Spectral Graph Theory. In it, she has two formulas for the minimal eigenvalue of a graph. She doesn't explain why they're equivalent, and I'm ...
3
votes
3answers
479 views

Finding all positive integer solutions to $(x!)(y!) = x!+y!+z!$

The equation is $(x!)(y!) = x!+y!+z! $ where $x,y,z$ are natural numbers. How to find out them all?
0
votes
2answers
549 views

How many strings are there of $4$ or fewer lower case letters that have the letter '$x$' in them?

These problems always fumble me up. Just looking to see if my answer is correct. I found that: $4$ letters: $(26^3) \times 4$, $3$ letters: $(26^2) \times 3$, $2$ letters: $(26) \times 2$, $1$ ...
1
vote
1answer
238 views

A perpetual calendar cubes spinoff problem

Perpetual calendar cubes keep track of the date all year around. They must be turned (or even transposed) once a day. The following is a spinoff problem I'm having trouble with. Any hints are much ...
1
vote
2answers
220 views

Number of ways to represent a number as a sum of only $1$’s and $2$’s and $3$’s

How do I find the number of ways to represent a number as a sum of only $1$’s and $2$’s and $3$’s? I think the title is self-explanatory. E.g., if I have to represent $13$ as a sum of only ...