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)

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
254 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
184 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. [on hold]

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
25 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
18 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
32 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 ...
5
votes
0answers
93 views

Number of permutations such that adjacent elements don't differ by more than $K$

Given $N$ and $K$, I need to count number of permutations of $1, 2, 3,\ldots, N$ in which no adjacent elements differ by more than $K$. How do I approach this problem?
1
vote
0answers
31 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
339 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
877 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 ...
2
votes
0answers
27 views

Graphs with bounded degree: how many are there?

Can one count the number of undirected (simple) graphs on $n$ nodes with degree at most $d$? Asymptotic bounds would be helpful too.
0
votes
2answers
56 views

The number of nonnegative integer solutions of $x_1+\cdots+x_6=24$ with $x_1+x_2+x_3>x_4+x_5+x_6$

I try to find the number of nonnegative integer solutions of $\begin{align} & {{x}_{1}}+{{x}_{2}}+{{x}_{3}}+{{x}_{4}}+{{x}_{5}}+{{x}_{6}}=24 \\ & ...
0
votes
0answers
22 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 ...
1
vote
1answer
29 views

Counting with restrictions.

I need help with counting with restrictions, such as in the problem In how many ways can we distribute 13 pieces of identical candy to 5 kids, if the two youngest kids are twins and insist on ...
1
vote
1answer
84 views

Maximise the smallest piece of grid

Given a big rectangular chocolate bar that consists of n × m unit squares. We wants to cut this bar exactly k times. Each cut must meet the following requirements: ...
2
votes
2answers
56 views

A game where starting with 3 boxes, with 10 balls in each, the goal is to remove as many balls as possible following the rules

This is a Norwegian olympiad problem: Peter has three boxes, with ten balls in each. He plays a game where the goal is to end up with as few balls as possible in the boxes. The boxes are each ...
3
votes
3answers
27 views

The probability of selecting both defective items when taking 10 out of 24

The following is a problem from my probability text. A box contains 24 light bulbs, of which two are defective. If a person selects 10 bulbs at random, without replacement, what is the probability ...
0
votes
0answers
20 views

Combinations of inheriting genes with certain variables

Context. The idea is taken from a breeding mechanic of a game similar to inheriting genes. The variables are highlighted in bold and italicized. There are 6 stats from each parent represented by 6 ...
5
votes
4answers
297 views

Probability that 2 appears at an earlier position than any other even number in a permutation of 1-20

Suppose we uniformly and randomly select a permutation from the 20! Permutations of 1,2,3,...,20. What is the probability that 2 appears at an earlier position than any other even number in the ...
0
votes
1answer
26 views

Combinatorial Challenge, alternative solution process.

Problem: "During an election campaign $n$ different kinds of promises are made by the various political parties, $n>0$. No two parties have exactly the same set of promises. While several ...
-6
votes
1answer
327 views

What is the number of positive integers? [closed]

b. In a system of ternary (Base 3) number, with n digits, how many number can be represented? Answer: c. For an n-digit signed 3's complement ternary number (n > 1), what is the number of positive ...
0
votes
0answers
43 views

What is umbral calculus, really? [duplicate]

I've seen this page on umbral calculus as well as wikipedia and and another question asked on this website (What's umbral calculus about?), but I still cannot realize what really umbral calculus ...
1
vote
0answers
27 views

A limit of the hyperfactorial and Barnes G-function

I'm doing some work on the various means (arithmetic, geometric, etc.) of some sequences of binomial coefficients, and I'm having some trouble proving a result regarding a ratio of the Hyperfactorial ...
12
votes
2answers
559 views

If each boy knows r girls and each girl knows r boys ,then number of boys=girls

Yet another question from BdMO 2013 Nationals: In a class,every boy knows $r$ number of girls and every girl knows $r$ number of boys.Show that there are equal number of boys and girls[Assume that ...
2
votes
1answer
22 views

Given a graph on $n$ vertices find the maximum amount of edges so it can be colored with no monochromatic $K_m$

I invented a problem and I wanted to share :What is the maximum amount of edges a graph on $n$ vertices can have if it can be edge-colored with $k$ colors so that it does not have a monochromatic ...
0
votes
1answer
41 views

In how many ways can the word “WORD” be rearranged so that no letter is in its original position?

In how many ways can the word "WORD" be rearranged so that no letter is in its original position? The answer is $9$, but what is the formula for it?
2
votes
3answers
54 views

Proof by induction, binomial coefficient

I have to make the following proof: $${\sum\limits_{k=1}^n}{k}{n\choose k} = n2^{n-1}$$ Base case, $n = 1$: $${\sum\limits_{k=1}^{1}}{k}{1\choose k} = 1 = 1\cdot2^0=1$$ Inductive Hypothesis: for ...
4
votes
4answers
68 views

Finding all possible combination **patterns** - as opposed to all possible combinations

I start off with trying to find the number of possible combinations for a 5x5 grid (25 spaces), where each space could be a color from 1-4 (so 1, 2, 3, or 4) I do ...
1
vote
2answers
51 views

Lottery based counting problem based on uniqueness and monotonicity

I was solving this problem and have prepared a solution here. Problem summary: Consider choosing Blank number of integers from 1 to ...
0
votes
1answer
27 views

How restrictions reduce the number of possible arrangements

A company has five departments. The company is establishing a board consisting of five members that represent a distinct department each. Suppose that every employee is a candidate to represent his ...
4
votes
2answers
393 views

Where can the knight be?

The answer is 33. I get $24$. Because of $8 \cdot 3 = 24$? How can I do this using combinatorics?
2
votes
2answers
56 views

Counting bit strings of length 10 contain either 5 consecutive 0's or 5 consecutive 1's

How many bit strings of length 10 contain either five consecutive 0's or five consecutive 1's ? My Solution: for 5 consecutive 0's After we have filled 0's from $1^{st}$ position we have 2 ...
1
vote
1answer
28 views

Maximal Multiplication of All Possible Summands

I have recently got interested in the following problem: Give a decomposition of a natural number to natural summands whose multiplication is maximal. I have tried to solve this problem, and ...
2
votes
3answers
1k views

Probability of having exactly 1 pair from drawing 5 cards

I have an exercise as follows: There is a collection of cards consisting of 52 cards (13 types and 4 colours each type). We draw 5 cards from the collection. Then what is the probability of having ...
1
vote
2answers
43 views

Combinatorics using a geometric diagram

How can I do this without trial-and-error? It has something to do with a triangle and summing the next row?
2
votes
2answers
49 views

How many ways are there of coloring $n$ numbers (using $k$ colors) s.t. each color is used at most $d$ times?

Let's assume we have $n$ numbered items and $k$ colors. We color each of the items with a single color. How many such colorings exist such that each of the colors is used at most $d$ times?
4
votes
2answers
762 views

Outcome of rolling a fair die 6 times

I'm failing to understand how to come to the answer to this question. If you roll a fair die six times, what is the probability that the numbers recorded are $1$, $2$, $3$, $4$, $5$, and $6$ in any ...
0
votes
1answer
34 views

How many possible paths?

The answer is $32$. Its supposed to be $2^5$ but I do not see how you get that? The way I see it, there are $5$ ways to go up and $5$ ways to go right, total ways = $5x5= 25$
0
votes
1answer
32 views

An interesting mathematics task.

Find the number of different ways of arrangement of all natural numbers from 1 to 9 inclusive, one in table cells measuring 3 by 3 such that the sum of the numbers in each row and each column are ...
0
votes
1answer
29 views

Probability of getting an average of 3 or more by rolling 4 sided die twice

What I understood is the sample mean of two rolls of all sample space(16) as given below: ...
1
vote
2answers
36 views

Pairs of integeres for which the arithmetic mean exceeds the geometric mean exactly by $2$

Suppose $0<x<y<2015$ are integers. How many pairs of $x$ and $y$ are there for which the arithmetic mean exceeds the geometric mean exactly by $2$? Progress Obtained the equation ...
1
vote
2answers
92 views

Number of lists at some Kendall-Tau distance

Given a ranked list (permutation) $R$ of $n$ elements, how many permutations of the same elements are there at Kendall-Tau distance $d$ from $R$ $(0 \le d \le \frac{n(n-1)}{2})$? Example: If $R = ...
0
votes
0answers
14 views

Ways of partitioning n points into some cubes

Assume there're $n$ fixed points in $\mathbb{R}^d$ contained in a ball with radius $M$,and you can partition the space by cubic grid with cube's edge length $h>\epsilon$. How many different ways of ...