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
552 views

number of ways to divide an array into m sets of equal sum

I recently came across this question: Find the number of ways to divide and array into m subarrays of equal sum? Ex: given a[]= {1, 1, 2, 3, 4, 5}, m= 2 ...
4
votes
0answers
45 views

Terminology in graph theory

Let $G$ be a finite graph with the following property: For any vertex $a$ and edge $\{b, c\}$ of $G$, there is an edge connecting them: there is one of $\{a,b\}$ or $\{a, c\}$ in $G$. Is there ...
1
vote
2answers
25 views

Interpretation of double factorial solution to a problem of pairing two types of objects

I'd like a clarification about or some insight into one possible form of solution to the following problem: Suppose that each of n sticks is broken, into one long and one short part. The 2n ...
5
votes
4answers
240 views

Outline for high school combinatorics class?

I am a high school student and I have taken all the math classes that my school provides (through calculus AB). I have been looking at a possible independent study for next year and I have landed on ...
1
vote
1answer
19 views

Number of decompositions in sum of $s$ elements

Let $E=\{ 3^k+3^l; 0\leq k\leq l\}$. For all $n\in \mathbb{Z}$ and $s \geq 1$ denote $r_s(E,n)$ the cardinality of $$ \{(n_1, \ldots ,n_s) \in E^s, n_1+\ldots +n_s=n \}.$$ I'm looking for an upper ...
12
votes
5answers
2k views

Combinatorial proof of a binomial coefficient summation.

Let $n$ and $k$ be integers with $1 \leq k \leq n$. Show that: $$\sum_{k=1}^n {n \choose k}{n \choose k-1} = \frac12{2n+2 \choose n+1} - {2n \choose n}$$ I was told this is supposed to use a ...
0
votes
1answer
27 views

Length of substring if we just consider a subdivision in $\log n$ substrings

Let $u$ be a string of length $n$ and consider a subdivision in $\log n$ substrings $u = u_1 u_2 \cdots u_{\log n}$. Is it true that there exists a constant $C$ such that for each $1 \le i \le \log n$ ...
1
vote
1answer
34 views

How to come up with this recurrence relation for putting p rooks in a m×n chessboard?

I have a m×n chessboard and I have to put p rooks in the board so that no two of them are in attacking position. (Two rooks attack each other if they are in the same row or same column) How many ways ...
2
votes
2answers
338 views

A cog wheel math puzzle

A machine has 4 cog wheels in connection. The largest wheel has 242 teeth and the others have 66,48 and 26 respectively. How many rotations must the largest wheel make before each of the wheel is back ...
0
votes
0answers
50 views

Finding permutation matrix

Let $P_{\pi}$ denote a permutation matrix associated to the permutation $\pi:\{1,...,n\}\rightarrow \{1,...,n\}$ and $\sigma$ denote the cyclic permutation $(1 2 ...n)$. If T is the $n\times n$ lower ...
1
vote
2answers
73 views

How many ways to arrange the seating?

The Annual Interplanetary Mathematics Examination (AIME) is written by a committee of five Martians, five Venusians, and five Earthlings. At meetings, committee members sit at a round table with ...
0
votes
1answer
31 views

Total number of triangles that can be made by $4n$ points, $n$ at each side of square

We are given a square with $n$ points on each side of the square. None of these points co-incide with the corners of this square. We have to compute the total number of triangles that can be formed ...
5
votes
1answer
92 views

How to evaluate this double infinite sum (Catalan number)

Let $C_n = \dfrac{1}{n+1}\binom{2n}{n}$. Is it possible to find the exact value of this infinite sum ? $$\sum_{n=1}^\infty \sum_{k=n}^\infty ...
2
votes
3answers
594 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 ...
2
votes
1answer
60 views

sample variance of regular polygon upon superimposition of vertices

Given, the vertices of a regular polygon, the centroid here would be the sample mean of the vertices and we assume it to be at the origin. The distance from each vertex to centroid is ...
3
votes
0answers
77 views

A sequence of polynomials [duplicate]

I posted this question a while back, and I think I may not have made myself clear or shown what I got so far. So let me post this question again with more information and clarification. I have a ...
1
vote
1answer
444 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
89 views

Ordering $2n$ numbers

In how many different ways can you order $2n$ different numbers with alternating $<,>$ signs? An example for the case where $2n=6$ is $$1<3>2<6>4<5>1$$ ...
1
vote
1answer
48 views

How many binomials are divisible by $p$?

Let $N$ be a interger (maybe $10^{15}$) and $p$ be a prime number less than $N$. How many binomials ${n}\choose{k}$, where $n<N$, divisible by $p$? we already know that ${pm}\choose{pn}$ $\equiv$ ...
1
vote
2answers
377 views

ln how manyways can we distribute $7$ apples and $6$ oranges among $4$ children so that each child gets at least one apple.

In how many ways can we distribute $7$ apples and $6$ oranges among $4$ children so that each child gets at least one apple? I think this can be solved by using permutations because the word ...
2
votes
0answers
48 views

inclusion-exclusion principle working

We have $n$ non-negative integers $a_1, a_2, \dots, a_n$. We will call a sequence of indexes $i_1, i_2, \dots, i_k$ such that $1\le i_1 < i_2 < \dots< i_k\le n$ a group of size $k$. How many ...
2
votes
1answer
22 views

Number of square matrices of order $n$ where each row and each column has at most one $1$

What is the number of square matrices of order $n$ with the property that each row and each column has at most one $1$, and $0$s elsewhere? For example, when $n=2$, there are $7$ such matrices: ...
4
votes
0answers
33 views

How many ways I can put $k$ bishops on $n\times n$ chessboard?

Is there a formula how to count in how many ways I can put $k$ bishops on $n\times n$ chessboard such that no two bishops threaten each other?
1
vote
2answers
32 views

Reduce Combination Formula

Hey i have to write a code for this: You can refer here: Picking Same Color Probability For the entire question. $\Pr(Success)=$$\sum\limits_{k=1}^{\min(m,n)}\frac{{m\choose k}\cdot{nm-m\choose ...
3
votes
0answers
31 views

Which graph with an automorphism group isomorphic to the quaternion group $Q_8$ minimizes $|V|+3|E|$?

In Symmetries of partial Latin squares, it is shown that for any graph $\Gamma=(V,E)$ with automorphism group $G$, there is a partial Latin square with $|V|+3|E|+49$ filled cells whose autotopism ...
3
votes
3answers
3k views

How to use stars and bars (combinatorics)

How to use the stars and bars method? Say I want to find number of combinations I can get with $x_1+x_2+x_3+x_4=22$, where $x_i\in\mathbb{N}$. Is this the correct time to apply the method?
5
votes
1answer
563 views

Permutations of a set with a conditional subset

Using the digits 1, 2, 3, 5, 6, 8, 0 only once, how many 4-digit numbers could be constructed if the number is even? This is an exercise from an online course I'm taking. The given solution suggests ...
2
votes
2answers
102 views

Prove $\sum\limits_{i=0}^{n}\binom{n+i}{i}=\binom{2n+1}{n+1}$ [duplicate]

I'm trying to prove this algebraically: $$\sum\limits_{i=0}^{n}\dbinom{n+i}{i}=\dbinom{2n+1}{n+1}$$ Unfortunately I've been stuck for quite a while. Here's what I've tried so far: Turning ...
2
votes
2answers
24 views

Sunflower Lemma - Allow Duplicates?

The sunflower lemma states that if we have a family of sets $S_1, S_2, \cdots, S_m$ such that $|S_i| \leq l$ for each $i$, then $m > (p-1)^{l+1}l!$ implies that the family contains a sunflower with ...
2
votes
1answer
83 views

Range of inner product of a sequence and its permutation

$a^n :=(a_i)_1^n$ is a finite sequence of real numbers of length $n$, where $\sum\limits_{i=1}^n a_i=0$ and $\sum\limits_{i=1}^n a_i^2=1$. Consider $s_n(a^n,\sigma):=\sum\limits_{i=1}^n ...
3
votes
1answer
45 views

find a group of lowest N numbers so that no 2 pairs have the same bitwise or

I am trying to find the lowest group of N numbers (i.e. N=1000) so that no 2 pairs from the group have the same bit-wise or. more specific need to find a group $A = \{a_1,a_2,a_3,..,a_N\} $ such ...
0
votes
1answer
322 views

Mini Sudoku -Critique of Solution-

"Let's play mini-Sudoku! We wish to place an "X" in four boxes, such that there is exactly one "X" in each row, column, and 2x2 outlined box. In how many ways can we do this?" Solution: " Using ...
0
votes
1answer
348 views

Probability of picking exactly one correct from a pool of 6 incorrect and 4 correct

So as the question says. You have 6 incorrect objects and 4 correct ones. What are the odds that, when picking 3 of them at random, you end up with exactly one of them being correct. This seems to be ...
1
vote
0answers
46 views

Calabi-Yau Toric Varieties

This is a rather naive question, but, from what I understand, we begin with a some reflexive polytope $P$. From the basic theory of toric varieties, we can construct a toric variety corresponding to ...
1
vote
1answer
760 views

How to find different number of distinct integers from given set of number

How many different integers can be expressed as the sum of $3$ distinct numbers from the set $\{3, 10, 17, 24, 31, 38, 45, 52\}$? Could someone help me with this problem?
3
votes
2answers
89 views

Interesting facts and problems to motivate high school combinatorics students

I will give some classes in combinatorics to high school students and I would like to know some facts (and proof) I can show to my students to motivate them to study this beautiful subject. I'm ...
0
votes
2answers
54 views

How to calculate combinations count for this problem

I will explain my question using simple example, cause I don't know to descrive it properly. If we have 2 numbers $\{a,b\}$, by comparing them, we get 3 possible combinations: $$a>b, \hspace{3pt} ...
0
votes
1answer
380 views

Book on discrete mathematics for self study

I am searching for book on discrete mathematics which is suitable for self study. This mean I want it to have exercises with answers (It would be ideal if it had solutions). I have already read ...
18
votes
2answers
214 views

How many pairs of nilpotent, commuting matrices are there in $M_n(\mathbb{F}_q)$?

As a follow-up to this question, I've been doing some work counting pairs of commuting, nilpotent, $n\times n$ matrices over $\mathbb{F}_q$. So far, I believe that for $n=2$, there are $q^3+q^2-q$ ...
0
votes
2answers
28 views

Bowl containing candy; how many handfuls of 15 are possible (with extra conditions)?

Assume that you have a bowl containing hard candies: 50 cherry 50 strawberry 40 orange 70 lemon 40 pineapple Assuming that the pieces of each flavor are identical, ...
0
votes
5answers
94 views

Help needed to solve combinatorics problem.

I have been revisiting my old probability courses and I found a problem, which I can't figure out how to solve or at least what I get differs from the answer in the book. The problem reads as ...
1
vote
1answer
164 views

On the probability that $\sum\pm b_i=0$ for some given $(b_i)$

Let $b_i, i=1,\ldots,m$ be real numbers. Let $r_i, i=1,\ldots,m$ be random variables with $P(r_i=1)=P(r_i=-1)=1/2$. Consider group $\Pi_m$ of all permutations of the set $\{1,\ldots,m\}$. On the ...
1
vote
3answers
126 views

Combination sum .

I want to evaluate the following sum : $$S(k,k')=\sum_{i} C_{i+k}^k C_{k'-i}^{k}$$ = $$S(k,k')=\sum_{i} \binom{i+k}{k} \binom{k'-i}{k}$$ I tried some steps but couldnt get further than : ...
1
vote
4answers
34 views

Question on Permutations Please advise

Among all seven digit decimal numbers,how many of then contain exactly three 9's? My Approach: 3 places contains only 9's---> 1*1*1 (No. of Ways to Choose out of 0 to 9) other 4 places: since first ...
1
vote
0answers
23 views

How to calculate the $k$-dimension of a subspace of a polynomial ring?

Let $k$ be an infinite field and $R:=k[x_1,...,x_n]$ the polynomial ring in $n$ indeterminates. Why is the $k$-dimension of $U$ given by $\begin{pmatrix} n+m-1 \\ m\end{pmatrix}$, when $U$ is the ...
2
votes
2answers
40 views

Size of a maximum matching of a complete multipartite graph?

Let $G=(V,E)$ be a complete multipartite graph on even number of vertices, with $V(G) = X_1\cup X_2\cup\ldots\cup X_k$, let $n_i := |X_i|$, and suppose $n_1\le n_2\le \ldots\le n_k$. The problem I am ...
1
vote
1answer
1k views

what is maximum number of points of intersection between the diagonals of a convex octgon?

What is the maximum number of points of intersection between the diagonals of a convex octagon (8-vertex planar polygon)? Note that a polygon is said to be convex if the line segment joining any two ...
3
votes
2answers
75 views

How to prove ${{pm} \choose {pn}}\equiv{m \choose n} \pmod{p}$.

Question:(1) if p is a prime and m,n $\in$ N,prove that ${{pm} \choose {pn}}\equiv{m \choose n} \pmod p$ (the book gives me a hint: think about $(1+x)^{pm}$ and $(1+x^m)^p$ in $F_{p}(x)$. (2) Prove ...
0
votes
0answers
80 views

combinatorics (check top cards of deck, if same color set aside and repeat, else stop)

Lets say you have a deck of $z$ cards. $x_1$ are white, $x_2$ are black and $y$ are blanks. $n>0$ is given. Now you do Check top $n$ cards, if they all have the same color, put them aside and ...
3
votes
1answer
31 views

Representation-theoretical reasons for positivity of product of two Schubert polynomials?

In the Wikipedia article on Schubert polynomials there is a claim that there are representation-theoretical reasons for the product of two Schubert polynomials to have nonnegative coefficients when ...