# Tagged Questions

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.

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 ...
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 ...
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 ...
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 ...
74 views

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 $... 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. ... 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 ... 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 \{... 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 ... 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 ... 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 ... 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 ... 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, ... 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 ... 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)^... 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 ... 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. 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 ... 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 ... 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? 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 ... 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? 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$: ... 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 ... 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 ... 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) 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$... 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 ... 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. 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 ... 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 ... 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 ... 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 ... 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 ... 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. 1answer 75 views ### Can someone help me to prove this identity?$$\sum_{i=0}^{n-1} \binom{4n}{4i+1}=2^{4n-2}$$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 ... 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 ... 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 ... 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! 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 ... 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/... 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{... 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=... 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 \sum_{k = 0}^K C_k \... 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 ... 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 ... 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$...
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},...