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)

2
votes
3answers
72 views

n distinguishable balls into n boxes

We have n distinguishable balls (say they have different labels or colours). If these balls are dropped at random in n boxes, what is the probability that: 1- No box is empty? 2- Exactly one box is ...
4
votes
0answers
44 views

Placing $4n$ non-attaking queens of in a $4n \times 4n$ chessboard.

Is it possible to place $4n$ non-attaking queens of in a $4n \times 4n$ chessboard?? I have found that it can be done for $4 \times 4$ chess board and trying to extend it to $8 \times 8$ chessboard ...
0
votes
0answers
39 views

Combinatorial approach to calculate determinant

Suppose you have set of $n*n$ matrices with entries from the set $\{1,-1\}$. Then what can be the maximum determinant which you can obtain from such type of matrices.
2
votes
2answers
450 views

To find the total no. of six digit numbers that can be formed having property that every succeeding digit is greater than preceding digit. [on hold]

I have a question and got strucked on this.. To find the total no. of six digit numbers that can be formed having property that every succeeding digit is greater than preceding digit. Please guide me ...
1
vote
1answer
109 views

Integral solutions to $x_1 \cdot x_2 \cdot x_3 \cdot x_4 = 210$

Find how many integral solutions and there to the given condition for $x_1 , x_2 , x_3$ and $x_4$ $$x_1 \cdot x_2 \cdot x_3 \cdot x_4 = 210$$ I factored it to $2 \cdot 7 \cdot 5 \cdot 3$, Then how ...
2
votes
1answer
29 views

How to prove this result using Permutations? [closed]

Let A be the set of all $3*3$ skew symmetric matrices whose entries are either -1, 0 or 1. If there are exactly 3 zeroes, three 1's and three (-1)'s, then prove that only 8 such matrices can exist.
1
vote
1answer
86 views

let s be a set with N elements and A1,…,A101 be 101 (possibly not disjoint) subsets of S

So the question I'm having problem with is the following: let s be a set with N elements and A1,...,A101 be 101 (possibly not disjoint) subsets of S with the following 5 properties: each elements ...
0
votes
2answers
36 views

What is the minimum number of painted edges in the chessboard?

Some edges of the squares of an 8×8 chessboard are painted red. What is the minimum number of edges that must be painted, so that each square has at least two red edges? What is the meaning of this ...
0
votes
1answer
44 views

Count n-length words containing pattern

I have a class $A$ of words from alphabet of letters {a,b,c}, containing "abbc" and class $B$ which has the same words but with ...
14
votes
0answers
334 views

Generating function solution to previous question $a_{n}=a_{\lfloor n/2\rfloor}+a_{\lfloor n/3 \rfloor}+a_{\lfloor n/6\rfloor}$

In attempting to answer this question, I reduced it to a seemingly simple generating functions question, but after days of work was unable to construct a proof. Since I do not have experience trying ...
0
votes
2answers
26 views

5 People roll a dice and flip a coin [closed]

Each of 5 people flip a coin and roll a dice (six sides). I know the total number of possibilities equates to $6 \times 2$ because the dice has 6 options, and the coin has 2 options. As a result we ...
3
votes
0answers
58 views

Combinatorics project ideas for high school students

It's that time again! Last year I asked for high school project ideas in the area of algebraic geometry, this year it's combinatorics (you can include graph theory and combinatorial game theory if you ...
0
votes
2answers
151 views

Assigning tables for Speed Networking session

I'm planning a structured Speed Networking activity for an event. Here are the details: 100 attendees participating Split into groups of 4 12 rotations 25 tables One person at each table never ...
0
votes
0answers
23 views

$10$ people out of a population of $n$ people take a slice of $10$ different cakes. They are not allowed to share. In how many ways can this occur?

For those confused by the title: There are 10 different cake slices available, 10 people chosen from a population of size n are allowed to pick one slice that has not already been chosen and eat it. ...
5
votes
2answers
6k views

Number of bit strings with 3 consecutive zeros or 4 consecutive 1s

I am trying to count the number of bit-strings of length 8 with 3 consecutive zeros or 4 consecutive ones. I was able to calculate it, but I am overcounting. The correct answer is $147$, I got $148$. ...
2
votes
1answer
31 views

Remove minimal number of elements

Given the numbers $ 1,2,..,2n + 1 $ , $ n > 0$ , remove as few numbers as possible so that among the remaining numbers no number is equal to the sum of two other numbers. After removal of first ...
1
vote
0answers
20 views

Question regarding a proof of the Combinatorial Nullstellensatz

N. Vishnoi has provided a slick proof of the combinatorial nullsetellensatz at http://research.microsoft.com/en-us/um/people/nvishno/site/publications_files/valon.pdf . The part that I am not ...
0
votes
1answer
49 views

How many 10 digit numbers are there so the sum of the digits is $2$?

How many 10 digit numbers are there so the sum of the digits is $2$? $abcdefghij$ is the 10 digit number. By default, $a=1$ is a must. $= 1bcdefghij$ Now we need: $bcdefghij = 1$ How can I solve ...
0
votes
2answers
28 views

Histogram of duplication in n choose k

Imagine having 17 balls to distribute to 4 people. One algorithm for distributing these balls is to give each ball to one out of the four randomly. This means, in an extreme case, it is possible for 1 ...
-2
votes
0answers
43 views

Simplicial homology [closed]

Let $\Delta$ be the simplicial complex on vertex set [5] whose Stanley-Reisner ideal is $I_{\Delta}=(x_{1}x_{4},x_{1}x_{5},x_{2}x_{5},x_{1}x_{2}x_{3},x_{3}x_{4}x_{5})$. Write the augmented oriented ...
0
votes
1answer
78 views

Generating Functions of Partitions?

Show that $2(1-x)^{-3} [(1-x)^{-3} + (1+x)^{-3}]$ is the generating function for the number of ways to toss $r$ identical dice and obtain an even sum. Workings: I'm not too sure on this problem. ...
0
votes
0answers
64 views

Average Degree of a Random Geometric Graph

A set of $N$ points are distributed randomly on a unit square with uniform distribution. Two points $\mathbf{p}_i$ and $\mathbf{p}_j$ are said to be connected if $\|\mathbf{p}_i - \mathbf{p}_j\| \leq ...
0
votes
1answer
69 views

An effcient method of solving a Diophantine equation with 3 variables $Ax+By+Cz=D$?

I'm trying to make an efficient algorithm to find one of the solutions and how many solutions there are to the equation $$Ax+By+Cz=D$$ where $A,B,C,D\in \mathbb Z$ and the range for $x,y,z\in \mathbb ...
6
votes
3answers
587 views

$\tbinom{2p}{p}-2$ is divisible by $p^3$

The problem is as follows: Let $p>3$ be a prime. Show that $\tbinom{2p}{p}-2$ is divisible by $p^3$. The only thing I can think of is that $(2p)!-2(p!)^2$ is divisible by $p^2$ which doesn't help ...
0
votes
0answers
18 views

How many cases can draw diagonals that Applicable 2 above condition?

Imagine A $n$_regular polygon that vertex is named by $1$ to $n$. We know can draw $\frac{(n)(n+3)}{2}$ diagonals in $n$_regular polygon and also know if we want draw Maximum diagonals are not ...
2
votes
2answers
59 views

Determine the number of integer solutions of $x_{1}+x_{2}+x_{3}+x_{4}=32$ where $x_{1},x_{2},x_{3}>0, \space\space 0<x_{4}\leq25$.

Determine the number of integer solutions of $$x_{1}+x_{2}+x_{3}+x_{4}=32,$$ where $x_{1},x_{2},x_{3}>0, \space\space 0<x_{4}\leq25$. My approach is in finding all the solutions with the ...
1
vote
3answers
42 views

How many ways there are?

I cant solve the following problem. In how many ways we can divide 6 balls between 3 children if every children must receive at least 1 ball. I don't understand the problem. Is it permutations or ...
1
vote
1answer
22 views

Split n balls to k boxes

I have $n$ different balls $(1,2,..., n)$ and $k$ different boxes $(1,2,...,k)$. I want to put all balls to boxes, but if ball i has smaller nuber than j (i < j) than ith ball must be put to box ...
0
votes
1answer
52 views

Generating function $D(x) = (1 + x)(1+x^2)(1+x^3)\cdots$ [closed]

Let $$D(x) = (1 + x)(1+x^2)(1+x^3)\cdots $$ 1) What is the inverse function of $D(x)$? 2) What sequence is generated by $D(x) $ Please don't vote down, the subject is complicated for me. Sorry ...
2
votes
2answers
101 views

How many even number in a sequence are there?

How many even numbers in the below numbers ? $$\binom{k}{0},\binom{k}{1},\binom{k}{2},\ldots,\binom{k}{k}$$ Worng: Is it true that all of them are odd iff $k$ is odd, and if $k$ is even then ...
0
votes
1answer
173 views

Divide 500 into certain group so that all no's 1 to 500 can be found.

500 coins are there. Divide 500 coins into certain bags such that any rupees from 1 to 500 can be found by the combination of the bag's coins. What are the minimum nos of bags ?
7
votes
3answers
656 views

Is every arrangement reachable by shuffling this way?

Suppose we have a vertical stack of $n$ distinguishable coins, each of which is either heads-up or tails-up. Let a shuffle be the following procedure: divide the stack at will into a top- and ...
0
votes
1answer
48 views

Minimum AND operation on subset

Given an array of size N . Let's create all the subsets of this array which contain at least 2 elements. Now, operate AND over the elements of each subset, and store the results in a new array. I ...
1
vote
1answer
96 views

Count pairs with odd XOR

Given an array A1,A2...AN. We have to tell how many pairs (i, j) exist such that 1 ≤ i < j ≤ N and Ai XOR Aj is odd. Example : If N=3 and array is [1 2 3] then here answer is 2 as 1 XOR 2 is 3 ...
0
votes
1answer
223 views

Find sum of all permutations

We call two arrays A and B with length n almost equal if for every i (1 <= i <= n) ...
2
votes
0answers
259 views
0
votes
1answer
110 views

Divide N Hot dogs among M persons

There are N hot dogs and M people and we need to divide the hot dogs equally. Now we need to calculate the minimum number of cuts required to distribute the hot dogs equally. In order to divide the ...
1
vote
1answer
79 views

Count ways to reach Nth row

Given a N*M grid I need to reach last row with following operations : ...
-1
votes
1answer
186 views

Count ways to form isosceles triangles

Their are N persons sitting on a table with N vertices.We need to count the number of isosceles triangles formed such that each vertex of the triangle is a vertex of the table and all persons seating ...
2
votes
1answer
62 views

Multiples of 3 and 5. [closed]

If we have the Tartaglia(Pascal) triangle in every row which numers are multiples of 3 which are even and which are multiples of 5?
0
votes
1answer
27 views

Partitioning elements into sets

How many ways are there to partition $n$ unique elements into $2$ sets? What about for $k$ sets? I am specifically interested in how to calculate this for varying values of $n$. Moreover, what if ...
1
vote
0answers
19 views

Given a specific rational number, is there a way to find an n and k for the binomial coefficient that will evaluate to it? [duplicate]

Looking at Pascal's triangle, it looks as though all rational numbers can also be expressed as binomial coefficients. Given a rational integer, is it possible to calculate n & k for the binomial ...
1
vote
2answers
33 views

Factorial formula problem [duplicate]

Prove that $(n-r)!(r!)$ divides $ n! $ i know its a factorial formula and it might be easy but i stuck .I tried induction to $n$ or analyzing the factorials but im missing something
2
votes
1answer
291 views

Probability question involving sets of cards

I have an infinite deck built out of sets of 10 cards (in other words 10*n cards). The sets are identical so one '2' is identical to another '2'. A player draws 6 cards. If he draws: any '1' AND a ...
1
vote
1answer
25 views

Number of permutations of $[n]$ with a multiple of $n$ inversions

We have a permutation $\left(a_1,a_2,...,a_n\right)$ of the set $\{1,2,...,n\}$. A pair $(a_i,a_j)$ is said to be an inversion of this permutation if $i<j$ and $a_i>a_j$. Find the number of ...
0
votes
1answer
300 views

I need a formula for how many ways I can choose k balls (two balls each time from the same box) from n boxes?

We have n (can take any value 1,2,3,...) boxes each has the same number of distinct marbles, say b marbles, so the total number of marbles S=n*b. we can choose marbles from boxes with the following ...
1
vote
0answers
36 views

Expected size of largest connected component in a random k-out digraph?

Given a digraph with n vertices and kn edges, where each vertex has k out-neighbors randomly chosen at uniform without loops, how would I go about figuring out the expected value of the size of the ...
4
votes
1answer
340 views

What is the number of ways to divide a rectangle into $n$ smaller rectangles line by line?

The original problem was to consider how many ways to make a wiring diagram out of $n$ resistors. When I thought about this I realized that if you can only connect in series and shunt. - Then this is ...
4
votes
2answers
92 views

does $a^2-51b^2=\mp 6$ have a solution for integers?

does $a^2-51b^2=\mp 6$ have a solution for integers? I have tried for many modulos, but could not get much out of them.
3
votes
2answers
883 views

How many perfect squares divide 1!2!3!4!5!6!7!8!9!

What I naturally did was to find the prime factorisation of the product of factorials which is $ 2^{30}3^{13}5^5 7^3 $. Clearly there is 15 unique perfect squares that divide $2^{30}$, 6 unique ...