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)

1
vote
0answers
16 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
0answers
10 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 ...
5
votes
2answers
200 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
18 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
10 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
22 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
52 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
46 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 \\ & ...
-1
votes
0answers
18 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
41 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
5 views

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

Let $S=K[x_{1},x_{2},...x_{n}]$and $I$ be the strongly stable ideal of $S$.Compute the annihilator number of $S/I$ with respect to the almost regularsequence $x_{n},x_{n-1},...x_{1}$.
0
votes
1answer
20 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
13 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
23 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
19 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
34 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?
1
vote
3answers
44 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
49 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
24 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
60 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
381 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?
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?
0
votes
1answer
31 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$
1
vote
1answer
26 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 ...
0
votes
1answer
29 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 ...
2
votes
2answers
49 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 ...
0
votes
1answer
27 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: ...
0
votes
0answers
12 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 ...
1
vote
2answers
35 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 ...
5
votes
0answers
43 views

A set of integers whose elements all divide $2015^{200}$ but do not divide each other

Let $S$ be a set of natural numbers,such that each element divides $2015^{200}$ but for no two elements $a$ and $b$, $a|b$. Find the maximum number of elements in $S$ . $2015^{200}=(5\cdot ...
1
vote
2answers
24 views

Number of 5 letter words with at least one double letter

How many 5 letter words have at least one double letter, i.e. two consecutive letters that are the same? Answer is: $26^5 – 26*25^4 = 1,725,126 $ But how can i solve? I don't understand. The book ...
1
vote
1answer
30 views

Is there an upper bound on Bell numbers?

For some reason my intuition is that $n^n$ might be an upper bound for Bell numbers, but I can't find anything to confirm that. Sorry if this is a simple question! (it's been a while since my ...
0
votes
0answers
27 views

How to display one to one correspondence for all bit strings not containing the bit O?

This is a problem from Discrete Mathematics and its Applications From the onset I saw that this set was countable was that you could physically count these out - 1, 11, 111, 1111 and perhaps ...
0
votes
0answers
30 views

Solving a proof by combinatoric method

Any good questions you guys have in mind?: prove the following equation by coming up with a combinatoric problem and solving it step by step (Solve combinatoric method): $$ {n \choose 1} + 14{n ...
2
votes
1answer
47 views

tricky question in combinatorics - deck of cards [on hold]

A deck of cards with $4$ sets, each set contains $13$ cards. We want to create a new sequence of $n$ cards: each time we choose a card, write it down as the next element in the sequence, put it back ...
0
votes
1answer
26 views

Finding the combination between 2 sets

8 balls are pulled at random from a bag of 32. Each ball is numbered 1-32. Balls that are 1-16 go into set $S_1$. $x_i \in \{1,2,3...16\}$ $S_1 = \{x_1, x_2, x_3, x_4\}$ Balls that are ...
0
votes
2answers
41 views
6
votes
2answers
424 views

Is there a planar graph that (almost) all its vertices has degree 6?

Is it true that for any $N_0\in\mathbb N$ there exists a planar graph $G=(V,E)$ on (at least) $N_0$ vertices such that at least $$|V|(1-o(1))$$ vertices has degree 6? It is easy to show that no ...
1
vote
0answers
23 views

Enumeration of points with infinite dimensions

A well known way to enumerate points with finite support in an infinite dimensions space $N \times N \times ...$ and avoid duplicates is to use the exponents of the factorization of $n$ as the ...
2
votes
2answers
50 views

How many arrangements do we have?

We have $N$ boxes and an inexhaustible supply of objects belonging to $k$ distinct classes such that $N\gt k$. How many different arrangements of the objects in the boxes are there if (a) each of ...
1
vote
1answer
35 views

Is there a set of integers where all differences are relatively prime?

Is there an infinite subset $\mathcal S\subset \mathbb Z$ with the property that for any 4-tuple of distinct elements $x,y,z,w\in \mathcal S$ $$ \gcd(x-y,z-w)=1? $$
-3
votes
2answers
32 views

a Combinatorics problem in series [on hold]

Hey everyone i was having a problem with the following question: in how many ways is it possible to solve the following equation using natural numbers: $$ x_1+x_2+x_3...+x_{15}=300 $$ that for every ...
2
votes
1answer
21 views

Algorithm to partition a set into subsets of max weight

I have a big set $S$ of elements $e_i$, each $e_i$ characterized by an integer weight $w_i$. I would like an algorithm to split set $S$ into subsets $S_j$ such that: The sum of weights in each ...
0
votes
1answer
19 views

largest independent set in a circuit of length $n$

largest independent set in a circuit of length $7$ and $n$? For $7$, I guessed it's $3$. Guidance on finding for $n$?
2
votes
4answers
72 views

Curious Binomial Coefficient Identity

Consider the following set of identities: ${m+1\choose 1}={m\choose 1}+1$, ${m+1\choose 2}=2\binom m 2 - {m-1\choose 2}+1$, ${m+1\choose 3}=3\binom m3-3{m-1\choose 3}+{m-2\choose 3}+1$, ... This set ...
3
votes
1answer
29 views

Combinatorial Identities

I am trying to prove the following identities: a. $$\sum_{k=0}^n(-1)^k{n\choose k}^2 = \bigg\{^{0 \ \text{if k is odd}}_{(-1)^m{2m\choose m} \ \text{if n = 2m}}$$ b. $$\sum^k_{i=0} {n+i ...
3
votes
2answers
346 views

Combinatoric Solution To The Birthday Paradox

I attempted the following solution to the birthday "paradox" problem. It is not correct, but I'd like to know where I went wrong. Where $P(N)$ is the probability of any two people in a group of $N$ ...
1
vote
0answers
32 views

Generating function from a set of binary strings

So this question is in my textbook and there's no solution, so I'm seeing if I can get a confirmation? Q: Let $S$ be the set of all binary strings of length 4, where for each string $a\in S$, the ...
1
vote
2answers
38 views

Double Factorial

I am having trouble proving/understanding this question. Let $n=2k$ be even, and $X$ a set of $n$ elements. Define a factor to be a partition of $X$ into $k$ sets of size $2$. Show that the ...
1
vote
3answers
40 views

Generating series of integers with a specified sum

If I say that 6 positive integers were added together to get a total of 200. let count = 6 let sum = 200 I have 2 questions First of all, is there a formula for generating a list of all the possible ...