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
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
91 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
321 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
759 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
92 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
22 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 ...
6
votes
0answers
70 views

Has this subset-sum game been studied?

Consider the following game: two players, Yolanda (who always goes first) and Zachary, take turns selecting (not yet chosen) numbers between $1$ and $9$. The first player who can make three of their ...
3
votes
1answer
137 views

If I randomly generate a string of length N from an alphabet {A, B, C}, what's the likelihood that k characters will be the same OR BETTER?

This is an addendum to a previous question found here. I have an alphabet: {A, B, C}. I'm randomly generating strings of length N from that alphabet. Examples: Examples: N=5, AACBC, AAAAA, BBCAA ...
-1
votes
1answer
59 views

how many ziplines between two buildings? [closed]

There are two buildings facing each other, each 5 stories high. How many ways can Kevin string ziplines between the buildings so that: (a) each zipline starts and ends in the middle of a floor. (b) ...
3
votes
3answers
71 views

The number of positive integral solutions to the system of equations.

The number of positive integral solutions to the system of equations $$\begin{align} & a_{1}+a_{2}+a_{3}+a_{4}+a_{5}=47\\ &a_{1}+a_{2}=37,\ \ \{a_{1},a_{2},a_{3},a_{4},a_{5}\} \in ...
1
vote
2answers
302 views

Probability of picking specific balls

Suppose I have $20$ red balls in one box and $20$ blue balls in another box. There $12$ red balls and $7$ blue balls have stars on them. I randomly take out one red ball and one blue ball at each ...
5
votes
5answers
5k views

If I buy 2 lottery tickets do I double my chance of winning?

There's a lottery. There are 6 balls chosen randomly from 49 and you have to match all the balls to win. I buy one ticket. If I buy two tickets with different numbers for the same draw, do I ...
0
votes
1answer
33 views

Amy's grandmother gave her 3 identical chocolate chip cookies and 4 identical sugar cookies.

Amy's grandmother gave her 3 identical chocolate chip cookies and 4 identical sugar cookies. In how many different orders can Amy eat the cookies such that either she eats a chocolate chip cookie ...
6
votes
1answer
119 views

If I randomly generate a string of length N from an alphabet {A, B, C}, what's the likelihood that exactly k characters will be the same?

I have an alphabet: {A, B, C}. I'm randomly generating strings of length N from that alphabet. Examples: Examples: N=5, AACBC, AAAAA, BBCAA What is the likelihood that exactly k characters of that ...
2
votes
1answer
53 views

A problem about chance

I can't really think of a more definitive title. I have a problem about chances or probably combinations (I'm not very good at math). The problem is: If there is an event that occurs 2 times in a ...