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)

9
votes
3answers
147 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
32 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
74 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
17 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
40 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
50 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
58 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 ...
4
votes
0answers
104 views

Number of ways to arrange $n$ numbers based on their relative values to each other

EDIT I've found a formula to solve this question, but I don't understand the reasoning behind it. Can someone explain this formula? $s(n - 1, x + y - 2) \times C(x + y - 2, x - 1)$ $s$ being ...
1
vote
1answer
24 views

How many line segments have both their end points located at vertices of a given cube?

How many line segments have both their end points located at vertices of a given cube? My try:- A cube has 8 vertices. Number of line segments = 8C2=28. (As a line segments has 2 end points)
0
votes
0answers
18 views

Find permutation matrix $X \in \{0,1\}^{N \times N}$ in order to make $XAX \geq_c B$

I need to solve a problem to find out the best permutation matrix $X \in \{0,1\}^{N \times N}$ which would maximize the number of elements in matrix $XAX$ which are above (component-wise) matrix $B$ ...
1
vote
1answer
63 views

A Closed Form Lower Bound Approximating $p_{n,m,s} = n![z^n]\left(\sum_{k=0}^s\frac{z^k}{k!}\right)^m$

Here, I found $p_{n,m,s} = n![z^n]\left(\sum_{k=0}^s\frac{z^k}{k!}\right)^m = \sum\limits_{\substack{k_1 + \cdots + k_m=n\\0\leq k_i \leq s}} \frac{n!}{k_1!\cdots k_m!}$ as the number of ways to ...
1
vote
0answers
22 views

Compute the number of ordered partitions [closed]

Let $a-b=2n$. Compute the number of ordered partitions of an integer $a$ if they include $b$ odd numbers.
0
votes
1answer
42 views

Prove there's a monochromatic isosceles triangle.

The points in a circle are coloured red and blue. Prove that there exists a monochromatic isoceles triangle. I can prove that there exists a monochromatic triangle. If there are no three points of ...
1
vote
0answers
54 views

Coefficient of $x^n$ in $x \prod\nolimits_{i = 1}^{d} (x - i) (x + i)$

I am looking for a general form of the coefficient of $x^n$ in $x \prod\nolimits_{i = 1}^{d} (x - i) (x + i)$. I know that the leading coefficient (in front of $x^{2 d + 1}$) is $1$, and there are no ...
1
vote
1answer
46 views

How to derive the close form of a power series with a ${2n\choose n}$ binomial coefficient? [duplicate]

In a step in a proof that the probability to return to origin in a symmetric random walk is $1$ the following combinatorics result seems important: $$\displaystyle \sum_{n=0}^\infty{2n\choose n}\,x^n ...
3
votes
1answer
36 views

What is the probability that all books of the same language land next to each other in a random arrangement?

4 different Mathematics books, 3 different German books, and 3 different Spanish books are arranged randomly on a shelf. What is the probability that all books of the same language will land next to ...
0
votes
0answers
32 views

Application of tensor product of graphs in real life.

I was going through the book HANDBOOK OF PRODUCT GRAPHS by Richard Hammack, Wilfried Imrich, and Sandi Klavzar. In the preface section, application of direct product of graphs is mentioned. I am ...
1
vote
2answers
35 views

If five letters from the word SPECIAL are arranged randomly with no repetitions, determine the probability that the word SPICE will be chosen.

Given the word SPECIAL, determine the probability that the word SPICE will be chosen if the letters from "SPECIAL" are arranged randomly without repetitions. Thanks, in advance.
0
votes
1answer
75 views

Can someone help me to prove this identity?

$$\sum_{i=0}^{n-1} \binom{4n}{4i+1}=2^{4n-2}$$
1
vote
1answer
56 views

How to show the matrix $\left( \binom{x-i}{j-1}\right)_{1\leq i,j\leq 2r+1}$ has determinant (-1)^r and it's inverse?

After playing around in mathematica, I found that the matrix $\left( \binom{x-i}{j-1}\right)_{1\leq i,j\leq 2r+1}$ has determinant $(-1)^r$ for the first few $r$'s. How can I prove this this, or at ...
3
votes
4answers
100 views

Number of ways to choose disjoint subsets.

Given a set $A$ of cardinality $rt$ where $r,t\in\Bbb N$ how many ways can you choose $t$ disjoint subsets of cardinality $r$? Is there an elementary formula and is there a name for this problem? I ...
0
votes
1answer
23 views

Solving Recurrence Relations with generating functions when the variable is in the function.

I'm studying for a midterm and couldn't figure out these three recurrences that I came across: $i_{n+1}=2ni_n+2i_n+2$ with initial condition $i_0=1$ $j_{n+1}=3j_n+1$ with initial condition $j_1=1$ $...
0
votes
1answer
33 views

sum of falling factorial $\sum_{k=0}^{n-1}\frac{n!}{(k+1)!}a^{n-k-1} $

I want to compute $\sum_{k=0}^{n-1}\frac{n!}{(k+1)!}a^{n-k-1}$. I note that it is similar to a generating function. The coefficients are falling factorials. Can I simplify it? Thanks!