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
0answers
12 views

Smallest Parameter to Satisfy Exponentially Scaled Binomial Coefficient Inequality

Let $t$ be given, I am mainly interested in large $t$. Define $m(t)$ as below $$ m(t)=\min\left\{m: \sum_{k=0}^m \binom{t+k-2}{k} 2^{t+k} \geq 2^{2t}\right\}. $$ Is there a nice estimate for $m(t)$? ...
2
votes
0answers
55 views

Groups of 3 from 12 numbers

I need groups of $3$ numbers from $12$ without any repetition and I need $4$ sets of these groups of $3$ numbers. e.g. $1,2,3~~~4,5,6~~~7,8,9~~~10,11,12$ is the obvious first set of groups of $3$ ...
6
votes
0answers
56 views

When can we quit a game of War?

Consider the game of War. (The rules are below.) It would be nice to be able to end the game early. Suppose, for example, one player has 50 of the 52 cards. It is very likely that he's going to win. ...
1
vote
3answers
56 views

Color the edges of $K_6$ red or blue. Prove that there is a cycle of length 4 with monochromatic edges. [closed]

Color the edges of $K_6$ red or blue. Prove that there is a cycle of length 4 with monochromatic edges. Attempt: I know that i have to... prove that there must be TWO vertices with “red-degree” at ...
3
votes
1answer
24 views

When is the intersection of $k$ sets non-empty?

Suppose, given a ground set $S$, we have two subsets $A,B \subseteq S$. If we know that $|A|, |B| > \frac{|S|}{2}$, then we know that $A \cap B \neq \emptyset$. Can this be generalized to $k$ ...
0
votes
2answers
30 views

UpMultiset Combination-choose 3

Today I saw this question in a book: There are $12$ objects, $3$ of which are alike and the remainder all different. In how many ways can a selection of $5$ be made? I tried to answer: $k=11, ...
0
votes
2answers
40 views

In how many distinguishable ways can ten nickels, two dimes, and two pennies be arranged in a row?

In how many distinguishable ways can ten nickels, two dimes, and two pennies be arranged in a row?, assuming that the coins all have different dates and so are distinguishable from each other, and the ...
1
vote
2answers
46 views

The number $\binom{8}{4}$ is equal to the number of subsets of size 4 of the set $\{1, \dots, 8\}$

I was asked to proof if is true and give a counter example if it is false. However I prefer True. since all the numbers 1-8 insides the brackets are in the sets. I'm I correct?
2
votes
1answer
24 views

Expectation of the fraction a random function covers its range

Preamble: The number of onto functions from a set of $m$ elements to a set of $n$ elements is, as stated in this answer, computed as follows: $$n!{m\brace n}\;.$$ Now, let's count the number of ...
0
votes
1answer
33 views

Find a recurrence relation and associated generating function for the number of different binary trees with n leaves

Find a recurrence relation and associated generating function for the number of different binary trees with n leaves. I'm learning about recurrence relations, and I'm struggling more with defining my ...
-1
votes
0answers
29 views

Recursion related Binomial tough problem [closed]

Given $(1+x+x^2)^n = a_0+a_1x+...+ a_{2n} x^{2n}$. Prove that $$(r+1)a_{r+1}=(n-r)a_r+(2n-r+1)a_{r-1}$$
17
votes
1answer
2k views

Given a set of digits, what is the biggest number we can make using exponentiation - numberphile noodle quiz

The question is motivated by a question on a can of number noodles. Each item is a digit between $0$ and $9$. Clearly, if you form a string and consider it to represent a base $10$ integer, then ...
3
votes
3answers
107 views

Powers of two with coefficients $\{1, -1\}$

Given a vector $(n_0, n_1, \dots, n_l)$ where $n_i \in \{-1, 1\}$, $i = \overline{0, l-1}, n_l = 1$ and $l \in \mathbb{N}$. Prove that for all $a$ such that $$0 < a \leq 2^0n_0 + 2^1n_1 + \dots + ...
0
votes
0answers
16 views

name for pairs without repetition

Let $X:=\{x_i\}_{i=1}^k$, $Y:=\{y_i\}_{i=1}^k$, $\sigma$ a permutation on the index set $\{1,...,k\}$. Is there a name for the following set and or for an element in it: ...
-2
votes
1answer
50 views

Number of different groups given a list of repeating digits

Suppose that you are given the list[1,1,2,2] . The different groups that can be formed with this list are - ...
4
votes
0answers
28 views

More elegant derivation of the shift in median bin occupancy

In answering Median of a multinomial variable, I found to my own surprise through a somewhat tedious calculation that the expected value of the median of the ball counts in $3$ bins into which $n$ ...
0
votes
1answer
14 views

Counting monomials with $k$ variables

Say we expand $\left(\sum_{i=1}^n x_i\right)^k$ into monomials. If $k=3$ there are $3n(n-1)$ monomials with two variables: $3x_1x_2^2 + 3x_1x_3^2 +\dots + 3x_1^2x_2 + \dots$. Is there a closed form ...
1
vote
0answers
23 views

Understanding the expansion of product notation.

I have a question regarding the expansion of product notation in the picture below. Equation 3.1 in the attached picture is ...
0
votes
2answers
35 views

Laurent Series Expansion Logic

Relative to the below image, I am curious about the progression from equation 3.2 to equation 3.3, then from equation 3.3 to equation 3.4. I understand the logic in 3.2. I understand that a Laurent ...
0
votes
2answers
14 views

Whether the equality $C^{m}_{2m}=\Sigma_{i=1}^{m}C^{i}_{m+1}C^{i-1}_{m-1}$ holds or not?

I've tried some values of $m$, and found that the equality $C^{m}_{2m}=\Sigma_{i=1}^{m}C^{i}_{m+1}C^{i-1}_{m-1}$ holds. But I can't give it a proof. Can anybody give some suggestions?
-1
votes
0answers
11 views

a design property in ring theory [closed]

Characterize all finite commutative rings with the following property. There is a number $\lambda$ such that every unit can be expressed in exactly $\lambda$ ways as the sum of two units.
0
votes
3answers
30 views

Iteration of $A_{n}(q)=q^nA_{n-1} (q)$

I can't seem to find how $A_{n}(q)=q^nA_{n-1} (q)$ iterates to $$A_{n}(q) = q^{n+1 \choose 2}A_{0}(q)$$ Where ${a \choose 2} = a(a-1)/2$ and absolute value of q is less than 1. I understand that I ...
1
vote
1answer
33 views

About finding formula for an additive-combinatorial quantity

The definitions: Let $n \in \mathbb{Z}^+$. A positive integer $L$ is called $n$ -magnificent if in every partition of $\{ 1, ... , L \}$ into $n$ non-empty parts, at least one part contains an ...
0
votes
0answers
13 views

Is there such a thing as a Negative Poisson Binomial?

The Poisson Binomial distribution is a generalization of the binomial for non-equiprobable Bernoulli trials. The negative Binomial give the number of Bernoulli trials until a number of success is ...
1
vote
2answers
53 views

Find the expected value when you roll n dice and the number of pair on the dice adds up to 7?

You roll $n$ fair dice. Let X be the number of pairs of dice that sum to $7$. Write $X$ as a sum of indicator variables and find $E[X]$ This is how I approached the problem Let $S$ be all the ...
1
vote
1answer
27 views

Find a functional equation for the generating function whose coefficients satisfy the relation

Find a functional equation for the generating function whose coefficients satisfy the relation: $\qquad{}$ $a_n = 3a_{n-1} -2a_{n-2}+2, a_0=a_1=1$ When I solve this, I get the function ...
0
votes
0answers
27 views

How many “words” can be formed by rearranging INQUISITIVE [closed]

How many “words” can be formed by rearranging INQUISITIVE so that U does not immediately follow Q?
0
votes
1answer
58 views

while reading $limits$ I thought of this $ \dbinom{x}{y}$ where $y \to x^+$

while reading $limits$ I thought of this $ \dbinom{x}{y}$ where $y \to x^+$, as per my opinion, I think the correct answer to be $undefined$ as $\dbinom{x}{y}$ is defined only when $x \geq y $ but ...
0
votes
1answer
24 views

Making a string with pieces of different length and fabric

You are making a string and have access to pieces of two different lengths, of length 1 inch and of length 2 inch. The 1 inch pieces come in 5 different fabrics and the 2 inch pieces come in 4 ...
0
votes
1answer
27 views

Finding the probability of a random graph?

How do I approach this problem? I am new to the topic and I am having a hard time figuring this out. For Erdos-Renyi graphs on $3$ vertices with parameter p, find the probability there is an edge ...
31
votes
9answers
2k views

why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$

why is $\sum\limits_{k=1}^{n} k^m$ a polynomial with degree $m+1$ in $n$? I know this is well-known. But how to prove it rigorously? Even mathematical induction does not seem so straight-forward. ...
1
vote
1answer
35 views

v1 deg out = zero?

My Attempt Yes it is true. There is one directed edge between two vertices and you can see that there is one vertex that the out-degree is zero. If you want to fix that, you can add a vertex and a ...
0
votes
0answers
53 views

min-max problem

Hello to everybody: I'm trying to prove that : Let $A$ be the incidence matrix of a clutter (simple hypergraph) $C$. Prove that the vertex covering number and the matching number of $C$ satisfy: ...
0
votes
2answers
49 views

Craps probability: What value of x makes this a fair game?

You are playing Craps at the casino. In each round of Craps, two 6-sided dice are rolled. You place a bet as follows: You wager 1 dollar. If a 5 is rolled you win x dollars. If a 7 is rolled, you ...
3
votes
3answers
63 views

How to show that in a subset of [0,1] of measure greater than 0.5, there exist two points at distance exactly 0.1?

My attempt: Let's disregard isolated points as they do not contribute to measure. If our set is union (disjoint) of finitely many, say $n$ intervals, there must be at least ($n-1$) intervals of ...
0
votes
1answer
17 views

Proof graph theory(length of a path)

In $G$ simple graph every vertex has the degree of $\delta$. Proof, that in $G$ graph there is at most one $\delta$ long path. I think that I should use in some way the Hamilton path, which says ...
-2
votes
1answer
37 views

Number of paths of length 2 in a complete graph containing n vertices [closed]

How many paths of length 2 does $K_n$ have? Where n is the number of vertices. I initially thought it should just be $n \choose 2$ but was told that was incorrect? Is there something I'm missing ?
1
vote
3answers
30 views

Generating function, determining coefficient

Here is a question I encountered the other day: Determine the coefficient of $x^{98}$ in the following generating function: $$f(x)=\frac{x}{(1-2x)^{21}}$$ I'm thrown off a bit by the large exponent ...
3
votes
1answer
78 views

How to prove that $n! = n^n - C_{n,1} (n-1)^n +C_{n,2} (n-2)^n - \cdots $?

How to prove that $n! = n^n - C_{n,1} (n-1)^n +C_{n,2} (n-2)^n - \cdots\,{} $? I faced this problem when trying to find the number of onto functions possible from one set having n elements to ...
0
votes
1answer
27 views

Colouring $K_{2s-1}$

Suppose we 2-colour $K_{2s-1}$ such that no vertex has more than one blue edge incident to it, prove that the graph contains a red $K_s$. I've never seen a Ramsey theory question like this and am ...
26
votes
7answers
20k views

In how many ways can a number be expressed as a sum of consecutive numbers?

All the positive numbers can be expressed as a sum of one, two or more consecutive positive integers. For example 9 can be expressed in three such ways, 2+3+4, 4+5 or 9. In how many ways can a number ...
1
vote
1answer
60 views

An interesting puzzle from Jiří Matoušek's book

There is an interesting puzzle from Jiří Matoušek's book Invitation to Discrete Mathematics, problem 1.2.8, which confused me lots of time. Divide the following figure into $7$ parts, all of them ...
1
vote
0answers
15 views

Chromatic index of complete graphs using line graphs

I'm interested in computing $\chi'(K_n)$ from the relation $$\chi'(K_n)=\chi(L(K_n)),$$ where $L$ denotes the line graph operator. Is there a good argument to do this? (The answer is of course $=n-1$ ...
4
votes
1answer
132 views

The Probability $P_{[m]}$ that exactly $m$ among the $N$ events $A_1,\dots,A_N$ occur simultaneously

For $1\le i_1,i_2,...,i_k\le N$ denote $$p_{i_1,...,i_k}=\Pr(A_{i_1}\cap A_{i_2}\cap\dots\cap A_{i_k}),$$ $$S_k=\sum\limits_{1\le i_1\le\dots\le i_k\le N}p_{i_1,\dots,i_k}.$$ Show that ...
1
vote
1answer
31 views

On the eigenvalues of “almost” complete graph ?!

Preliminaries: Let $K_n$ be the complete graph on $n$ vertices. $|E(K_n)|=\frac{n(n-1)}{2}$. It's well known that the eigenvalues of $K_n$ are $n-1$ with multiplicity 1, and -1 with multiplicity ...
1
vote
2answers
14 views

Complete bipartite graph from 2 to m points

How can I show that $K_{2,m}$ is planar for all m? I can't even seem to draw $K_{2,2}$ without intersection and if I draw it as a square then it seems to fail to be bipartite as the second set lies ...
0
votes
1answer
21 views

Sampling with replacement

How-many distinct samples of size $n$ can be drawn with replacement from the population ${u_1, u_2,......, u_n}$ of $n$ units ? I have considered the number of ways in which $n$ units can occupy $n$ ...
0
votes
0answers
56 views

How to distribute $n$ balls of different kinds among $n$ baskets of different kinds? Non-trivial combinatorics/permutation task

I have a task that I don't know how to approach. There are $n$ baskets of four types; $n$>1000. Each basket fits exactly one ball. Number of balls equals number of baskets. Balls are of different ...
1
vote
1answer
14 views

Number of faces of connected plane graph with cycles

Suppose $G$ is a connected plane graph with at least $g$ edges containing no cycles of length smaller than $g$, then if $f$ is the number of faces and $e$ is the number of edges then prove that $f ...
0
votes
1answer
28 views

Multiset Combination

How many Combinations can you make with the set {1,1,2,3,4} taken 2 at a time? If I do this in the way I do in Permutation: C(5,2) / 2!, I end up in wrong answer. Actually, there are 7 Combinations: ...