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)

3
votes
1answer
137 views

Closed formula for number of $n$ distinct topologies

While studying some topoligies I asked myself how many distinct topologies exist on a set of $n$ points. It can be shown there is a relation to $T_0$ topologies and a formula for $n$ distinct ...
0
votes
2answers
98 views

Upper bound for the number of primes in a series of n consecutive odd positive integers (all greater than 3)

Apart from 3, 5, 7, there cannot be three consecutive odd numbers which are all primes, as is well known. I wonder how this fact* can be used to calculate the upper bound in the title for any n. *: ...
1
vote
5answers
407 views

Number of solution for $xy +yz + zx = N$

Is there a way to find number of "different" solutions to the equation $xy +yz + zx = N$, given the value of $N$. Note: $x,y,z$ can have only non-negative values.
3
votes
1answer
123 views

Fun combinatorics: How many numbers with some restrictions

I came accross this fun problem today: How many 8-digit numbers are there where: each digit appears only one digits 1-4 appear sequentially (though not necessarily consecutively) 5 does not appear ...
1
vote
0answers
53 views

A family of $8$-regular Ramanujan Cayley Graphs

I'm looking for expander graphs with certain properties. Is there a family of $8$-regular Ramanujan Cayley graphs $\{\text{Cay}(G_n,S_n)\}_n$ such that each of them has no cycles of odd length? ...
0
votes
1answer
56 views

Number of rules in my fuzzy logic

I have 6 variables with 4 membership functions such as "tiny,small,large,huge". I tried to write the rules and came up with 200 rules but the combinations are killing me and it is still incomplete. ...
1
vote
2answers
194 views

What is the smallest alphanumeric string that has 10 million permutations?

I'm aiming to create UUIDs, for a project I'm working on. The standard UUID generators create a very long strings. I'm only anticipating a maximum of 10 million uses and because I'm storing that many ...
6
votes
1answer
129 views

Probability of adjacent seating

A homework question states: A room holds two rows of six seats each. Two friends are assigned randomly to the 12 seats. What is the probability that the 2 friends sit in adjacent seats? ...
2
votes
1answer
283 views

Recursive equation for palindromes

Can someone help me determine the recursive equation for all binary strings that are palindromes? A binary string is a palindrome if it reads the same forward and backward. Examples of palindromes are ...
1
vote
3answers
114 views

Find the generating function for this set of strings

Let $a(n)$ be the number of $\{0,1\}$-strings of length $n$ which contain no $4$ consecutive $1$'s and no $4$ consecutive $0$'s (don't contain "$0000$" or "$1111$"). Find the generating function for ...
5
votes
2answers
114 views

Binomial coefficients equal to a prime squared

I am looking for some reading on when binomial coefficients are equal to $p^2$ for $p$ a prime. In general I imagine this is rare, as there are simply too many factors. Concretely, I am looking for ...
5
votes
1answer
115 views

Closed form formula for the following sum

Does anyone know of a closed-form formula for the sum $\sum_{n = 1}^\infty x^{2^n-1}$? We can assume that $0<x<1$. Thanks!
2
votes
0answers
220 views

Unambiguous expression for binary strings containing some substring

Is there some systematic way for finding an unambiguous expression for a binary string which contains a certain substring? For finding expressions not containing a substring, it is sometimes easy to ...
1
vote
0answers
68 views

Characteristic polynomial of the tree

How can one show that a coefficient of $\lambda^{n-2k}$ in characteristic polynomial of the tree is a number of matchings of size k in this tree. $n$ is a number of vertexes in the tree.
1
vote
1answer
49 views

3-arc-transitivity of the Odd graphs

The Kneser graph $K_s^{(r)}, (s \ge 2r+1)$ has as its vertex set the $r$-subsets of $\{1,2,\ldots,s\}$, with two vertices being adjacent iff the corresponding subsets are disjoint. An exercise asks ...
1
vote
3answers
101 views

Need help with combinatorics question(probably cyclical permutation)

A human invites 6 of his friends to a meeting. In how many different arrangements they along with the human's wife can sit at a round table if the hosts and the wife always sit together? Is this a ...
2
votes
1answer
51 views

Number $e(n)$ of trees with $n+1$ unlabeled vertices $n$ labeled edges

How do I find the number $e(n)$ of trees with $n+1$unlabeled vertices $n$ labeled edges. We're suppose to give a simple bijective proof, I guess? Help appreciated!
1
vote
3answers
150 views

Distinguishable telephone poles being painted

Each of n (distinguishable) telephone poles is painted red, white, blue or yellow. An odd number are painted blue and an even number yellow. In how many ways can this be done? Can some give me a ...
0
votes
1answer
127 views

“Simmetric” connected k-regular bipartite graph

Let $G$ be a k-regular bipartite graph with $k > 0$. Then it is known that the two sets which partition the vertex set of $G$ have the same cardinality. However I am interested in connected ...
2
votes
2answers
74 views

Can we get the line graph of the $3D$ cube as a Cayley graph?

Given a graph $G=(V,E)$, the line graph of $G$ is a graph $\Gamma$ whose vertices are $E$ (the edges of $G$) and in $\Gamma$, two vertices $e_1,e_2$ are connected if, as edges in $G$, they share an ...
0
votes
1answer
96 views

Probability of 7 white chessboard squares without neighbours

If we start with a 2x30 chessboard and we remove 15 black squares, how can I find the probability that we get 7 white squares which don't have any neighbours? (A white square will have no neighbours ...
1
vote
0answers
170 views

How to find the parity check matrix for 101101101101101 in Hamming Codes (15,11) in graphic way?

I am trying to find hamming matrix for safe coded word: 101101101101101 My questions are: 1) What matrix check I should use? I mean there are two types of 15,11 => one starting with 1111 and one ...
0
votes
1answer
86 views

Arranging marbles in a row

Samson has $5$ identical blue marbles, $11$ identical white marbles and $4$ identical red marbles which he wants to arrange randomly in a row. What is the probability that: every red marble will ...
3
votes
1answer
133 views

Lower bound for the number of coin weightings

The book that I am currently studying has the following exercise. Given is a set of $n$ coins of weights $0$ or $1$ and a scale to weight them. We would like to determine the weight of each coin by ...
1
vote
1answer
148 views

Binomial coefficients as multiple sums

I found the formula $$ \sum_{n_1=1}^{n-1} \sum_{n_2=1}^{n_1-1} \sum_{n_3=1}^{n_2-1} \cdots \sum_{n_m=1}^{n_{m-1}-1} 1 = {n-1 \choose m} $$ But I don't know how to prove it. Should I use double ...
5
votes
0answers
109 views

Nice puzzle: Creating a binary word using weights and scales

You are given $N$ weights where for each $i \in \{1,2,...,n\}$, the $i$-th weight weighs $i$ pounds. You are given an $N$-binary-word that's formed by $L$'s and $R$'s and scales. You need to provide ...
0
votes
1answer
161 views

Optimal Solution Set To Linear Programs

I have the following assignment question, and I am not quite sure how to proceed. Q: Consider the following LP (P): $\max\{{c^Tx:Ax=b, x \geq 0}\}$, where $A$ is an $m$ by $n$ matrix. Prove or ...
0
votes
1answer
100 views

linear arrangements in a row

there are 7 teams A,B,C,D,E,F, each with 5 members. In how many ways can the 35 people be made to sit in a row such that every F team member sits next to i) at least one team G member 2^5*5!*30! (ANS ...
4
votes
0answers
73 views

What's the name for this unimodal sequence?

Let $a_0, a_1, \ldots, a_n$ be an increasing sequence of positive numbers, and consider the sequence $s_1,\ldots,s_n$, where $$ s_k \;=\; \frac{a_0+\cdots + a_k}{k}. $$ So $$ s_1 \;=\; a_0+a_1,\quad ...
0
votes
2answers
79 views

How many students like none of the toppings? (Principle of Inclusion - Exclusion)

There are 17 students. 11 students like one pizza topping 7 students like two of the toppings 4 students like 3 of the toppings 2 students like 4 of the toppings 1 students likes all of the toppings ...
3
votes
2answers
74 views

Is there a nice characterization of these classes of functions on a set of $n$ elements?

I am looking at the set of all functions from $[n] \to [n]$, where $[n] = \{1,2,\dots,n\}$. Now, I consider two functions equivalent, if they are conjugates by some permutation, that is, they are the ...
2
votes
1answer
218 views

Proof using the rule of product or multiplication rule of combinatorics.

Assume that set $A$ has $r$ elements, and set $B$ has $n$ elements (both of them are finite and not empty sets), I need to proof using the rule of product or multiplication principle of ...
0
votes
1answer
27 views

show that $|\cup^n_{i=0} X_i| = \sum \binom{n}{r}\binom{r}{r-i}\binom{n-r}{s-i}$

Define $$ X_i = \{(D,E,F) : D \subseteq N_n, |D| = r,E\subseteq D, |E|=r-i,F\subseteq N_n - D, |F|=s-i\} $$ Where $N_n$ denotes the set of all subsets. $$|X_0 \cup X_1 \cup \ldots\cup X_n| = ...
1
vote
1answer
67 views

FInd the number of pairs $(A,B)$

Let $n,r,s$ be given, where $n\geq 1$,$1\leq r\leq n$ and $1\leq s \leq n$. a) determine the number of pairs $(A,B)$ with $A\subseteq N_n, |A|=r,B\subseteq N_n, \text{and} |B|=s $ Now my ...
0
votes
0answers
36 views

Finding the addends behind an output series.

Let's imagine that we have a series of output, say, scores $S_1,S_2,\ldots,S_n \in \mathbb{N}$. We know that these scores are the result of addition of natural numbers, such that the highest score is ...
7
votes
2answers
219 views

Rearrangement of dinner guests

A dinner host wants his guests to move, between main course and dessert, so that everyone gets a complete set of new neighbours. Guests are seated either side of a long table. Most guests have five ...
5
votes
1answer
166 views

Count number of special onto functions

We define an onto function from $[n] \times [n]$ to $[n-2] \cup \{0\}$ as follows, where $[n] = \{1,2,3,\ldots ,n\}$, $$f : [n] \times [n] \rightarrow [n-2] \cup \{0\}.$$ 1) $f(x,x) = 0$. 2) ...
3
votes
1answer
57 views

Standard Approach to the Fundamental Counting Principal

I'm trying to teach myself combinatorics from a textbook. The last question of the first chapter is as follows: If A is a finite set, its cardinality $o(A)$, is the number of elements in $A$. ...
2
votes
1answer
99 views

Is this graph coloring problem solved correctly?

On this Wikipedia page about Burnside's lemma, it is calculated that there are 57 rotationally distinct colorings of the faces of a cube with three colors. I'm confused by the way it is done. They ...
3
votes
1answer
93 views

Bijection between multisets and directed animals?

The number of directed animals (aka polyominoes) of size $n$ (A005773) is enumerated by the generating function $$\frac{1}{2} \left(1+\sqrt\frac{{1+z}}{{1-3 z}}\right).$$ This generating function ...
2
votes
1answer
84 views

Simple problem on restricted partition

When finding number of ways to partition n distinct chocolates among m children such that each child has at most $$\left\{\begin{matrix} \left \lfloor \frac{n}{m} \right \rfloor & \text{if} \ \ ...
2
votes
1answer
273 views

Distributing $k$ distinct items among $r$ distinct groups without ordering

Calculate the number of ways of distributing $k$ distinct items among $r$ distinct groups such that each group receives at least $a$ and at most $b$ items and internal arrangement of items ...
1
vote
1answer
49 views

Simple question of maximum value a part can have?

We have to partition n chocolates among m children. Children will be happy if max and min a child has got is less than 2. What is the max a child can get?? For n=6 m=3 ,the partition will be 2 2 2 ...
3
votes
2answers
81 views

Sperner's Lemma in infinite-dimensional spaces?

I've been looking at Sperner's Lemma for a little while and have managed to come to grips with some of the combinatorial proofs. Some descriptions I have encountered claim to prove it for "simplices" ...
0
votes
3answers
111 views

Newton's binomial problem

It is known that in the development of $(x+y)^n$ there is a term of the form $1330x^{n-3}y^3$ and a term of the form $5985x^{n-4}y^4$. Calculate $n$. So, I know that the binomial formula of Newton ...
0
votes
1answer
39 views

Compute the number of injective mappings

Proof that the number of injective mappings of $A=\{a_1,a_2,a_3,\dots,a_r\}$ in $B=\{b_1,b_2,b_3,\dots,b_n\}$ with $r\leq n$ is $$n(n-1)\dots(n-r+1)=\frac{n!}{(n-r)!}.$$
4
votes
3answers
117 views

Points on a sphere

We draw n points, A, B, C, ... Z, on the upper hemisphere of a sphere, and their n antipodal points on the lower hemisphere, a, b, c, ..., z. We draw the n(n-1)/2 great circles connecting each pair ...
2
votes
0answers
106 views

Eliminating negative binomial coefficients

I have a sum $$\sum_{m=0}^{n}\sum_{j=0}^{k}(-1)^j{k \choose j}{n-mj \choose k}$$ that comes up when counting compositions. Now the trouble is, if I would interpret it literally and for $n<mj$ ...
1
vote
0answers
36 views

Weights for degree ordering

Let $x_1,x_2,x_3$ be indeterminates. Fix an integer $k\geq 3$. Consider the set $M$ of all monomials of the form $x_1^{i_1}.x_2^{i_2}.x_3^{i_3}$ where each $i_j\in \mathbb{N}$ with $i_j\geq 1$ and ...
1
vote
4answers
670 views

distributing z different objects among k people almost evenly

We have z objects (all different), and we want to distribute them among k people ( k < = z ) so that the distribution is ...