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)

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.
6
votes
2answers
188 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
62 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
41 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
55 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
32 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!
2
votes
1answer
20 views

Partitioning binary strings by total parity

If I have a binary string $\underline{a} = (a_1 \, a_2 \,\ldots\, a_N)$ where $a_i \in 0,1$ and I partition the set of all such strings $A$ by the total parity of the string, $A = \Pi_0 + \Pi_1$ where ...
2
votes
1answer
33 views

A correct expression for Hardness?

I'm interested in whether it's possible to express the hardness of a result in the following form. 1.For example: Suppose $A(n)$ is the class of graphs for which the minimum degree $\delta(G)\geq n/...
0
votes
0answers
34 views

Is it possible to compute this series?

Question Given: $$ a_r = \sum_{ mn=r} \mu(m) c_n$$ where $\mu(m)$ is the mobius function. And $$c_n= n^s$$ Is there any asymptotic/direct method to compute the below? $$\sum_{r=1}^\infty \frac{...
0
votes
1answer
37 views

How is this combinatorial relation called?

I was trying to learn some set theory and came up with the following relation between the union and intersection: For any set consisting of sets $A$, we have: $$\left\vert\bigcup_{a\in A}a\right\vert=...
2
votes
0answers
65 views

Identity involving the Catalan numbers and binomial coefficients

Let $C_k := \frac{1}{k + 1} \binom{2k}{k}$ be the $k$-th Catalan number and let $K$ be a positive integer. I am looking for an identity or simplification of \begin{equation} \sum_{k = 0}^K C_k \...
-1
votes
1answer
29 views

Finding number of ways of selecting 6 gloves each of different colour from 9 pair of gloves? [duplicate]

There are nine pairs of gloves each of different colors in how many ways can we arrange six gloves such that each is of different color? I tried like this : First number of ways in which we can select ...
-2
votes
1answer
35 views

Finding number of ways of selecting 6 gloves each of different colour from 18 gloves? [closed]

There are nine pairs of gloves each of different colors in how many ways can we select six gloves such that each is of different color? I tried like this : First number of ways in which we can select ...
4
votes
1answer
61 views

A number which can be factored into a product of $k$ and $k+2$ consecutive natural numbers (each $>1$)

We say that the number $N \in \mathbb{N}$ has the property $P(k)$ if it can be factored into a product of $k$ consecutive natural numbers (not equal to $1$). Find the value of $k$ such that some $...
0
votes
1answer
42 views

Particular 6-regular graph on 42 vertices. [closed]

Does anybody know of the existence of any known graphs that are 6-regular on 42 vertices?
0
votes
0answers
27 views

Number Theory and p-Power-Partitioned Numbers

Given any natural number $N = a_{n}a_{n-1}\ldots a_{1}$, we're going to define its digits-partition as the set $D_{N} = \bigcup_{j=1}^{n}\bigcup_{k=1}^{p(a_{j})}\{(P_{k},j)\}$, where each pair $(P_{k},...