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
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
59 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
58 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!
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},...
6
votes
4answers
202 views

Number of functions $f\colon\{1,2,3,\dots,n\} \to \{1,-1,i,-i\}$ satisfying a certain condition

What should I do here? I don't even know where to start from. Please help me by giving me a hint. Find how many are the functions: $f: \{1,2,3,\dots,n\} \to \{1,-1,i,-i\}$, where $n \geq 2$, such ...
3
votes
2answers
117 views

Binary encryption puzzle

There are 8 rooms, one containing a pot of gold. You know which room the gold is in, but your partner does not. The task is to inform your partner which room the gold is in under the following ...
2
votes
1answer
58 views

distribute $n$ white balls and $n$ colorful balls to $n$ cells

I got stuck with a question stating "let there $n\ge2$ and $n\in N$. in how many ways can you distribute $n$ colorful balls (different) and $n$ white balls (similar) to $n$ cells, such that in the ...
2
votes
2answers
59 views

Finding maximum value of ${n \choose r}$ for given value of n [duplicate]

While I was solving some binomial theorem chapter questions I encountered many questions which asked me me to find maximum value of ${n \choose r}$ for given value of n. Example: Find n for which $...
2
votes
2answers
48 views

describe odd number series

How to solve odd's 1 - > 1 3 - > 2 5 - > 4 7 - > 5 9 - > 7 11 - > 8 13 - > 10 15 - > 11 17 - > 13 19 - > 14 21 - > 16 23 - > 17 25 - > 19 27 - > 20 ......... ......... ......... 127 ...
1
vote
1answer
56 views

Finding the coefficient of $x^{50}$ in $\frac{(x-3)}{(x^2-3x+2)}$

First, the given answer is: $$-2 + (\frac{1}{2})^{51}$$ I have tried solving the problem as such: $$[x^{50}]\frac{(x-3)}{(x^2-3x+2)} = [x^{50}]\frac{2}{x-1} + [x^{50}]\frac{-1}{x-2}$$ $$ = 2[x^{50}]...
0
votes
0answers
13 views

Condition for n points in the plane to determine a convex n gon

Suppose there are n points in the plane, labelled 1 through n, no three of which lie on a line. Suppose further that for every triple [i,j,k] with i< j < k that travelling from i to j to k is ...
2
votes
2answers
26 views

$k$ kids, father and mother, it is forbidden to sit two chosen kids near to each other, How many ways there are to arrange them in line?

I have the following question : We have $k$ kids, father and mother, it is forbidden to sit two chosen kids near to each other. How many ways there are to arrange them in line? This is what I ...
0
votes
1answer
54 views

How to solve this Iran TST 2014,second exam, problem?

This Problem is Iran TST 2014, second exam, day 2 ,problem 3 Consider $n$ segments in the plane which no two intersect and between their $2n$ endpoints no three are collinear. Is the following ...
6
votes
4answers
122 views

Express $1 + \frac {1}{2} \binom{n}{1} + \frac {1}{3} \binom{n}{2} + \dotsb + \frac{1}{n + 1}\binom{n}{n}$ in a simplifed form

I need to express $$1 + \frac {1}{2} \binom{n}{1} + \frac {1}{3} \binom{n}{2} + \dotsb + \frac{1}{n + 1}\binom{n}{n}$$ in a simplified form. So I used the identity $$(1+x)^n=1 + \binom{n}{1}x + \...
0
votes
2answers
38 views

how many sequences above 1,2,3,4,5,6,7 that don't contain odd couples

I got stucked a little with this question. would appreciate your help. the question is "find a recursive relation that counts how many sequences of order n above ${1,2,3,4,5,6,7}$ that don't contain ...
-4
votes
2answers
29 views

Finding a closed formula of a given sum [duplicate]

I dont understand how to solve this question: I need to find a closed formula for : $$\sum_{k=0}^n k\,5^k$$ Thanks a lot!
0
votes
1answer
28 views

Pochhammer symbol finite summatory

I need some help in showing that in product among $n$ lower triangular matrices, the number of addends to be summed in order to obtain the value of the elements $(i, j)$ is: $\frac{<n>_{i-j}}{(i-...
1
vote
1answer
20 views

Listing all possible trebles from multiple sets where you can only select one element of each set

I'm stuck on a combinatorics problem and was hoping someone could help me. I would like to know the number of possible trebles (order not important) from sets of elements where only one element can ...
0
votes
3answers
69 views

Find recurrence relation with general solution $a_n=A+Bn+C2^n+\frac{1}{3}n2^{n-1}$

General solution is: $a_n=A+Bn+C*2^n+\frac{n}{3}*2^{n-1}$ Can you give me some tips on solving this? Any help would be appreciated.
2
votes
2answers
68 views

Chessboard Kings and no check [closed]

What is the largest number of kings which can be placed on a chessboard so that no two of them put each other in check?