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
0answers
12 views

An Interesting Combinatorics Questions

Let l,b be positive integers. Divide the l x b rectangle into lb unit squares in the usual manner. Consider one of the two diagonals of this rectangle. How many of these unit squares contains a ...
1
vote
1answer
27 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
29 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 ...
2
votes
0answers
12 views

Identifying Binary Search Trees from their Prufer Sequence

If you ignore its root, a Binary Search Tree generated by some permutation of $\{1, \ldots, n\}$ is a labeled tree. Which means you can calculate its Prufer Sequence. I did this in Python and I found ...
0
votes
2answers
21 views

5 People roll a dice and flip a coin [on hold]

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 ...
1
vote
1answer
20 views

pairwise balanced design has block size related to the number of elements.

A pairwise balanced design is a set of elements $X$ and set of blocks $A$ such that each pair of elements of $X$ occurs in exactly $\lambda$ blocks. I am trying to solve the following problem: Given ...
1
vote
1answer
13 views

Generating Functions for Multinomials

Find a generating function $(x_1, x_2, ... , x_m)$ whose coefficients of $x_1^{r_1}x_2^{r_2} ... x_m^{r_m}$ is the number of ways $n$ people can pick a total of $r_1$ candies of type $1$, $r_2$ ...
1
vote
0answers
29 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
0answers
10 views

Find nth integer composition

I am processing compositions of integer N in K groups in a loop - for bigger K, N, number of compositions is enormous (1,731,030,945,644 for N = 100, K = 10). I would like to split my loop into more ...
0
votes
0answers
20 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. ...
2
votes
2answers
38 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 ...
2
votes
1answer
28 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 ...
0
votes
1answer
48 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
24 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 ...
0
votes
1answer
31 views

Probability of $k$ collisions

Say we have $m$ buckets. We select a random bucket and put a ball in it, we repeat this $n$ times. In the end what is the probability of having at least one bucket with exactly $k$ balls? I have ...
0
votes
0answers
19 views

Generalized Mobius Inversion formulae

I am having as problem with inverting a relation of the form $f(i)=∑_{j=0}^ig(i,j)h(j)$ I would like to have h in terms of f and g. I know that if my formula was of the form $f(i)=∑_j^ih(j)$ I could ...
1
vote
1answer
21 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 ...
1
vote
3answers
40 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 ...
0
votes
0answers
14 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
0answers
19 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 ...
2
votes
2answers
46 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 ...
7
votes
3answers
633 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 ...
3
votes
0answers
32 views

Points Distributed evenly around a circle: how many points are in each region?

A circle of circumference $2$ is split into three arcs of length $\frac{2}{3}$ (so the regions are $[0,\frac{2}{3})$, $[ \frac{2}{3},\frac{4}{3})$, $[\frac{4}{3},2)$, $2$ identifies with $0$) and ...
0
votes
1answer
50 views

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

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 ...
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
17 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
61 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?
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 ...
5
votes
0answers
85 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?
2
votes
0answers
26 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.
6
votes
2answers
374 views

Prove that any set of 2015 numbers has a subset who's sum is divisible by 2015

I assume this is correct to any size set, not 2015 in particular... it's obviously true for 2. I know from pen and paper it's true for 3, and 4.... I understand that I should look at the reminders, ...
1
vote
1answer
27 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
0answers
24 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 ...
3
votes
3answers
26 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 ...
2
votes
2answers
55 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 ...
0
votes
2answers
55 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 \\ & ...
-2
votes
0answers
38 views

Simplicial homology [on hold]

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
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 ...
2
votes
0answers
33 views

The annihilator numbers of $S/I$ [on hold]

Let $S=K[x_{1},x_{2},...,x_{n}]$ and $I$ be a strongly stable ideal of $S$. Compute the annihilator numbers of $S/I$ with respect to the almost regular sequence $x_{n},x_{n-1},...,x_{1}$. ...
0
votes
1answer
22 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 ...
0
votes
0answers
19 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 ...
1
vote
0answers
25 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 ...
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
38 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
52 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 ...
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
26 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
4answers
64 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 ...
4
votes
2answers
392 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?