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)

27
votes
2answers
813 views

Proof or derivation of this identity $\lim_{n\to \infty}{\frac1{2^n}\sum_{k=0}^n\binom{n}{k}\frac{an+bk}{cn+dk}}\;\stackrel?=\;\frac{2a+b}{2c+d}$?

I just came up with the following identity while solving some combinatorial problem but not sure if it's correct. I've done some numerical computations and they coincide. $$\lim_{n\to \infty}{\frac{1}{...
1
vote
1answer
31 views

Josephus problem: the renumbering method from Concrete Mathematics

In Concrete Mathematics, Chapter 3, Section 3, an interesting method to solve the Josephus problem is discussed. The paragraphs below depict the method, which are extracted from the book: (Initially, ...
-2
votes
1answer
26 views

Combinatorics in a restaurant

In a restaurant menu there are 6 types of drinks : Coca cola , lemonade , sprite , wine , tea and diet sprite . How many people need to order a drink to ensure that at least one drink would be ...
1
vote
1answer
48 views

Help in proof: a connected graph is $k$ edge connected iff all blocks are

Attempt: we know that the edge set of $G$ is the union of those of it's blocks (maximal connected subgraphs of $G$ not having a cut vertex), any two of them touching in at most one vertex. If all ...
7
votes
4answers
332 views

Jessica the Combinatorics Student, part 2

The original question about Jessica, which I encourage review of, is as follows: Jessica is studying combinatorics during a $7$-week period. She will study a positive integer number of hours every ...
1
vote
1answer
44 views

What is the coefficient of the following

I got the question on a midterm and got it wrong. I'd like to know where I went wrong. We were supposed to find the coefficient of $x^{15}$ of$$(1-x^2)^{-10}(1-2x^9)^{-1}$$ My answer The only way to ...
1
vote
0answers
19 views

Upper Bound for discrete objective value

I really need your help with the following problem: Let $ N \ge 3 $ be given, then consider $$ L(N)=\max\left\lbrace \sum_{j=2}^{N-1} \frac{c_j}{j} \, \middle| \, c_j \in \mathbb{N}, \nexists 0\le d \...
13
votes
3answers
512 views

Pigeonhole Principle Question: Jessica the Combinatorics Student

Jessica is studying combinatorics during a $7$-week period. She will study a positive integer number of hours every day during the $7$ weeks (so, for example, she won't study for $0$ or $1.5$ ...
0
votes
1answer
41 views

How many integers in $\{500,…,1000\}$ are not divisible by 3, 7 or 13?

I am wondering what the best way to approach this question is. I thought that I would calculate the number of integers that aren't divisible by 3, 7 or 13 in $\{1,2,...,1000\}$ as well as the number ...
0
votes
0answers
21 views

The maximum number of codewords which have coordinates differing by 1

I'm trying to solve the following problem: Find the maximum possible size of a set $S \subset \mathbb{F}_q^n$ of codewords satisfying the following three conditions: For every $\mathbf{x}, \mathbf{...
1
vote
2answers
44 views

Counting integer solutions for a system of (in)equalities

I wish to enumerate the number of solutions of the system of equations and inequalities for 3 non-negative integer unknowns $x,y,z \ge 0$: ($a$,$b$ specified) \begin{align} x+y+z&=a\\ x+y&>...
0
votes
1answer
26 views

Hardness for problems with non constant input parameters.

It's well known that problems like $3$-sat and $4$-sat and probably $k$-sat for $k\geq 5$ are NP-hard problems but what happens for example if i was to consider something like $\lceil \mathrm{log}(n) \...
1
vote
1answer
48 views

Coloring a triangular bipyramid

A triangular bipyramid looks like this: http://mathworld.wolfram.com/TriangularDipyramid.html I have to find the ways to color it using n colors allowing rotations and reflections. I do not ...
6
votes
2answers
92 views

Bridges across a tiled floor

A few years back, a friend of mine did a seminar on "Bridges across a tiled floor". A "bridge" was defined as a row or column of an $n \times n$ binary matrix consisting entirely of $1$'s, for ...
0
votes
3answers
53 views

In how many ways can 8 similar rings be worn in five fingers of a hand? [closed]

Provided that a finger may not contain more than one ring.However a finger may be empty.
1
vote
3answers
60 views

Let $S$ be the set numbers whose digits are chosen from ${1, 3, 5, 7}$ such that no digits are repeated. Find the sum of every element in $S$.

All numbers in $S$ are natural. I could find the $|S| = 64$ by my own. Can't find the sum of every number in $S$, nor understand the book's explanation for that. The answer is $117856$. Taken from ...
9
votes
3answers
148 views

Summation with combinations

Prove that $n$ divides $$\sum_{d \mid \gcd(n,k)} \mu(d) \binom{n/d}{k/d}$$ for every natural number $n$ and for every $k$ where $1 \leq k \leq n.$ Note: $\mu(n)$ denotes the Möbius function. I have ...
2
votes
2answers
73 views

Supposedly really hard problem involving combinations

This problem gives 7 (max) out of 100 points for a college entrance exams. Seems odd because it looks easy to me, although my combinations are not too good. There are $10$ people forming a ...
1
vote
1answer
35 views

Degree of Jacobian of homogeneous polynomials

What is the degree of the Jacobian (as a polynomial) of 3 homogeneous polynomials in 3 variables of degrees say $m_1, m_2$ and $m_3$ ? I don't know how to prove that it is independent. In my case the ...
2
votes
2answers
55 views

Number of even numbers having digit 2 in them.

I am trying to count numbers from 1 to N which exist in A121022 but I am unable to think of solving in better than O(NLog(N)) , can you suggest a better algorithm?
0
votes
1answer
43 views

Probably an ambiguous word problem

I don't know if this should have been posted on English because it's about interpretation of a sentence, or Math because it involves with a math problem to get the right context and interpretation... ...
1
vote
1answer
33 views

Combinations of sandwiches

My stats summer packet proposes the question: "if a sandwich shop has $3$ different types of meat, $4$ different types of bread, and $3$ different types of cheese. How many types of sandwiches can you ...
0
votes
0answers
34 views

mutual information and combinatorics

\begin{align} &\mathrm{H}\left(\frac{1}{2^{k}}\right) \\[3mm]&\ \!\!\!\!\!\!\!\!\!\! - {1 \over 2^{k}}\left\{% {k \choose 0}\mathrm{H}\left(\left[1 - \epsilon\right]^{\,k}\right) + {k \choose ...
0
votes
1answer
50 views

Is this equation true?

As the question states, does this equation hold true? $\sum_{j=0}^n \sum_{E \in {n \choose j}} (-1)^{|E|}(n-|E|)! = \sum_{j=0}^n(-1)^j(n-j)!{n \choose j} $ From what I understand, this holds true at ...
1
vote
1answer
79 views

Numbers with constant digit-sum in increasing order

For base $b = 10$, I want to list all numbers with $d$ digits (no leading zeros) and digit sum $x$, in increasing order. For example for $d = 6$ and $x = 40$ we would get: 139999, 148999, 149899, ...
4
votes
2answers
37 views

Probability of 4 specific numbers (1-3000) occuring in a sample of 400

How to calculate the probability that four specific, distinct numbers from the range 1 - 3000 occur at least once in a fixed sample of 400 random numbers from the range 1-3000? The numbers in the ...
0
votes
0answers
16 views

Existence of Kazhdan Lusztig basis proof due to Soergel

This question is regarding the proof of the existence and uniqueness of Kazhdan Lusztig basis theorem for an arbitrary coxeter group $W$ due to Kazhdan and Lusztig in his paper "Representations of ...
-3
votes
1answer
26 views

Number of licence plates that match a criterion [closed]

A new license plate in Alberta consists of three letters followed by four numbers. Letters are chosen from a list of $24$ acceptable letters that may be repeated. And any digits can be used and they ...
0
votes
1answer
19 views

When arranging numbers and letters in combinatorics, should one use multiplication or addition?

Let's say that we are given that a code is formed with 3 letters of alphabet followed by 3 digits from 0-9, and both can be repeated. When required to find the total number of combinations. Is it ...
0
votes
1answer
33 views

stirling numbers of second kind

i am new to combinatorics and just encountered stirling numbers of second kind the book i am using does not provide much info about it except number of ways of distributing "r" distinct objects ...
6
votes
0answers
75 views

Inequality for hook numbers in Young diagrams

Consider a Young diagram $\lambda = (\lambda_1,\ldots,\lambda_\ell)$. For a square $(i,j) \in \lambda$ define hook numbers $h_{ij} = \lambda_i + \lambda_j' -i - j +1$ and complementary hook numbers $...
2
votes
1answer
29 views

There must be a monochromatic odd cycle in $t$-coloring of $K_{2^t+1}$

Prove: if we $t$-color the edges of the complete graph on $2^t+1$ vertices, then there must be a monochromatic odd cycle. This is supposed to be an easy exercise but I haven't made much progress. ...
1
vote
0answers
26 views

Constructing a Collection of Sets Satisfying Certain Intersecting Properties

I am trying to solve the following problem. We would like to construct $\{A_1, \ldots, A_n\}$, where $n$ is even, and each $A_i \subseteq [m]$, with $|A_i| = k$ and $m = \text{poly}(n)$. Now, I would ...
1
vote
0answers
30 views

Combinatorial property of sets

Is the following true? For every $\varepsilon>0$ there is a finite subset $W$ of $\mathbb{N}\times \mathbb{N}\times \mathbb{N}$, such that $$|p_1(W)\cap p_2(W)\cap \{p_1(x)+p_2(x):x\in W\}\cap \{...
1
vote
0answers
61 views

Solving a non-standard linear recurrence [closed]

Can you find an expression for the sequence $(a_n)$ satisfying the following recurrence $$a_n = a_{n-1} + a_{n-2} + \sum_{i=3}^{n} 2\binom{n}{i}a_{n-i}$$ for $n \geq 3$ where $a_0 = 0, a_1 = 1, a_2 ...
4
votes
1answer
57 views

n-th roots of unity summing to $0$

Let $\zeta = e^{2\pi i/n}$ be an $n$-th root of unity, and let $S = \{\zeta^m|m=0,1,\ldots,n-1\}$ be the corresponding sets of all $n$-th roots of unity. Let $k \leq z$. Let $C \subseteq S$ such ...
0
votes
0answers
15 views

Solve $\max_X \mathrm{sum}(AXB \geq \gamma)$, with $X$ being a permutation matrix

I have a problem to find the best permutation matrix $X \in \{0,1\}^{n \times n}$, which would maximizes the number of elements in $AXB$ which are above a certain positive number $\gamma$. In other ...
1
vote
0answers
21 views

Find optimum diagonal matrix $D$ to maximize $ADB$ above a threshold $\gamma$

I have a problem to find the optimum diagonal matrix $D$, which would maximizes the number of elements in $ADB$ which are above a certain positive number $\gamma$. In other words, the problem is ...
-2
votes
0answers
24 views

Number of possible combinations

There is a set of 9 cubes, each one can rotate about x an y axes, ie. up and down and left and right. Each cube can be connected (geared) to any other in the set so if one is turned, in any direction, ...
0
votes
2answers
43 views

There is group a $S$ with $2n$ members $n$ of them are identical and $n$ of them are different, How many subsets are there?

I have the following question : There is a set $S$ with $2n$ members $n$ of them are identical and $n$ of them are different, How many different subsets are there for $S$ in size $n$. This is what I ...
0
votes
1answer
41 views

Elementary proof of MacMahon's generating function for plane partitions

Recall Macmahon's elegant and beautiful generating function for plane partitions $$ \sum_{n=0}^{\infty} pp(n) q^n = \frac{1}{(1 - q)^1(1 - q^2)^2(1-q^3)^3\cdots}= \prod_{j=1}^{\infty}\frac{1}{(1-q^j)^...
2
votes
1answer
41 views

A combinatorics challenge. Counting members and totals of a random group

This combinatorics challenge. Counting members of a group in a real world situation.. with a very strange data pool. I need to count a mass of people divided into random groups, from each group ...
0
votes
1answer
24 views

Using Routes To Map Increasing Mappings

Problem So how do I establish a bijection between these two sets? Also, $N_n$ = (1,2,3,4,...,n). Thank you.
7
votes
2answers
189 views

Coloring the pentagonal hexecontahedron

So, I'd like to color the pentagonal hexecontahedron in a way that is satisfying aesthetically and mathematically. For me this equates to, in order of priority - 1. No same-colored faces can share an ...
1
vote
1answer
56 views

What is the probability of a random 8 bit string to have no more than 2 consecutive 1's. [closed]

I don't know how to approach this problem. I think the correct approach is getting a recurrence relation. But I don't know how. Help is much appreciated. This is not a homework problem. I saw ...
0
votes
2answers
39 views

Checking if something is a Bijection

Reflection Principle's Proof I was able to follow the proof until the end, and then the proof said to check that it was a bijection. How would one check if something was a bijection?
0
votes
0answers
22 views

How many combinations to break a monoalphabetic substitution

Let a language $\Sigma$ have 16 letters, we have a message in that language that was encrypted using monoalphabetic substitution (a permutation of the alphabet) and we want to break it. We also ...
-1
votes
0answers
17 views

Increasing Mapping [duplicate]

Problem What does it mean when by a strictly increasing mapping? For example, if you had $8$ = (1,2,3,4,5,6,7,8) and $3$ = (1,2,3) what would the increased mapping be?
1
vote
0answers
51 views

Solving $x_1 + \dots + x_n = m$ with general (i.e. not specific to a variable) restrictions

The number of non-negative integer solutions to $$x_1 + \dots + x_n = m$$ is extremely well known to be ${m + n - 1 \choose m}$. It is also not difficult to solve if we require, say, $x_1 \geq 5$: ...
4
votes
4answers
60 views

8 people in 4 teams with different pairs in each team each day for 7 days without repeated pairs or anyone being in the same within 3 days

Ok I am a Scout Leader and on our 7 day summer camp we have 8 Leaders and will have the Scouts in 4 different patrols or teams. I want to set up a rota for the Leaders so that they can be assigned to ...