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. Combinatorics is a ...

learn more… | top users | synonyms (4)

3
votes
3answers
131 views

Find the coefficient for a term in an expression

We have the expression: $$( 1 + x^1 + x^2 + x^3 + \dots + x^{27})(1 + x^1 + x^2 + \dots + x^{14})^2$$ For this expression how do you calculate the coefficient of $x^{28}$? I know the answer is ...
4
votes
1answer
120 views

Give a combinatorial proof of the recurrence relation

Let $F_n$ be the number of forests on the vertex set $V = \{1,2,\ldots,n\}$(Thus we are counting labelled forests). Give a combinatorial proof of the recurrence relation $$F_n = \sum_{i=1} ...
0
votes
1answer
170 views

Number of times the integer $3$ occurs in all $2^{n-1}$ compositions of $n$ [duplicate]

Suppose $n\ge4$. Show that in a list of all $2^{n-1}$ compositions of $n$, the integer $3$ occurs exactly $n2^{n-5}$ times. [Hint: Look at ways of drawing lines between n dots.] The number of k-term ...
4
votes
1answer
154 views

No induced ordered graph yields large clique/stable set in ordered graph

Let $H$ be the ordered graph with three vertices $v_{1}$, $v_{2}$, $v_{3}$ (in this order) and one edge $v_{1}v_{2}$. Prove that there exists $c > 0$ such that every ordered graph $G$ not ...
9
votes
6answers
688 views

Books for combinatorial thinking

I have looked through many discrete mathematics books but they don't put much emphasis on combinatorial thinking.What books could you recommend that are more problem-oriented and emphasize ...
2
votes
0answers
86 views

Longest consecutive subsequence bound with limit

Let $S\subseteq \{1,2,\ldots,n\}$ and let $X(S)$ be the length of maximal consecutive subsequence in $S$. For example: if $S=\{4,5,7,8,9,11,12\}$ then $X(S)=3$ because of the subsequence $\{7,8,9\}$. ...
4
votes
1answer
108 views

An algorithm for pairing within a set

I have $2n$ countries and I want to pair them and have $n$ groups according to Euclidean distance, for instance, I want to minimize the sum of Euclidean distances. I have a $2n \times 2n$ symmetric ...
1
vote
1answer
64 views

Finite sets with density

For every $a\in(0,1]$ (and every $\epsilon>0$) there exists a number $M\geq 1$ such that whenever $X$ is a finite set and $A_1, \dots, A_M \subset X$ are subsets with $\frac{\# A_1}{\# X}, \dots, ...
2
votes
4answers
460 views

How many tetrahedrons in a tetrahedron?

Given a regular tetrahedron. All the edges were divided into N equal segments. How many non-degenerate ($|\text{volume}| > 0$) tetrahedrons with vertices at the points of division can be built ...
0
votes
1answer
600 views

Combinatorics Issues

I have three homework questions, all of which have the mutual problem of combinatorics The first one: A library subscribes to two different weekly news magazines, each of which is supposed to ...
1
vote
1answer
154 views

Submodularity of the product of two non-negative, monotone increasing submodular functions

I'm trying to prove the submodularity of the product of two non-negative, monotone increasing submodular functions Formally, we have $f$ and $g$ are submodular functions, that is, ...
3
votes
1answer
775 views

Partition an integer $n$ into exactly $k$ distinct parts

I know how to find the number of partition into distinct parts, which is necessarily equal to the number of ways to divide a number into odd parts. I also know how to partition n into exactly k parts. ...
6
votes
2answers
118 views

A question on Hamming metric/distance

Suppose $\sf{X}=\{0,1\}$, and $\sf{X}^n$ is the set of all binary sequences of length $n$. So the first question is that what does it mean by the convex closure of a subset $\sf{A}$ of $\{0,1\}^n$, ...
0
votes
4answers
129 views

Cardinality of a set $\{A,B\}$ $A$ is a subset of $B$, which is a subset of $S$

Let's say that $A$ is a subset of $B$ and be is a subset of a set $S$ of $n$ elements. How big is the set $\{(A,B)\}$ then.
2
votes
3answers
304 views

Prove that the combination formula can be reduced to…

Prove that: $$\frac{m!}{k!(m-k)!} = \frac{m}{k}\frac{m-1}{k-1}\cdots\frac{m-k+1}{1}$$ It's quite obvious when I write down some terms, but I just don't know how to make a rigorous proof. Any hints ...
7
votes
1answer
195 views

Probability that a $3\times 3$ matrix with entries in $\{0,1,2,3\}$ is invertible.

Let $A$ be a $3\times 3$ matrix, and each of its entries takes value from $\{0, 1, 2, 3\}$ with probability $1/4$ for each value. What is the probability that A is invertible? I have tried to list ...
2
votes
4answers
418 views

Permutation Theorem

I am reading about permutations, and came across this theorem, which has an accompanying proof. I was wondering if anyone knew of an example, that they could provide, when I would have to use the ...
5
votes
2answers
197 views

combinatorial descents finding the number of permutations with criteria

I need help with the following: Define a descent of a permutation to be $j$ when $p_{j+1} < p_j$. Then the descent set of a permutation is the set of all descents. For example, the ...
4
votes
3answers
125 views

In how many ways we can arrange two strings with distinct elements such that the order is intact?

In how many ways we can arrange two strings (with distinct elements) such that the order is intact? For example if the strings are , "aA" and "bk". The valid arrangements are: ...
1
vote
1answer
123 views

How to find (or 'generate') combinatorial meaning for the given expression

$\left(\dfrac{6(k-n)(k-1)}{(n-2)(n-1)}+1\right)\dfrac{30}{n(n+1)(n+2)}$ (for $n\geq 3$ and $1\leq k \leq n$) The expression comes from question Please help to find function for given inputs and ...
0
votes
1answer
134 views

Counting the number of possibilities

I have given number of y string variables. Assignments to these y variables can be done in only following: Right hand side of ...
1
vote
1answer
168 views

What is the probability for sequence of length $L$ in subset of $[n]$

I am trying to calculate the probability that I'll have a sequence of length $L$ in a random subset of $[n]$ when the subset size is $k$. For example, if $n=5$, $k=4$ and $L=2$ I'll have the ...
4
votes
1answer
55 views

Combinatorics of symmetric elements in $M_n(F_m)$

One of my tutees asked me a question about the number of such matrices, and I'm stumped: In the set of matrices of dimension $n\times n$ over a finite field $F_m$, we want to ask how many are ...
1
vote
1answer
97 views

Probability of two binomial trials of N tests with P=x having same outcome in 1<=Z<=N places.

As stated in title. I have an existing result (the target) of a binomial experiment of length N trials with P(success)=x. Is there an analytic/closed-form way of getting probability that a new trial ...
3
votes
2answers
1k views

Finding coefficient of generating function

Find the coefficient of $x^{52}$ in $$(x^{10} + x^{11} + \ldots + x^{25})(x + x^2 + \ldots + x^{15})(x^{20} + x^{21}+ \ldots + x^{45})$$ One thing I tried doing was factoring out $x^{10}, x, ...
1
vote
0answers
253 views

Constrained Permutation Problem

This isn't homework -- just a problem I came up with to test my skills. I failed, for now. A teacher must arrange $n$ students into a line, but $k$ pairs of the students cannot stand one ...
2
votes
3answers
284 views

Enumerating Rooted labeled trees without Langrange inversion formula

I am wondering how to enumerate rooted labeled trees without the Langrange inversion formula. Because each tree is a collection of other trees, the recursive generating function becomes $$C(x) = x + ...
0
votes
1answer
62 views

Counting and set operations

Assuming I have items that each have an optional set of attributes. i.e. Item1[A], Item2[B], Item3[A,B], Item4[A,C], Item5[] And I have the count of each occurrence, i.e.: A = 3 (A has occurred 3 ...
1
vote
1answer
389 views

What is the minimum number of moves of solve the puzzle?

There is board in which there are $m\times m$ boxes each assigned an a non zero integer except one box which is marked as $0$ and is treated as vacant. Only the vertical and horizontal neighbors of ...
1
vote
0answers
63 views

combinatorial proof of Fibonacci identities [duplicate]

Give a combinatorial proof to each of the Fibonacci identities: $$nF_0+(n-1)F_1+\dots\dots+2F_{n-2}+F_{n-1}=F_{n+3}-(n+2)$$ and $$ F_2+F_5+\dots\dots+F_{3n+1}=\frac{F_{3n+1}-1}{2} $$ Assume that ...
0
votes
1answer
77 views

group theory - function into function

There is a group $A$ and it has $12$ elements, lets look at all the functions $A$ to $A$ which has the next trait: $a\in A, f(f(f(a)))=a$, but , $f(f(a))\neq a$. Prove its an Injective and ...
5
votes
1answer
75 views

Given $A$ and $B$, how many positive integers $N$ such that $N\times B$ has at least one divisior $D$ that lies in $N \lt D \le A$?

For two integers $A$ and $B$, how can we find the number of positive integers $N$ such that $N\times B$ has at least one divisior $D$ that lies in $N \lt D \le A$? For example, if $A = 100$ and $B = ...
14
votes
2answers
650 views

In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard?

Given $N,M$ with $1 \le M \le 6$ and $1\le N \le 36$. In how many ways we can place $N$ knights (mutually non-attacking) on an $M \times M$ chessboard? For example: $M = 2, N = 2$, ans $= 6$ $M = 3, ...
0
votes
1answer
93 views

Finding a recurrence relation for the Josephus problem if we're looking at the person before the person who lives

Consider the Josephus problem. Let $L(n)$ be the number of the next to last person left standing. Find $L(12)$ and $L(13)$. Derive a recurrence for $L(n)$. I know that the Josephus problem is ...
1
vote
3answers
55 views

The elements in a recursive set

I have a set of numbers that is defined in the following way: $a_1 = \{1,-1\}$ $a_2 = \{2,0,0,-2\}$ $a_3 = \{3,1,1,-1,1,-1,-1,-3\}$ $a_n = \{a_{n-1} +1 , a_{n-1} -1 \}$ i.e. at each step we ...
1
vote
0answers
100 views

Probabilistic results on the elementary symmetric polynomials

The elementary symmetric polynomials of degree $k$ in $N$ variables are defined as $$e_k(x_1, \ldots, x_N) = \sum_{(i_1,\ldots,i_N) \in I_k^N}{x_1^{i_1}\ldots x_N^{i_N}}, \quad 0 \le k \le N$$ with ...
2
votes
1answer
160 views

Upper bound for ramsey number $r(a_1,\ldots, a_m)$

I am looking for any (finite) upper bound of the ramsey number $r(a_1,\ldots, a_m)$. I can prove the well known fact for any positive integers $a,b$ there is a $c$ for which $c\ge r(a,b)$ by taking ...
2
votes
1answer
189 views

Count the subsets of [n] whose sum is modulo $2^k$

Prove that for all $k \geq 1$ and $n \geq 2 ^{k-1}$, the number of subsets of $\{1,2,3\cdots n\}$ with sum congruent to $i$ mod $2^k$, equals the number with sum congruent to $i+1$ mod $2^k$, for all ...
1
vote
1answer
141 views

Elementary Generating Function Models

An international singing contest has $5$ distinct entrants from 50 different countries. Use a generating function for modeling the number of ways to pick $20$ semifinalists if there is at most $1$ ...
0
votes
1answer
269 views

how many combinations on a variable number of items?

I havent done combinations in forever, so I have no idea howto do this... I have an unknown quantity of items in a set, and I need to figure out how many combinations there are of 35 unique items ...
1
vote
1answer
125 views

A Combinatorial Question to Solve a System of Equations [duplicate]

Suppose we have $N$ integer-valued variables $i_1$, $i_2$, $\cdot\cdot\cdot$, $i_N$, such that each variable can take integer values from 0 to $k$, and the sum of these $N$ variables is also equal to ...
2
votes
1answer
151 views

applying multi-section formula to find convergence

The question asks to use the multi-section technique to determine if $$\sum_{n>=0} (a^n)/(4n +1)!$$ converges, and to provide a finite expression for the exact value of the series. The multi ...
1
vote
1answer
102 views

What is the bijection in this combinatorics example?

Example 3.19. A medical student has to work in a hospital for five days in January. However, he is not allowed to work two consecutive days in the hospital. In how many different ways can he ...
0
votes
1answer
58 views

Does $ \sum_{k = 0}^{\infty} \sum_{n = 0}^{\infty}\frac{B^k C^{(n+k+1)}}{(ib)^n k! (n+k+1)!}$ converge?

In relation to my question: Finding the residue of function with Laurent series $\sum_{n=0}^{\infty}\sum_{k=0}^{\infty}\frac{y^n(A+By+Cy{^-1})^k}{\beta (\beta i)^n \ k!}$ I need to find an expression ...
0
votes
0answers
48 views

Name for a type of combinatorial design?

Let $X$ be a ground set, and consider a collection $\mathscr{S}$ of subsets of $X$, $\mathscr{S} = \{S_1, \dots, S_n\}$. We would like to find a collection $\mathscr{S}'$ with the property that for ...
2
votes
3answers
5k views

probability selecting marbles

can someone solve this example? An urn contains 2 Red marbles, 3 White marbles and 4 Blue marbles. You reach in and draw out 3 marbles at random (without replacement). What is the probability that ...
0
votes
2answers
41 views

probability of events problem

need help with this problem, can someone walk me through how to do this problem Let A and B be events with P(A) = 3/7 ; P(B) = 1/2 and P((A U B)c) = 3/8. What is P(A ∩ B)?
2
votes
3answers
215 views

Can $n(n+1)2^{n-2} = \sum_{i=1}^{n} i^2 \binom{n}{i}$ be derived from the binomial theorem?

Can this identity be derived from the binomial theorem? $$n(n+1)2^{n-2} = \sum_{i=1}^{n} i^2 \binom{n}{i}$$ I tried starting from $2^n = \displaystyle\sum_{i=0}^{n} \binom{n}{i}$ and dividing it ...
0
votes
1answer
93 views

probability of selecting dvds

studying for a test, cant figure out this probability problem A bin at Blockbuster contains 100 DVD's of which 20 are defective. You randomly select 10 and try them out at home. You discover that ...
-4
votes
1answer
59 views

Binom formula.Generalize and prove.

Given the identity: $3^n = \sum_{i=0}^{n} \binom{n}{i} 2^i$ Generalize it and prove your statement.